復雜系統重構*

張海峰 王文旭

1)(安徽大學數學科學學院,合肥 230601)

2)(北京師范大學系統科學學院,認知神經科學與學習國家重點實驗室,IDG/麥戈文腦研究院,北京 100875)

遠離平衡態的開放復雜系統遍及自然、社會和技術領域,是復雜性科學的主要研究對象.通過與外界的能量和物質交換,復雜系統通過自組織形成了多種多樣的內在結構、秩序和規律,對認識和預測復雜系統提出了艱巨的挑戰.隨著實驗技術的提高和科技的進步,反映和體現各種復雜系統機理的數據呈指數增長,為研究復雜系統提供了新的機遇.通過系統行為表象數據,揭示復雜系統結構和動力學屬于物理領域的反問題,是認識復雜系統的基礎,是預測系統狀態演化的前提,對于實現系統狀態的調控必不可少.然而,復雜系統的多樣性和復雜性給解決這一反問題造成了極大的困難.因此,需要開闊思路,借助多學科的交叉與融合,充分挖掘數據中隱藏的知識和深層次機理.本文綜述了近年來復雜系統,特別是復雜結構重構和推斷方面的研究成果,希望能夠啟發復雜系統反問題方面的創新.同時,也希望呼吁各領域學者都能關注復雜系統反問題,推動自然、社會、經濟、生物、科技領域的交叉與融合,解決大家共同面對的科學問題.

1 引 言

小到微生物群落,大到宇宙星系,現實世界中的大部分系統屬于遠離平衡態的開放復雜系統.這些系統通過與外界進行物質與能量的交換,對抗內部熵的增加,從而形成耗散結構和自組織現象,這是復雜系統自發產生秩序和復雜性的根源[1].與近平衡態不同,在遠離平衡態的系統中,由于存在漲落決定的分叉和相變,系統中的規律由特定的作用機制決定,因此,沒有統一的定律,這是統計物理與復雜系統領域所面對的最大挑戰[1].BZ化學振蕩反應是典型的遠離平衡態的物質獲得新特性的例子,表現出了遠離平衡態條件下的長程相關性[2].生物系統也是一大類遠離平衡態的穩定系統.通過從外界吸收能量和物質,生物系統維持其內部各種各樣的非平衡狀態和有序結構[3],并且受到自然選擇等競爭的作用,形成了地球上極大的生物多樣性和復雜的生態環境[4,5].

另一方面,低維確定性混沌[6]的發現和元胞自動機[7]的出現,從根本上改變了人們對復雜性的認識: 確定性的低維非線性系統也可以產生不可預測的復雜性[8].復雜可以源于簡單和復雜性的涌現導致傳統還原論的局限性[9],迫切需要統計物理發展適用于復雜系統的理論與方法.美國圣塔菲(Santa Fe)研究所在這一歷史背景下應運而生,旨在通過多學科的交叉與融合,研究各種復雜系統的內在機理和演化規律等跨學科問題.此后,由于計算機技術的發展和大量數據的產生,關于復雜系統的研究成果呈指數律增長[10,11].

復雜系統具備一些普遍的特征和產生復雜性的因素,主要包括單元(個體)動力學復雜、相互作用結構和模式復雜和自適應演化等.從基因到人腦,不同層次和尺度的生物系統都具有高度的復雜性.細胞受到基因和微環境的共同影響,表現出協作、分裂、凋亡、融合、遷移、突變等復雜行為[12].人的復雜行為源于人腦的復雜性和高級認知功能.但是,人并不具有經濟學中的完美理性.人的決策受到各種認知偏見、刻板印象和群體規范的影響.對人類經濟決策行為的深入研究催生了行為經濟學[13],旨在通過實驗和數據分析發現人類有限理性經濟行為的內在動機和成因.對于復雜相互作用結構的研究催生了復雜網絡這一研究方向[14].相關研究揭示了復雜系統共有的結構特征,比如小世界效應、層次結構、社團結構、異質性和多樣性等[15].研究復雜結構如何影響其上的動力學對于理解同步、傳播、級聯失效、合作、協同、集群等群體行為有重要科學價值[16,17];同時,網絡社團檢測方法、網絡控制方法、結構推斷和相變等方法對傳統方法進行了拓展[18,19].與此同時,研究人員逐漸認識到網絡結構本身作用的局限性.事實上,復雜系統的動力學和群體行為由個體、相互作用模式、相互作用結構和環境共同決定.復雜系統研究需要與相關學科緊密結合,才能真正打破學科壁壘和促進學科的交叉與融合,為深入理解社會、經濟、金融和生物復雜性提供有效的理論工具和方法.

