Clustering-based State Aggregation of
Dynamical Networks
Takayuki Ishizaki
Ph.D. from Tokyo Institute of Technology (March 2012)
Research Fellow of the Japan Society for the Promotion of Science
More than 10 hours

From Tokyo to Stockholm

I am (was?) tennis man

Model Reduction via Projection
Given stable system

input-to-state mapstate-to-output map

Find

Stable reduced modelDim. of state:✓Findsuch thatis small enough

2/22

Typical System Norms
Stable system✓: Laplace transform: Frobenius norm

Solution
Impulse response

Transfer function-norm

Maximum gain-norm
Energy of✓-norm of3/22

Contents
Clustering-based State Aggregation in terms of-norm

How to reduce systems while preserving network topology?
Use of positive tri-diagonalization
Application to diffusion process over complex network-aggregation of Positive Networks
Preservation of network topology as well as positivity
Use of controllability gramian
Application to Chemical Master Equation
4/22

System Description[Definition] Bidirectional Networkwithis said to be bidirectional network

andif

is symmetric and stable.

Including reaction-diffusion systems:: reaction of: diffusion between

and

5/22

Traditional Model Reduction
Traditional model reduction methods
Balanced truncation, Krylov projection, Hankel norm approximation
No specific structure in transformation matrix
Drawback: Network structure (spatial information) is destroyed
Given: Sparse Reduced model✓: Dense: Dense 

Need to impose suitable sparse structure on

6/22

Clustering-based State Aggregation
Aggregation of disjoint sets of states (clusters)
Block-diagonally structured aggregation matrix
Interconnection topology among clusters is preserved Coarse
ClusterFine

How to find reducible clusters?
✓ For simplicity, Aggregation = Averaging:

7/22

Key Observation
to Construct Reducible Clusters
50th order

Given[State trajectory under random input]
About
trajectories

Clustering
accordingly to behavior
can be aggregated into
dimensional variables??

[Definition] Reducible Cluster
A clusteris said to be reducible if
underwhereany input signalCluster.

Positive Tri-diagonalization[Lemma] For every bidirectional network, there exists a unitarysuch thathas the structure below.

Bidirectional network

Positive tri-diagonal realization(not necessarily positive)

Metzler

for allReducibility Characterization
Bidirectional network: positive tri-diagonal realization: transformation matrix
Index matrix

reducible

reducible: DC-gain

Maximal gain
due to positivity

identical
identical

Cluster reducibility is characterized by rows of

10/22

Reducible Cluster Aggregation
Reducibility:[Theorem] A cluster

is reducible iff

Furthermore, if all clusters are reducible, thenCoarseholds.

Aggregated modelwith
Dynamical network

Fine

Relaxation to??
11/22

Reducibility Relaxation[Definition]-reducible Cluster

A clusteris said to be -reducible if✓

for row vector: coarseness parameter[Theorem] If all clusters are -reducible, thenholds wherelinear dependence onPreservation: Stability and Interconnection topology among clusters In addition,

represents average of original state
12/22

Cluster Set Construction• Give, Initialize

While•• Choose, Set• For allif,
satisfies, then- reducibility :where✓ Cluster set to be obtained is not necessarily unique
13/22

Numerical Example
Diffusion process over the Holme-Kim model (3000 th dim.)(less than 0.5% error) if
Dim. ofreduced modelError boundThe value of276 clusters(276th dimensional model)14/22

Contents
Clustering-based State Aggregation in terms of-norm

How to reduce systems while preserving network topology?
Use of positive tri-diagonalization
Application to diffusion process over complex network-aggregation of Positive Networks
Preservation of network topology as well as positivity
Use of controllability gramian
Application to Chemical Master Equation
15/22

System Description[Definition] Positive Networkwithpositive network

andif

is said to be

is Metzler and (marginally) stable, and.

Metzler matrix : having
non-negative off-diagonal entries: non-negative
non-negative propertye.g., Heat diffusion systems, Electric circuit systems, Markovian processes

Model reduction while preserving positivity, stability and network

16/22

Reducibility Characterization ( -case)
Givenwith stable

Controllability gramian✓ Lyapunov equation

reducible

reducible

Cholesky factorization

identical
identical

Cluster reducibility is characterized by rows of

17/22

-State Aggregation[Definition]-reducible Cluster

The cluster

is said to be -weakly reducible if✓: coarseness parameter[Theorem] If all clusters are -weakly reducible, thenholds wherelinearly bounded byPreservation: Stability, Positivity, Interconnection topology among clusters
18/22

Generalization to
Marginally Stable Positive Networks
Gramian is not defined if

has zero-eigenvalue Projected gramianwhere✓

is orthogonal complement ofsuch thatControllability gramian of stable projected system
Unique positive semi-definite matrix for
Cholesky factorization
identical: Graph Laplacian

identical
19/22

Application toChemical Master Equation（CME）
Michaelis-Menten systemex) Initial number ofare both[Realizable distributions]: reaction rate constantStateRealization
probabilitywith

CME expression:
Continuous-time Markovian process
off-diagonal entries of are non-negative
column sums of are zeroth dimensional(zero-eigenvalue)
20/22

Numerical Example
th order[Reduced order versus

ifth order[Trajectories of]]: solid lines: dot lines

Validates ascoarseness parameter

Relative error ofandin-norm:
21/22

Summary
Clustering-based State Aggregation
positive tri-diagonalization leads to-aggregation
controllability graman leads to -aggregation

Preserving interconnection topology as well as stability, positivity
Application to diffusion process over complex networks and CMEs
CoarseAggregated modelwith
Dynamical networkFine
22/22