第8部（数理談話会）

九大数理談話会
複雑ネットワークと制御理論
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
内容









スケールフリーネットワーク
スケールフリーネットワークの構造的可制御性
最小支配集合（MDS)
MDSサイズの理論解析
計算機シミュレーションによる解析
データベース解析
生物情報ネットワーク解析への応用
MDSの拡張
結論

共同研究者:
Jose Nacher [Toho U.]
スケールフリーネットワーク
スケールフリーネットワーク（１）

頂点の次数


P(k)



次数=5
その頂点につながっ
ている辺の個数
次数分布
次数 k の頂点の頻
度
次数=2
スケールフリーネッ
トワーク

P(k) がべき乗則に
従う
P( k )  k

次数=3
代謝マップ, グラフ, 次数
A



D
F
G
H
I
J
次数1の頂点： J
次数2の頂点： B, C, D, F, G, H
次数3の頂点： E, I, A
次数分布: P(k)

C
E
次数


B
P(1)=0.1, P(2)=0.6, P(3)=0.3, P(4)=P(5)=P(6)=…=0
スケールフリーネットワーク（２）
次数=5
次数=2
頂
点
数
頂点数 ∝ (次数)-3
次数
次数=3
スケールフリーネットワークの
構造的可制御性
[Liu, Slotine, Barabasi: Nature, 2011]
線形システムの可制御性（１）
入力:


dx(t )
 Ax(t )  Bu(t )
線形システム:
dt
初期状態: x0 目標状態: xF
出力:

有限時間で、システムの状態を x0 から xF へ
導く制御 u(t) (tの関数)
x(t): N-dim. real vector (internal nodes)
u(t): M-dim. real vector (control nodes)
A: N×N real matrix
B: N×M real matrx
 x1 
 
 x2 
  
 
 x 
 N
 x1 
 u1 
 
 
 x2 
 u2 
A   B 


 
 
u 
x 
 M
 N
線形システムの可制御性（２）
定理. システムが可制御 iff
N×NM 行列 C=(B,AB,A2B,…,AN-1B) のランクがN
(i.e., rank(C)=N).
 0

 a21
A
a31

a
 41
0 
 b11 0 



0 0 0 
 0 b22 
B

0 0 a34
0
0





0 0 0 
0 
0
0 0
 b11 0

 0 b22
C 
0
0

0
0

0
0
0
0
a21b11 0
0
0
a31b11 0 a34a41b11 0
a41b11 0
0
0
ほとんど係数について rank(C)=4 ⇒ 構造的可制御性
0 0

0 0
0 0

0 0 
構造的可制御性
GB(VL,VR;EB) : G(V,E) から以下により構成した二部グラフ
V L  {xiL | xi V }, V R  {xiR | xi V }, ( xi , x j )  E  ( xiL , x Rj )  EB
定理. [Liu et al. 2011]
M* を GB の最大マッチングのサイズ（辺数）とする時。
システムを構造的可制御とするために必要な制御頂点（driver
nodes）の最小数は max {N-M*,1}
driver
nodes
スケールフリーネットワークの構造的可制御性
構造的可制御のための driver nodes 数 [Liu et al. 2011]
 ランダムなネットワーク
N D  n  e  k  / 2

スケールフリーネットワーク
 

N D  n  exp  12 1   11  k 

⇒ γ<2 の場合、多くの driver nodes が必要
n: ネットワークの頂点数
最小支配集合（MDS）
最小支配集合（１）


VD が無向グラフ G(V,E) の支配集合（dominating
set） ⇔ (∀v∈V)（v ∈VD∨(∃u∈VD)({u,v}∈E))
最小支配集合（MDS: minimum dominating set）:
要素数最小の支配集合
最小支配集合（２）


NP困難であるが、線形計画法＋分枝限定法に基
づく実用的ソフトが存在
人工ネットワークの設計・制御への既存応用



mobile ad-hoc networks (MANET)
transportation routing
computer communication networks
MDSと可制御性の関係
定理. [Nacher & Akutsu, 2012]
ネットワークの各辺は両方向性であり、MDSの各頂点はすべて
の接続辺を個別に制御可能であると仮定。すると、MDSを
driver nodes として選択すれば、システムは構造的可制御。
MDSサイズの理論解析
解析結果（近似的な解析）
γ>2
 上限: trivially O(n)
 下限: O(n) (to be shown)
γ<2
 上限: O(n1-(2-γ)(γ-1))
 下限: ?
γ>2 の時の下限（１）

次数分布がαk-γに従うとして、以下のようにαを決定
n
n  k  dk 
1


n
(1  n  1 )  n      1
 1
C(S) をS と V-S の間の辺の集合とすると、
|S|+|C(S)|<n であれば、 S は支配集合でない
S として次数 K 以上の頂点をすべて選ぶと
n
n
| C ( S ) | n  k  k dk  n(  1)  k  1dk
K

K
  1   1
  1  1
1 
     2    2   n  
    2
 n  
n 
 2  K
 2 K
γ>2 の時の下限（２）


|S|<n/2 を仮定できるので、
  1  1
    2  n / 2
n  
 2 K
よって、 |S| の下限は以下のように見積もれる
1 
 1
| S | n  k dk  n  1   1 
K
n 
K
n

 1      1 

 n    1   2  
 K      2 


 1
 2