遠離平衡態的開放復雜系統的耗散結構、自組織有序性和依賴于特定機制的規律,為認識和預測復雜系統的狀態演化提出了艱巨的挑戰.由于實驗技術的提高和科技的發展,反映和體現復雜系統現象和機制的數據呈指數增加,為研究復雜系統提供了新的基礎和肥沃的土壤.通過復雜系統行為表象數據,重構和推斷復雜系統的結構和動力學,屬于物理科學中的反問題.重構和推斷復雜系統是復雜性研究的基礎,是通過動力學建模預測系統演化的前提,是有效調控系統狀態的必要條件.但是,由于復雜系統機制多樣性、表象的復雜性、動態適應性和極大的隨機性等因素,通過可獲得的數據解決復雜系統的反問題比研究正問題難度更大,需要開闊思路,借助多學科知識的交叉與融合,針對各類復雜系統的特性,提出有效的復雜系統重構理論與方法.本文將綜述近年來復雜系統,特別是復雜網絡結構重構方向的代表性成果,包括基于壓縮感知的重構方法、基于微擾響應的推斷方法等.希望能夠啟發相關的后續研究,特別是與近些年興起的機器學習和人工神經網絡方法的結合.21世紀是復雜的世紀,而復雜系統重構和推斷方法是研究復雜現象的基礎,因此,有不可替代的重要意義.我們也希望通過本文呼吁各領域的學者都能夠關注復雜系統重構問題,集思廣益,推動多學科的交叉與融合,在學科邊界產生原始創新.這是統計物理與復雜系統領域新的機遇和挑戰.

網絡重構(network reconstruction),又稱網絡推斷(network inference),研究的是基于觀測的數據(如圖1(a)和圖1(b))去推斷節點之間的連邊關系[20?23](如圖 1(c)).一個復雜的系統,其個體的動力學行為不僅僅只取決于個體本身,還依賴于和其他個體之間的交互,這些交互就構成了系統的結構,個體之間的交互形成了網絡.因此,網絡重構問題本質上屬于數據驅動的系統辨識范疇[24],是對哪些個體之間存在交互的辨識.但鑒于網絡結構的復雜性、網絡節點動力學的非線性以及結構的稀疏性等性質[25],一方面需要我們發展系統辨識中的一些經典方法,如極大似然估計的方法,另一方面,需要根據問題的特有屬性提出一些新的方法,如根據網絡規模大而稀疏的特點,我們提出了基于壓縮感知的推斷方法等.以下將對近些年在網絡重構方面取得的研究進展進行部分總結與展望.

圖1 網絡重構示意圖(a)通過離散的數據;(b)連續的數據;(c)推斷網絡結構Fig.1.Illustration of network reconstruction:(a)By using the discrete data;(b)the continuous data;(c)reconstruct network.

2 基于壓縮感知的網絡重構方法

2.1 壓縮感知理論

壓縮感知理論是在信號稀疏的情況下,通過少量的數據采集可以重構原始信號[26].給定一個測量矩陣 A ∈RM×N,以及觀測值 Y ∈RM,可以通過下面公式來重構信號 X ∈RN:

壓縮感知的思想是當X是稀疏的時候,只需要少量的觀察數據(M ?N)即可重構X.可以通過求解下述凸優化問題[26?30]準確得到稀疏信號X:

上述問題已經證明了是NP-hard.但是在一定條件下最小L1范數下的結果是等價于最小L0范數結果的,所以有

