九大数理談話会 複雑ネットワークと制御理論

Presentation on theme: "九大数理談話会 複雑ネットワークと制御理論"— Presentation transcript:

1 九大数理談話会 複雑ネットワークと制御理論
九大数理談話会 複雑ネットワークと制御理論 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

2 内容 スケールフリーネットワーク スケールフリーネットワークの構造的可制御性 最小支配集合（MDS) MDSサイズの理論解析
計算機シミュレーションによる解析 データベース解析 生物情報ネットワーク解析への応用 MDSの拡張 結論 共同研究者: Jose Nacher [Toho U.]

3 スケールフリーネットワーク

4 スケールフリーネットワーク （１） 頂点の次数 P(k) スケールフリーネットワーク P(k) がべき乗則に従う
スケールフリーネットワーク　 （１） 頂点の次数 その頂点につながっている辺の個数 P(k) 次数分布 次数 k の頂点の頻度 スケールフリーネットワーク P(k) がべき乗則に従う

5 代謝マップ, グラフ, 次数 A B C D F G H I J E 次数 次数分布: P(k) 次数1の頂点： J
次数3の頂点： E, I, A 次数分布: P(k) P(1)=0.1, P(2)=0.6, P(3)=0.3, P(4)=P(5)=P(6)=…=0

6 スケールフリーネットワーク （２） 頂点数 頂点数 ∝ (次数)-3 次数

7 スケールフリーネットワークの構造的可制御性
[Liu, Slotine, Barabasi: Nature, 2011]

8 線形システムの可制御性 （１） 入力: 出力: 線形システム: 初期状態: x0 目標状態: xF
線形システムの可制御性　（１） 入力: 線形システム: 初期状態: 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

9 線形システムの可制御性　（２） 定理. システムが可制御 iff N×NM 行列 C=(B,AB,A2B,…,AN-1B) のランクがN (i.e., rank(C)=N). ほとんど係数について rank(C)=4 ⇒ 構造的可制御性

10 構造的可制御性 定理. [Liu et al. 2011] GB(VL,VR;EB) : G(V,E) から以下により構成した二部グラフ
M* を GB の最大マッチングのサイズ（辺数）とする時。 システムを構造的可制御とするために必要な制御頂点（driver nodes）の最小数は max {N-M*,1} driver nodes

11 スケールフリーネットワークの構造的可制御性
構造的可制御のための driver nodes 数 [Liu et al. 2011] ランダムなネットワーク スケールフリーネットワーク ⇒ γ<2 の場合、多くの driver nodes が必要 n: ネットワークの頂点数

12 最小支配集合（MDS）

13 最小支配集合 （１） VD が無向グラフ G(V,E) の支配集合（dominating set） ⇔ (∀v∈V)（v ∈VD∨(∃u∈VD)({u,v}∈E)) 最小支配集合（MDS: minimum dominating set）: 要素数最小の支配集合

14 最小支配集合 （２） NP困難であるが、線形計画法＋分枝限定法に基づく実用的ソフトが存在 人工ネットワークの設計・制御への既存応用
mobile ad-hoc networks (MANET) transportation routing computer communication networks

15 MDSと可制御性の関係 定理. [Nacher & Akutsu, 2012] ネットワークの各辺は両方向性であり、MDSの各頂点はすべての接続辺を個別に制御可能であると仮定。すると、MDSを driver nodes として選択すれば、システムは構造的可制御。

16 MDSサイズの理論解析

17 解析結果 （近似的な解析） γ>2 上限: trivially O(n) 下限: O(n) (to be shown) γ<2
解析結果　（近似的な解析） γ>2 上限: trivially O(n) 下限: O(n) (to be shown) γ<2 上限: O(n1-(2-γ)(γ-1)) 下限: ?

18 γ>2 の時の下限 （１） 次数分布がαk-γに従うとして、 以下のようにαを決定
γ>2 の時の下限 （１） 次数分布がαk-γに従うとして、 以下のようにαを決定 C(S) をS と V-S の間の辺の集合とすると、 |S|+|C(S)|<n であれば、 S は支配集合でない S として次数 K 以上の頂点をすべて選ぶと

19 γ>2 の時の下限 （２） |S|<n/2 を仮定できるので、 よって、 |S| の下限は以下のように見積もれる
γ>2 の時の下限 （２） |S|<n/2　を仮定できるので、 よって、 |S| の下限は以下のように見積もれる これは γ についての増加関数になっている

20 γ<2 の場合の上限の解析 (1) 次数 K=nβ 以上の頂点集合を DS とする その頂点数NDS は、 一方、辺の総数 EG は、
γ<2 の場合の上限の解析 (1) 次数 K=nβ 以上の頂点集合を DS　とする その頂点数NDS は、 一方、辺の総数 EG は、 EDS (=DSに接続する辺の個数) は、 よって、任意に選んだ辺が DS に接続しない確率は、

21 γ<2 の場合の上限の解析 (2) DSに接続しない辺があると、その頂点がDSにカバーされない可能性　⇒ DSにカバーされない頂点数の期待値 (NG-DS) は次式以下 NG-DS と NDS をバランスさせると より、β=2-γ を得る よって、MDS の上限は この式は 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.

22 γ<2の時の説明 次数 nβ 以上の頂点数 そこから出る辺でカバー されない頂点数 以下を満たす β を選ぶ MDSのサイズ ≥nβ

23 生物情報ネットワーク解析への応用

24 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]

25 タンパク質相互作用ネットワーク解析への応用
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]

26 MDSの拡張

27 二部グラフ構造を持つネットワークの制御 多くのネットワークは二部グラフ構造を持つ 薬剤・標的、研究者・共著論文、遺伝子・疾患ネットワークなど
左側頂点のみが制御頂点となる MDSは常にLiuらの手法以下の頂点数を与える [Nacher & Akutsu: Sci. Rep. 2013]

28 必須・冗長頂点の計算 Jiaらにより提案された必須および冗長頂点 [Jia et al.: Nat. Comm. 2013] の概念をMDSに適用（⇐MDSは一意とは限らない） 必須頂点: すべてのMDSにおいて出現 冗長頂点: どのMDSにも出現しない 必須頂点は単なるMDS頂点より重要性が高いと考えられる [Nacher & Akutsu: J. Comp. Net. 2015]

29 ロバストMDS ロバストMDS (RMDS): 各頂点がC個以上の頂点によりカバーされる (C=1 ⇒ MDS)
RMDSサイズは最小次数が D-C+1のMDSサイズとオーダーが一致 [Nacher & Akutsu: PRE, 2015]

30 Molnarらによる研究 次数カットとMDSサイズの関連性 [Sci. Rep. 2013]

31 結論

32 既存結果と矛盾しない理由 Liu et al. 提案手法（MDS法） Driver node の値のみが制御可能と仮定
⇒ 次数 k の頂点は、k 個の driver nodes に相当

33 結論 γ<2 であれば、MDSのサイズは小さい(o(n)) ⇒ 非一様性の高いネットワーク（heterogeneous network）は制御が比較的容易 その傾向をシミュレーション解析およびデータベース解析により検証 人工ネットワーク(e.g., mobile networks and computer networks) では接続辺の個別な制御が可能であると思われるので、この結果が有効である可能性 しかし、生体内ネットワークではその仮定が成立しない 今後の課題 生体内ネットワークの制御を容易とする理論的枠組みの構築 MDSサイズのより精緻な解析