Model Reduction of Complex Dynamical Networks
based on State Aggregation
Takayuki Ishizaki (Tokyo Institute of Technology)

Contents
 Overview of model reduction problem

what is model reduction?
 error evaluation in terms of(preliminary)-norms

 Network structure preserving model reduction(main)

system description of dynamical networks
 key idea of state aggregation with an-error evaluation
 numerical example State aggregation with an
2/22

controllability gramian-error evaluation (additional)

Overview of Model Reduction
Given stable system

input-to-state map

3/22

FindFindstate-to-output map

such that

Stable reduced model

Dimension of state:is small enough※Typical System Norms
stable system: Laplace transform of※: Frobenius norm ofsolution
impulse responsetransfer function-normmaximum gain

-norm

energy of impulse response-norm of
4/22

Contents
 Overview of model reduction problem

what is model reduction?
 error evaluation in terms of(preliminary)-norms

 Network structure preserving model reduction(main)

system description of dynamical networks
 key idea of state aggregation with an-error evaluation
 numerical example State aggregation with an
5/22

controllability gramian-error evaluation (additional)

System Description[Definition] (single-input) Dynamical Network
A linear system

andwithis said to be a dynamical network

ifis stable and symmetric.

A generalization of reaction-diffusion systems:

where
6/22

: intensity of reaction (chemical dissolution): intensity of diffusion between
andConnected undirected graphstable, symmetricDrawback of
Traditional Model Reduction Methods
 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

Reduced model: full matrix: sparse : dense 
no physical interpretation...

State Aggregation Approach Model reduction by aggregating disjoint sets of states

Block-diagonally structured aggregation matrix



Network topology among clusters is to be preserved Coarse

weighting
vectors

Clusters

Fine

How to find “reducible” clusters?
※ For simplicity of notation, suppose the indices are permuted accordingly to clusters

Key Observation
to Construct Reducible Clusters
th orderGiven[State behavior under a input signal]
abouttrajectories

Clustering
accordingly to behavior

can be aggregated into
dimensional variables??
[Definition] Reducible Cluster
Letbe the index set of the -th cluster.

-th cluster

The -th cluster is said to be reducible if
where
under any input signal
9/22.

Basis Expansion
via Positive Tri-diagonalization
Dynamical network[T. Ishizaki et al. CDC 2010]

Positive tri-diagonal pairtri-diagonal

DC-gain is maximalbasis expansion

where10/22

Aggregation of Reducible ClustersCluster reducibility:[Theorem] Let

be the index set of the -th cluster.

The -th cluster is reducible if and only if
Furthermore,holds for: unitary, i.e.,
Aggregated model

Dynamical network

Elimination of uncontrollable subspace with block-diagonally structured

Reducibility:

Simple Example

whereGiven

positive tri-diagonal pairaggregation: solid lines: dot-lines

holdsRelaxation of Reducibility Condition
Dynamical network

exactly same behavior

similar behavior
13/22Aggregation of Weakly Reducible Clusters
and define

Denote[Definition]-weakly Reducible ClusterThe cluster

is -weakly reducible if※CoarseAggregated model: coarsenessparameter
Dynamical network

Fine[Theorem] Let
Suppose all clusters areThen,-weakly reducible, and takehold for an

determined by.

Algorithm to Construct
Weakly Reducible Cluster Set
Given network• Give, Initialize

While•• Choose, Set• For allif-weak reducibility condition:

where15/22

and,satisfies, thenNumerical Example
 Holme-Kim model ofnodes

a famous complex network model

non-zero edge weight is randomly chosen fromcluttered... 16/22

clustersclusters

Remarks on-aggregation

 Similar aggregation approach admits to multi-input systems


positive tri-diagonalization with respect to each input signal

 Aggregation of positive networks preserves the positivity
positivity: non-negativity of off-diagonal entries ofand entries of Generalization to positive directed networks is also possible

asymmetric with non-negative off-diagonal entries
 tri-diagonalization is replaced with Hessenberg transformation
 however, higher computational costs are to be required


17/22

Contents
 Overview of model reduction problem

what is model reduction?
 error evaluation in terms of(preliminary)-norms

 Network structure preserving model reduction(main)

system description of dynamical networks
 key idea of state aggregation with an-error evaluation
 numerical example State aggregation with ancontrollability gramian

18/22-error evaluation (additional)

-aggregation based on Controllability Gramian-norm:

Positive semi-definite solution: controllability gramian
relates toof Lyapunov equation

is non-singular-norm & controllability[Theorem]
The cluster

19/22

is reducible if and only if

is controllable

Aggregation of Weakly Reducible Clusters
Denoteand define[Definition]-weakly Reducible Cluster

The cluster

is -weakly reducible if[Theorem] Let
Suppose all clusters areThen,

20/22-weakly reducible, and takehold for a positive constant.

Remarks on-aggregation

 Lyapnov equation

is identical regardless ofsingle- or multi-input systems
 moreover, regardless of symmetry of Generalization to positive directed networks is also possible

preserving network topology, stability, and positivity that to systems with arbitrary stable
is difficult not only error evaluation, but also guaranteeing stability of reduced model

21/22

Summary
 Model reduction based on state aggregation is proposed

preserving network structure
 aggregation of reducible clusters
 characterization via positive tri-diagonalization leads to characterization via controllability gramian leads to-aggregation-aggregation

 Aggregation techniques have ability to preserve other propertiessystem positivity, second order (oscillator) structure, etc…
CoarseAggregated model

Dynamical network
22/22

Fine