(3)式是一個凸優化問題,已有很成熟的算法作為參考[27?30].因為網絡數據具有天然的稀疏性,所以可以通過壓縮感知的方法對其進行網絡重構.如圖2所示,就是利用壓縮感知方法重構出Karate網絡的第4個節點的鄰居,可以看到求出的X(顏色越偏向藍色,其值越接近0)反映了第4個節點的鄰居結構.

2.2 基于耦合振子系統的網絡重構

由于描述物理網絡中的動力學函數未知,可以應用冪級數來表示.又因為級數的高階項比較多,因此估計其系數非常困難.考慮到這些系數非零項很少,比較稀疏,而且網絡的結構也是稀疏的.所以可以通過少量的觀察數據應用壓縮感知的方法重構網絡[31].

一個復雜的振子網絡可以通過下面節點動力學描述:

其中 xi∈RD是 節點的狀態量,fi(xi)為節點自身動力學,函數形式未知,Cij是節點i與j的耦合矩陣:

圖2 基于壓縮感知方法重構Karate網絡中4號節點的鄰居(重構方法見2.4節)Fig.2.Reconstructing of node 4 in the Karate network based on compressive sensing framework(the reconstruction method is introduced in Subsec.2.4).

則其第k個分量可以用n以下的冪級數的形式表示:

其中(xi)k表示第i個體狀態的第k個分量,可以通過數據觀察得到.[(αi)k]l1,···lD為冪級數的系數,是未知量.可以看出(7)式關于未知量是線性的.給定一個時刻 tm,根據(4)式與(7)式有

2.3 基于演化博弈系統的網絡重構

