復雜網絡的可控性

1、復雜網絡的可控性已有2783次閱讀2011-6-13 22:34 |個人分類:復雜網絡|系統(tǒng)分類:科研筆記|關鍵詞:復雜網絡前不久，nature上發(fā)表了一篇關于研究復雜網絡的可控性的文章。這篇文章結合了工程控 制論的思想和復雜網絡的研究，開辟了一種幫助我們進一步理解復雜系統(tǒng)的新方法（這是文 章自己的說法，但是關于有向網絡的可控性研究，據我所知，在2010年就已經有人研究過 了）。復雜系統(tǒng)涉及多個組分（如基因調控過程中的基因、蛋白質等分子，或者社交網絡中的 人物賬號等）和這些組分之間的關系。一般的建模方法，如常微分方程等，由于受限于計算 能力或者是建模對象本身的模糊性，已經不能對這種大規(guī)模的復雜

2、系統(tǒng)進行建模。而復雜網 絡是對復雜系統(tǒng)建模的一種有效的方法。復雜網絡的節(jié)點表示的是復雜系統(tǒng)中的多個組分的 某種量化性質，如基因調控網絡中基因的激活/抑制狀態(tài)、社交網絡中賬號的狀態(tài)等；復雜 網絡的變表示節(jié)點之間的某種聯系或者是共享某種信息，如基因網絡中AB表示基因 A的產物會促進基因B的表達、社交網絡中CD表示賬號D的動態(tài)會和賬號C共享。我們研究復雜系統(tǒng)的最終目標是希望能對它們進行控制。如基因藥物的靶標選取問題， 選擇哪個基因（基因調控網絡中的節(jié)點）作為藥物的靶標，能使得整個生物系統(tǒng)達到一個我 們期望的狀態(tài)呢？還有社交網絡中，我們選取那個節(jié)點作為信息的發(fā)布點對整個社交網絡產 生我們想要的宣傳效果

3、呢？這些都可以抽象為如何對一個表示狀態(tài)的復雜網絡進行有效地 控制，從而使得整個網絡進入我們期望的狀態(tài)。這篇文章最開始的出發(fā)點是研究復雜有向網絡的可控性。眾所周知，我們若是能對整個 網絡中的每一個節(jié)點輸入一個控制信號，那么整個網絡是可控的。但是對于一個大規(guī)模的復 雜系統(tǒng)，這是很難實現的。作者希望能找到最少的控制節(jié)點（文章中稱為驅動節(jié)點，driver nodes）來有效地控制整個網絡。作者采用的是比較古老的“最大匹配”方法（這是基于將 整個網絡看成一個線性系統(tǒng)的）尋找最小的驅動節(jié)點數ND。并將這種方法用于幾個基于 對象建模的真實網絡和一群ER隨機網絡以及一群度分布和真實網絡相同的隨機 網絡，通過比

4、較得到的最小驅動節(jié)點數，作者發(fā)現最新驅動節(jié)點數主要是由于網 絡的度分布性質確定的。接著作者根據這一發(fā)現以及cavity method推導出了一 組自穩(wěn)定的方程組，度分布為自變量，最小驅動節(jié)點數為所求的結果。這篇文章有兩個研究成果都是與我們預想的結果是相反的，一是復雜網絡中 的驅動節(jié)點一般不是網絡的hub；二是稀疏的異質網絡是最難控制的而致密的同 質網絡是比較容易控制的。這篇文章的研究還發(fā)現我們本以為難以控制的具有個 體獨立性的社交網絡相比于其他的網絡模型，如基因調控網絡等，卻是相對比較 容易控制的。這篇文章的成果是顯著的，但是如何將文中的理論用于實際，如何將研究框 架擴展到非線性系統(tǒng)。這仍是有

5、待我們的研究的。 HYPERLINK http:/www.nature.eom/nature/journal/v473/n7346/full/nature10011.html%23/comments http:/www.nature.eom/nature/journal/v473/n7346/full/nature10011.html#/comments前不久，我寫過一篇關于我研讀nature上發(fā)表的“Controllability of Complex Network”的文章( HYPERLINK /home.php?mod=space&uid=545746&do=blog&id= /hom

6、e.php?mod=space&uid=545746&do=blog&id= 454884 )。當時只是自己感性上覺得這篇文章很有用，會對將來各種復雜網絡的 研究產生較大的影響。但由于暫時我還沒有看到相關的重要的后續(xù)研究出現，對 于其是否將產生比較重大的影響，我還有些懷疑。今天在Science上看到了一篇關于這篇文章的一篇評論 HYPERLINK /content/332/6031/777.full /content/332/6031/777.full我不禁感覺這條路前面的燈亮了。有一些專家學者都認為Yang-Yu Liu等人 的工作是非常重要的：香港城市大學的Guanrong Chen認為：

