大規模ネットワークシステムのクラスタ低次元化

石崎 孝幸 （東京工業大学）

Outline
Introduction: Why clustered model reduction?
Clustered Model Reduction Theory
Examples

Input

OutputConclusion
Clustered model reduction
Input

Output2/26

Large-Scale Network Systems
Power Network

Thermal power

Tokyo area: 20 million houses
rate of houses with PV will increase
up to 50% by 2030 (PV2030)
50% of total maximum power

Power line
homes
Micro Gridhomes

PV

Hydroelectricpower

How should
weprospective
stabilize?
Model reduction
is oneapproach

Traffic Network
Center of Tokyo area: 5 million cars
Heavy traffic jam
average velocity 20km/h

How should we improve?

3/26

Model Reduction Methods
Heat diffusion✓Output

Input

Main goal: Findsuch thatis small enough+ stability preservation, error bound derivation, low computational costStandard methods:
Balanced truncation, Hankel norm approximation
error bound, stability preservation  high computational cost Krylov projection
lower computational cost  possibly unstable model, no error bound 4/26

Drawback of Standard Methods
Network system

Reduced modelNo specific structure

Sparse Dense Drawback: Network structure is lost through reduction

5/26

Clustered Model Reduction
Network system

Reduced model

Aggregated state

Cluster state: row vector

Sparse Sparse 

Preservation of network structure among clusters
6/26

Why Clustered Model Reduction?
Gene Network [Mochizuki et al. , J. Theoretical Biology (2010)]

Clustered model reduction

Extract essential principle
to show mechanism of functions
Other possible application: Hierarchical decentralized control

7/26

Outline
Introduction: Why clustered model reduction?
Clustered Model Reduction Theory
Examples

Input

OutputConclusion
Clustered model reduction
Input

Output8/26

Typical System Norm
Stable system
Transfer function-norm-norm✓

solution
impulse response✓: Laplace transform
Maximum gain

Energy of impulse response-norm of: Frobenius norm

9/26

System Description[Definition] Bidirectional Networkwith
is said to be bidirectional network

andif

is symmetric and stable.

Reaction-diffusion systems:

10/26

Clustered Model Reduction Problem✓

Reduced model

Bidirectional network
Cluster state

Aggregated state(i) Find a set of reducible clusters(ii) Find suitable aggregation weights: row vector

Sparse Sparse [Problem] Given
where, find a block-diagonal
andsuch that

11/26

How to Formulate Reducibility?
Bidirectional network[State trajectory under random]

7 clusters

50 trajectories

50 nodes, nonzero
israndomly chosen fromcan be aggregatedinto 7-dim. variable?

[Definition] Reducible cluster
LetA cluster

is said to be reducible if
for any

12/26

Positive Tridiagonalization[Lemma] For every bidirectional network
such that
Bidirectional network, there exists a unitary
has the following structure.

Positive tridiagonal realization(not necessarily positive)

Metzler✓

13/26

Reducibility Characterization
Bidirectional network: positive tridiagonal realization: transformation matrixIndex matrix

reducible

reducible: DC-gain

Maximal gain
owing to positivity

identical
identical

Equivalent characterization of cluster reducibility

14/26

-Reducible Cluster Construction[Definition]-reducible Cluster

A clusteris said to be -reducible if: coarseness parameter

Procedure for finding a cluster set(i) Given, calculate the index

matrix(ii) For a fixed , findsatisfying
above definition of -reducibility
15/26

Reducible Cluster Aggregation[Theorem] DefinewithIf all clusters are -reducible, thenholds whereCoarselinear dependence on

Reduced model
with
Bidirectional network

Fine
16/26

Remarks
Clustered model reduction
preserves stability & network structure of original systemprovides a priori-error boundgives method to find a cluster set
requires low computational cost
[T. Ishizaki et al. IEEE TAC (2014)]

This method can be extended tomulti-input systems
positive directed networks
asymmetric with nonnegative off-diagonal entries
a priori -error bound[T. Ishizaki et al. ACC12, CDC12]
17/26

Outline
Introduction: Why clustered model reduction?
Clustered Model Reduction TheoryExamples

Input

OutputConclusion
Clustered model reduction
Input

Output18/26

Scale-Free Networks
Hole-Kim model (1000 nodes)
small world, high cluster coefficient
random edge weights
47 nodes27 nodes19/26

Computational Complexity
Total

Calculation time [sec]900

Others

800
700
600

Clustering

500
400
300
200

Tridiagonalization

10000

1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

Dim. of original networks
Matlab R2011b 64bit Intel® Core™ i7-2620M CPU @2.70GHz, RAM 16.0GB

20/26

Scale-Free vs Erdős-Rényi Networks
1000 nodes, around 2000 edges, two inputs
Random edge weights0.7
0.6: Erdős-Rényi: Barabási-Albert

0.4
More
effective for scale-free networks(scale-free)
0.3
0.2

uncontrollable?

0.1
00

20

40

60

80

100

120

140

160

Dim. of reduced models≈

Relative error

0.5

180

1000
21/26

Application to Chemical Reaction
Michaelis-Menten system# of(a)&are initially both(a)(b)(b): Probability of th distribution

CME expression✓-dim. (in practice, more than 10000-dim. )
Approximate

in terms of-norm (-norm)

22/26

Clustered Model Reduction of CME
th orderth orderif✓ Preservation:
property as probabilityand]: solid lines: dot lines

relative error# of clusters[Trajectories ofsteady state

states are
not aggregatedone HUGE cluster
is madeCluster size

23/26

Application toAverage State Observation
Network system

Average state observer

Findsuch that1000-dim.

is small enoughObservation by 5-dim.
: System state: Observation[Time]

24/26

Concluding Remarks
Clustered model reduction
extract essential information on input-to-state mapping
application to scale-free networks, CMEs, average state observation

Open problems:
approximation of input-to-output mapping
more sophisticated clustering algorithm
networks of high-dimensional subsystems
nonlinear systems
application to control system design
25/26

Acknowledgements
Collaborators:
Kenji Kashima (Kyoto University)
Jun-ichi Imura (Tokyo Institute of Technology)
Antoine Girard (University of Grenoble)
Luonan Chen (Chinese Academy of Sciences)Kazuyuki Aihara (The University of Tokyo)

Thank you for your attention!
26/26