在生物、社會科學和經濟學中的許多復雜動力系統都可以用演化博弈建立數學模型[33].在演化博弈試驗中,每一個人可以處于兩種狀態:合作與背叛,分別可以表示為 S(C)=[1,0]T與S(D)=[0,1]T,博弈中雙方收益是由博弈雙方的策略,以及收益矩陣 P (在囚徒困境博弈[34]中決定.所以第i節點的收益為

進行M輪演化博弈實驗,收集每個人狀態與收益,即有M個線性方程:

式中只有 aij為未知量.所以上述公式可以寫成以下形式:

其 中Ai=[ai1,···,ai,i-1,ai,i+1,···,aiN]T,Gi與Pi已知.應用壓縮感知理論即可求解 Ai,從而揭示網絡的結構[35?37],該方法也可以推廣到加權網絡.

2.4 基于二值動力學系統的網絡重構

二值動力學是復雜系統中常見的一種動力學形式[38?41],如疾病傳播動力學中的感染態與易感態、演化博弈中的背叛與合作、Ising動力學中的自旋向上和自旋向下等等.對于疾病傳播動力學,可以應用SIS(susceptible-infected-susceptible)模型或CP(contact process)模型來模擬其傳播過程.文獻[42]應用壓縮感知的方法給出了詳細的重構過程.這里只簡單介紹SIS模型的重構方法.

兩邊取對數有

通過一些方法[42]在時間序列中統計出以及構造M個線性方程,類似

其中

Xi與Yi已知.應用壓縮感知理論即可求解 Ai,從而揭示網絡的結構[42].

當二值動力學未知的情況,可以記兩種狀態分別為激活態與未激活態,假設一個個體i由未激活變為激活態的概率與處于激活態鄰居的個數有關,對其線性化[43]:

類似地,通過一些方法[43],在時間序列中統計出構造 M個線性方程,可以寫成(15)式的形式,進而通過壓縮感知進行求解,也可以通過Lasso進行求解[43].

壓縮感知在動力學系統重構與網絡重構的應用還有很多,如Wang等[44]利用壓縮感知可以重構非線性動力學系統;Su等[45]利用壓縮感知重構具有空間地理信息的網絡,不僅可以重構網絡結構還可以得到每個節點所在的地理位置;Su等[46]還通過外部事件序列,利用壓縮感知探測隱藏節點;Tang等[47]通過交通流量數據,利用壓縮感知對交通網絡進行重構;Chen和Lai[48]通過玻爾茲曼機對動力學進行估計,然后應用壓縮感知方法重構網絡;最近壓縮感知方法還被推廣到了多層網絡[49?51]、加權網絡的重構[52]等.

3 重構非線性動力學系統網絡

對于連續的非線性動力學系統,一般情況下,N個節點的網絡動力學可以由以下常微分方程描述:

3.1 直接方法

給定網絡動力學:

當其中的內部動力學與耦合函數已知的情況下,可以通過記錄時間序列中不同時刻的數據,以此來重構網絡[53].第i個體的第d維動力學公式可以表示為

如果可以觀察M個時刻,將會構造M個線性方程:

寫成矩陣形式為

3.2 自適應同步方法

在動力學網絡中的局部動力學與耦合函數已知的情況下,可以根據原系統復制一個輔助系統,然后通過不停迭代輔助系統中的網絡結構使得復制系統與原系統同步.則得到的輔助系統中的網絡結構就是我們要重構的原始系統的結構[55].考慮一個系統(以一維為例):

假設 fi與gj滿足利普希茨連續條件.給原始系統一個副本:

其中 yi表 示復制系統的狀態,Kij表示復制系統的耦合強度,Ii為可控制信號.根據原系統和復制系統的狀態,可以通過不停迭代 Ii與Kij使得原系統與復制系統同步.定義同步誤差為

副本中的耦合強度調整為

可控信號設置為 Ii=-αei.在這里 γij＞0,α ＞0 .文獻[55]中證明了當 α 足夠大的情況下,兩個系統的誤差隨著時間減少,最終會收斂到同步狀態.此時復制系統的拓撲結構與原系統的拓撲結構相同,即以此重構網絡的局部結構.

對于自適應同步的方法,Zhou和Lu[56]把該方法推廣到了加權網絡;Liu等[57]將這一方法推廣到了含有耦合延遲的非自治復雜網絡的拓撲識別;更進一步,Wu等[58]利用該方法研究了含時變耦合延遲和受隨機擾動影響下的網絡重構;Zhao等[59]把這一方法推廣到了多層網絡,等等[60?64].

3.3 驅動-響應實驗

上述方法都需要在已知節點的局部動力學以及耦合函數情況下重構網絡結構,下面將介紹一些在節點的局部動力學和耦合函數未知情況下的網絡重構方法.

如果一個系統存在一個穩態,當給系統一個微弱的、持續的擾動,這個系統將趨向另外一個穩態,且與第一個穩態相似.兩個穩態的差異不僅取決于驅動信號,而且與網絡的拓撲結構有關(如圖3所示).因此可以通過多次不同的驅動-響應實驗,以此重構整個網絡結構.

圖3 驅動-響應實驗示意圖.對穩態系統施加(穩態是一個穩定點(a),或者一個周期軌道(b))一個持續驅動I,系統達到另外一個穩態.兩個穩態的差異v包含了網絡的拓撲結構Fig.3.Driving-response experiments.System is shifted from one stable state(the stable state is a fixed point(a),or a periodical trajectory(b))to another position by input a driving signal I.The difference of the trajectories contains information about the topology.

這種方法首先是為了解決生物網絡上拓撲識別,特別是基因調控網絡[65?67],其動力學一般可以應用非線性動力系統描述.當系統趨于穩態時,這種系統可以近似為一個一階線性微分方程:

其中 xi表示第i個RNA、蛋白質或代謝物的濃度;和前面一樣,反 映網絡的拓撲結構,Ii(t)表示外部的擾動.當給定一個持續的微弱的擾動Ii(t)=Ii,m,系統將趨向一個新的穩態當對每個個體都進行M次擾動實驗,會得到一個線性方程組:

通過求解此線性方程組即可推斷網絡的結構.對于每個個體i都可以構造類似以下方程組:

上述描述的系統穩態是趨向一個不動點,然而在自然界還存在更多、更復雜的系統.而另外一種簡單的系統,是穩態趨向一個周期軌道,它經常以耦合振子的極限環形式出現.對于此系統,也可以應用對穩態系統微小地、持續地擾動來實現網絡重構[68].網絡動力學可以給定:

其中 φi(t)表 示振蕩器 i的相位,ωi(t)表示振蕩器i的頻率;和前面一樣,Jij反映網絡的拓撲結構,Ii,m表示持續的外部擾動.當外部沒有驅動時,m=0,此時 Ii,0=0 .

對于驅動 Ii,m,考慮穩態上面的鎖相吸引子,相位差可以表示為

當對原始系統(Ii,0)的擾動(Ii,m)是微小的,則會有

給定一個微小驅動 Ii,m,集體的頻率可以觀察:

令

對 gij在 Δij,0處進行線性展開可以得到包含拓撲結構 Jij的線性方程[68],當給定許多次擾動的情況下可以得到類似(28)式的線性方程組,求解即可推斷網絡的拓撲結構.

上述兩個方法都是在系統的穩態附近進行微小擾動,下面將介紹一種將系統驅動到一個已知不動點以此重構網絡的方法[69,70].考慮一個動力學網絡:

參數如上述描述.給定該系統一個持續的驅動:

當 θ 足夠大,且 fi與gij滿足利普希茨連續條件時,該系統會被驅動到一個穩定點: xs=[x1,s,x2,s,···,xN,s]T,它接近于即有

定義:

則有

于是可以寫成

3.4 基于噪音的方法

當一個動力學網絡趨向同步時,在沒有外部擾動的情況下,整個系統的每個個體狀態一致,它們之間有效的相互作用消失,從而無法提取其中的結構信息.但是,噪聲會導致去同步化,可以在時間序列中包含個體之間潛在的交互信息[21].

因此可以通過噪聲的擾動來揭示網絡的結構[71?74].考慮一個動力學網絡:

4 似然估計的方法重構網絡

對于二值動力學,當給定動力學過程以及網絡,會得到一系列時間序列.但是,當網絡結構未知,給定時間序列以后,就變成了什么樣的網絡結構最有可能產生這種時間序列,即應用最大似然估計的方法即可以得到[75?81].

對于二值動力學,假設一個節點由未激活態(t時刻)變為激活態(t + 1時刻)只受激活態的鄰居的影響,通過貝葉斯公式,有

5 其他方法

網絡重構的方法還有很多,例如,Wu等[82,83]將格蘭杰因果關系檢驗運用到了網絡重構當中,并針對不同的情況,提出了傳統格蘭杰因果關系檢驗、條件格蘭杰因果關系檢驗、分段格蘭杰因果關系檢驗、隨機擾動分段格蘭杰因果關系檢驗、偏相關格蘭杰因果關系檢驗等不同的格蘭杰因果關系檢驗識別方法;Li和Li[84]通過時效網絡擴散過程的到達時間數據,提取時效交互過程的統計特征和推斷出時效網絡的拓撲結構,并嚴格證明了推斷結構的漸近一致性;Casadiego等[85]通過引入顯式依賴矩陣把每個個體的動力學分解成與其他個體兩點、三點或更高階的相互作用,從而可以通過數據揭示網絡(兩點)和超網絡(三點)的交互作用.

圖4 EM算法推斷Karate網絡33號節點的結構(a)網絡結構;(b)二進制數據;(c)EM算法推斷出節點33的結構;(d)真實網絡33號節點的結構Fig.4.Reconstructing the neighbors of node 33 in Karate network:(a)The real structure of the Karate network;(b)the binary state data;(c)inferring the neighbors of node 33 based on EM algorithm;(d)the real neighbors of node 33.

6 未來展望

網絡重構發展到現在,雖然已經取得了一些成就,但是還有很多問題需要解決.現有的方法主要還是針對簡單的動力學網絡.對于多層網絡的重構、符號網絡的重構、時效網絡的重構、多體動力學網絡的重構等等,雖然有一些文獻已經對這些問題有所涉及,但是其重要性還沒有受到應有的關注,也沒有很好地解決.而且現在的網絡重構針對的主要還是小規模網絡,如何快速地、精確地重構大規模網絡也是以后需要解決的問題.