7、實際中大部分網絡 都是有向網絡，相比以前人們對無向網絡的研究，這項工作比以往的網絡控制研 究都更具有通用型和實際價值，尋找driver nodes的算法是非常重要的，因為 它很有用。 丹麥科技大學的生物學家Rune Linding認為這篇文章的算法可用 于解讀細胞內生化相互作用網絡，如可以作為研究控制激酶磷酸化網絡的框架。 另外此項研究還可用于控制生物機器人，如控制蟲新桿狀線蟲的297個神經細胞 中的49個來對這個生物機器人實現必要的控制。另外這篇文章將泰斗級控制論專家Jean-Jacques Slotine和網絡領軍人物 之一 Barabas聯合在一起，十分給力這條路的后續(xù)發(fā)展。復雜網絡的嚴

8、格可控性一一強悍的特征值又回來了已有1139次閱讀2013-9-27 14:16 |系統(tǒng)分類:論文交流|關鍵詞:網絡，可控性控制一個系統(tǒng)是非線性研究中的一個重要問題。如何控制一個系統(tǒng)呢？首要問題是需 要多少外界信號的輸入，也就是滿足可控性條件的控制器個數問題。然而這是一個很難事先 根據Kalman條件得到的問題，2011年Liu等在Nature上發(fā)表論文Controllability of complex networks，利用最大匹配理論解決了復雜網絡的結構可控性問題。他們提出一個系統(tǒng)結構可控需要的獨立控制器（Driver）為系統(tǒng)非匹配節(jié)點數（完美匹配時為系統(tǒng)任意一個節(jié)點）， 并且Drive

9、r數與網絡度分布存在密切關聯。最近我們在 Nature Communications 上發(fā)表論文 Exact controllability of complex networks，給出了網絡嚴格可控性的相關結論。我們從可控性的PBH條件（與Kalman條 件等價）入手，得到網絡嚴格可控性所需要的Driver數為系統(tǒng)特征值的最大幾何重數；當 系統(tǒng)矩陣可對角化（比如對稱）時，退化為系統(tǒng)特征值的最大代數重數。進一步在分析稀疏 和致密網絡時發(fā)現，稀疏網絡最大幾何重數出現在零特征值上，從而對稀疏網絡就可直接由 系統(tǒng)矩陣的秩來決定Driver數；而對于同權致密網絡，最大幾何重數出現在負權值上，同 樣可直

10、接對同權網絡簡單計算Driver數。仿真實驗說明了對稀疏和致密網絡簡單計算的正 確性，同時發(fā)現同權網絡越致密越難控制（Driver數越大）。0.0000.0040.9961.000WEAt此此cI-1I i II I 1 Tn d 1 ,01.0 -$BA蚱此N=0.0000.0040.9961.00012 3 4Figure 2 Exact ccntrallnbility of undirected networks. Exact controllability rnc?asure as a function of LR random networks Eirid (b) ER rundom

11、 networks with random weights assigned to links (WER)t (c) r?口 v for Newman-Watts small-world networks, (d) nD versus half of the average degree for Barabsi-j undirected and their coupling matrices are symmetric. The data points are obtained from the MM lL equal from 20 independent realtzations. The

12、 curves (SoD) are the theoreticai predictions of equations (5) and ( The representative network sizes used are N= 1,000, 2,000 zind 5,000.另外，我們還可以通過線性代數中初等變換的方法求的網絡需要Driver的節(jié)點。該方法簡單易行，復雜度約為O(N2(logN)A2)。EigenvaluesTransformation-1J016-1.0000-1.0000-100000.00004.7016-1.9032-1.00000.19391.00001.00002.

13、7093糜=0叩性=4AM= LOO歡=-L00叩慚)=3Figure 1 | Illustration of the exact controllability framework to identify n minimum set of drivers, (a) A simple undirected network with self-io ops, (b) a simple directed network and (c) an undirected network with dense connections The matrix A 勺胡 the column canonical

14、form of matrix A by the elementary column transformation, the eigenvalues * and the eigenvalue corresponding to the maximum geometric multiplicity p(zM) of A are given for each simple network. The rows that are linearly dependent on others in the column canonical form are marked by red. The nodes corresponding to them are the drivers that are marked by red as well in the networks. For the undirected networks in and c,叭沖)is equal to the maximum algebraic multiplicity, that is the multiplicity of 2“七 The configuration of drivers is not unique as