n
これは γ についての増加関数になっている
γ<2 の場合の上限の解析 (1)


次数 K=nβ 以上の頂点集合を DS とする
その頂点数NDS は、
n
N DS  n  k  dk  n(n  ( 1)  n ( 1) )  O(n1 ( 1) )
n

一方、辺の総数 EG は、
n
EG  n k  k  dk  2 1  n  (n 2  1)
1

EDS (=DSに接続する辺の個数) は、
n
EDS  n  k  k  dk  2 1  n  (n 2  n  ( 2 ) )
n

よって、任意に選んだ辺が DS に接続しない確率は、
EG - EDS n b (2-g ) -1 ( b -1)(2-g )
= 2-g
»n
EG
n -1
γ<2 の場合の上限の解析 (2)

DSに接続しない辺があると、その頂点がDSにカバーされない可
能性 ⇒ DSにカバーされない頂点数の期待値 (NG-DS) は次式
以下
N G  DS  O(n  n (  1)( 2 ) )  O(n1 (  1)( 2 ) )

NG-DS と NDS をバランスさせると

1   (  1)  1  (   1)( 2   )
より、β=2-γ を得る
よって、MDS の上限は
Î G - DS
O(n1( 2 )( 1) )


この式は 1<γ<2 において o(n)
さらに、γ=1.5 の時、最小オーダー (O(n0.75))となる
This analysis is a corrected version of one in our paper appeared in New Journal of Physics.
γ<2の時の説明

次数 nβ 以上の頂点数
1  (  1)
次数
≥nβ
N DS : O(n
)
 そこから出る辺でカバー
されない頂点数
1 (  1)( 2  )
N G  DS : O(n
)
 以下を満たす β を選ぶ
n1  ( 1)  n1 (  1)( 2 )
   2
カバー
されない
頂点

MDSのサイズ
O(n1( 2 )( 1) )
生物情報ネットワーク解析
への応用
MDS の生体ネットワーク解析への応用



実際の生物の制御は困難
でも、MDS は重要性の高いタンパク質や遺伝
子の検出には有効
タンパク質相互作用ネットワーク解析への応用





[Milenkovic et al. PLoS One, 2011] (before our work)
[Wuchty, PNAS, 2014]
[Khuri & Wuchty, BMC Bioinformatics, 2015]
[Wang et al., BIBM 2014]
代謝ネットワーク解析への応用

[Asgari et al., PLoS ONE, 2013]
タンパク質相互作用ネットワーク解析への応用

MDSは重要なタンパクの検出に有効 [Wuchty, PNAS 2014]
 必須遺伝子、がん関連遺伝子、ウィルスの標的遺伝子などに
おいて、MDS 中のタンパク質の比率が高い.
 These proteins are highly involved in regulatory functions,
showing high enrichment in transcription factors and
protein kinases, and participate in regulatory links,
phosphorylation events, and genetic interactions.
[Wuchty, PNAS 2014]
MDSの拡張
二部グラフ構造を持つネットワークの制御
多くのネットワークは二部グラフ構造を持つ
薬剤・標的、研究者・共著論文、遺伝子・疾患ネットワークなど
左側頂点のみが制御頂点となる
MDSは常にLiuらの手法以下の頂点数を与える
[Nacher & Akutsu: Sci. Rep. 2013]
必須・冗長頂点の計算

Jiaらにより提案された必須および冗長頂点 [Jia et al.: Nat. Comm. 2013]
の概念をMDSに適用（⇐MDSは一意とは限らない）



必須頂点: すべてのMDSにおいて出現
冗長頂点: どのMDSにも出現しない
必須頂点は単なるMDS頂点より重要性が高いと考えられる
[Nacher & Akutsu:
J. Comp. Net. 2015]
ロバストMDS

ロバストMDS (RMDS): 各頂点がC個以上の頂点によりカバ
ーされる (C=1 ⇒ MDS)


任意の C-1 個の辺の削除に対してロバスト
RMDS サイズの上限 (γ<2の時):

 1 ((DDCC 11)()(22 )() 11) 
O n



(D: 最小次数)
RMDSサイズは最小次数が D-C+1のMDSサイズとオーダーが一致
[Nacher & Akutsu:
PRE, 2015]
Molnarらによる研究



次数カットとMDSサイズの関連性 [Sci. Rep. 2013]
次数相関とMDSサイズの関連性 [Sci. Rep. 2014]
ランダム、および、恣意的なダメージに対して
ロバストなMDS [Sci. Rep. 2015]
結論
既存結果と矛盾しない理由

Liu et al.


Driver node の値のみが制御可能と仮定
提案手法（MDS法）
各 driver node は接続辺を個別に制御可能と仮定
⇒ 次数 k の頂点は、k 個の driver nodes に相当

結論



γ<2 であれば、MDSのサイズは小さい(o(n)) ⇒ 非一様性の高
いネットワーク（heterogeneous network）は制御が比較的容易
その傾向をシミュレーション解析およびデータベース解析により
検証
人工ネットワーク(e.g., mobile networks and computer
networks) では接続辺の個別な制御が可能であると思われる
ので、この結果が有効である可能性

しかし、生体内ネットワークではその仮定が成立しない
今後の課題


生体内ネットワークの制御を容易とする理論的枠組みの構築
MDSサイズのより精緻な解析

Download Report