理解復(fù)雜系統(tǒng)：從網(wǎng)絡(luò)到最優(yōu)高階模型

Understanding Complex Systems:From Networks to Optimal Higher-Order Models

理解復(fù)雜系統(tǒng)：從網(wǎng)絡(luò)到最優(yōu)高階模型

https://arxiv.org/pdf/1806.05977

摘要

為了更好地理解復(fù)雜系統(tǒng)的結(jié)構(gòu)和功能，研究人員通常用網(wǎng)絡(luò)來表示復(fù)雜系統(tǒng)中組件之間的直接相互作用，假設(shè)遠(yuǎn)距離組件之間的間接影響可以通過路徑來建模。這樣的網(wǎng)絡(luò)模型假設(shè)實際路徑是無記憶的（memoryless）。也就是說，路徑穿過節(jié)點時的延續(xù)方式不取決于它來自哪里。最近對復(fù)雜系統(tǒng)中實際路徑數(shù)據(jù)的研究質(zhì)疑了這一假設(shè)，并指出路徑中的記憶確實對網(wǎng)絡(luò)科學(xué)的核心方法有相當(dāng)大的影響。一個不斷增長的研究社區(qū)致力于所謂的“高階網(wǎng)絡(luò)模型”來解決這個問題，試圖利用傳統(tǒng)網(wǎng)絡(luò)表示所忽視的信息。在這里，我們總結(jié)了該領(lǐng)域的進(jìn)展，并概述了呼吁更多研究的剩余挑戰(zhàn)。

統(tǒng)計物理學(xué)的一個長期目標(biāo)是理解由大量相互作用組件組成的復(fù)雜系統(tǒng)中的涌現(xiàn)現(xiàn)象。這類系統(tǒng)不僅出現(xiàn)在凝聚態(tài)物理學(xué)中，而且廣泛存在于其他學(xué)科，物理學(xué)家已經(jīng)能夠為更好地理解生物、社會、經(jīng)濟和技術(shù)系統(tǒng)做出貢獻(xiàn)。復(fù)雜系統(tǒng)的一個顯著特征是，所有系統(tǒng)組件都可以相互影響，無論是直接還是間接。對于那些這些相互作用的拓?fù)浣Y(jié)構(gòu)未知的系統(tǒng)，通常使用平均場方法（mean-field approaches）進(jìn)行研究，該方法用單個平均場總結(jié)所有元素之間的相互作用。在過去的幾十年里，數(shù)據(jù)的激增表明，現(xiàn)實世界中的復(fù)雜系統(tǒng)表現(xiàn)出稀疏且復(fù)雜的拓?fù)浣Y(jié)構(gòu)，其中很少有組件直接相互作用，而大多數(shù)組件通過多個直接相互作用的序列間接相互影響 [1]。

在簡要介紹高階網(wǎng)絡(luò)模型框架之后，這篇進(jìn)展文章通過提問提供了高階網(wǎng)絡(luò)模型為它們所代表的系統(tǒng)提供新的和關(guān)鍵見解的例子：復(fù)雜系統(tǒng)中的路徑結(jié)構(gòu)如何影響流行網(wǎng)絡(luò)科學(xué)方法的適用性？高階網(wǎng)絡(luò)模型如何幫助我們提高對復(fù)雜系統(tǒng)的理解？哪些復(fù)雜系統(tǒng)需要高階建模技術(shù)？具體來說，我們結(jié)合網(wǎng)絡(luò)科學(xué)的三個基礎(chǔ)領(lǐng)域來回答這些問題：社區(qū)檢測、節(jié)點排名和動態(tài)過程建模。答案既提出了挑戰(zhàn)，也為開發(fā)新的數(shù)據(jù)驅(qū)動建模技術(shù)以更好地理解復(fù)雜系統(tǒng)提供了機遇。

復(fù)雜系統(tǒng)中的高階相互作用模型

由于研究的系統(tǒng)和數(shù)據(jù)不同，致力于高階網(wǎng)絡(luò)模型的成長中的社區(qū)采取了多管齊下的方法：一股工作流建立在許多系統(tǒng)表現(xiàn)出多體相互作用（many-body interactions）的觀察之上，這需要將連邊推廣到捕捉不僅僅是成對相互作用的高階模型 [19, 20, 21]。例子包括已知是社交網(wǎng)絡(luò)基本構(gòu)建塊的三角形 [22]，科學(xué)合著網(wǎng)絡(luò)中的團（cliques）[23]，生化轉(zhuǎn)錄網(wǎng)絡(luò)中的前饋環(huán)網(wǎng)絡(luò)模體（feed-forward loop network motifs）[24]，以及生態(tài)系統(tǒng)中物種間的空間共存關(guān)系 [25]，以及基因調(diào)控網(wǎng)絡(luò)中的三基因相互作用（trigenic interactions）[26]。另一條研究路線承認(rèn)，許多復(fù)雜系統(tǒng)中的連邊可以是多種類型的，這就要求網(wǎng)絡(luò)模型的多層推廣（multi-layer generalisations）[27, 28]。例子包括多模態(tài)交通系統(tǒng) [29]，電力和通信基礎(chǔ)設(shè)施的相互依賴層 [30]，以及多層金融網(wǎng)絡(luò) [31]。最后，越來越多的高分辨率時間序列數(shù)據(jù)可以用來推斷系統(tǒng)中兩個以上組件之間的相互作用的時間序列或路徑。例子包括學(xué)術(shù)引用網(wǎng)絡(luò)的數(shù)據(jù) [17]，時間戳社交網(wǎng)絡(luò) [32, 32]，以及醫(yī)院網(wǎng)絡(luò)中的患者路徑 [33]，以及交通和信息網(wǎng)絡(luò)中的人類軌跡 [14]。

盡管動機和數(shù)學(xué)基礎(chǔ)不同，這些方法有一個共同點：它們考慮到標(biāo)準(zhǔn)網(wǎng)絡(luò)模型過于簡單，無法解釋在越來越多的關(guān)于生物、技術(shù)、經(jīng)濟和社會系統(tǒng)的豐富數(shù)據(jù)中捕捉到的復(fù)雜影響路徑。圖 1 在時間序列數(shù)據(jù)中說明了這一點。此類數(shù)據(jù)通常提供關(guān)于現(xiàn)實世界路徑的信息，要么直接通過捕捉過程或級聯(lián)影響節(jié)點的一系列相互作用，要么間接通過捕捉可用于推理因果或時間尊重路徑（causal or time-respecting paths）的時間戳連邊 [32]。專注于成對相互作用，一個標(biāo)準(zhǔn)的網(wǎng)絡(luò)模型代表了底層系統(tǒng)的連邊拓?fù)洌▓D 1b）。這種表示丟棄了關(guān)于連邊如何貢獻(xiàn)于路徑的信息，隱含地意味著節(jié)點可以通過以無記憶、馬爾可夫方式遍歷節(jié)點的傳遞路徑間接相互影響。在我們的例子中，節(jié)點 A 和 B 都可以通過四條傳遞路徑

在我們的例子中，節(jié)點 A 和 B 都可以通過四條傳遞路徑
間接影響 D 和 E（圖 1c）。仔細(xì)觀察時間序列數(shù)據(jù)中相互作用的順序揭示（reveals）這四條可能的路徑中只有兩條存在于序列中（圖 1d），從而使假設(shè)傳遞性、馬爾可夫路徑的網(wǎng)絡(luò)分析方法失效。克服這一缺點需要一種以路徑為中心（path-centric）的數(shù)據(jù)視角，將網(wǎng)絡(luò)推廣到路徑的高階模型 [17, 16, 34, 15, 14, 35]。圖 1d 用二階模型說明了這一思想，該模型考慮了長度為二的路徑的拓?fù)洹１局唠A馬爾可夫鏈模型的精神，該模型可以用記憶網(wǎng)絡(luò)（memory network）[17] 來表示，其中狀態(tài)節(jié)點（state nodes）代表二階狀態(tài)空間中的狀態(tài)，連邊編碼狀態(tài)之間可能的轉(zhuǎn)換。取決于路徑的拓?fù)洌鍌€物理節(jié)點（physical nodes）A, B, C, D, 和 E 中的每一個（通常是現(xiàn)實世界中的興趣對象），都有一個或多個狀態(tài)節(jié)點。這些狀態(tài)節(jié)點實現(xiàn)了高效的高階路徑網(wǎng)絡(luò)模型：由狀態(tài)節(jié)點上的馬爾可夫模型描述的路徑（該模型以不依賴于先前訪問過的狀態(tài)節(jié)點的概率將路徑從一個狀態(tài)節(jié)點導(dǎo)向下一個），在物理節(jié)點上表現(xiàn)為非馬爾可夫（non-Markovian）（圖 1f）。這種建模方法可以通過為路徑上當(dāng)前物理節(jié)點之前的 個節(jié)點的每個前綴添加一個狀態(tài)節(jié)點，推廣到任意階數(shù) m m。通過這種方式，我們可以構(gòu)建網(wǎng)絡(luò)模型，以捕捉任何給定階數(shù) m m 的路徑中的高階效應(yīng)。

非馬爾可夫路徑與社區(qū)發(fā)現(xiàn)

社區(qū)發(fā)現(xiàn) [36] 是一個統(tǒng)稱，指代大量將節(jié)點分組為模塊以簡化并突顯網(wǎng)絡(luò)拓?fù)渲谢窘Y(jié)構(gòu)的算法。由于高階表示可以捕捉更復(fù)雜的相互作用形式，推廣到高階表示的社區(qū)發(fā)現(xiàn)算法能夠捕捉更復(fù)雜的關(guān)系規(guī)律形式。例如，對于具有長流持續(xù)時間的期刊和社區(qū)之間的引用流，一個標(biāo)準(zhǔn)的網(wǎng)絡(luò)模型（其期刊之間的加權(quán)有向連邊是根據(jù)文章之間的引用聚合而成的）無法捕捉通過像《自然》（Nature）這樣的多學(xué)科期刊的復(fù)雜引用流（圖 2a,c）[17]。無論流來自哪里，它們都會按照該期刊在所有發(fā)表于該多學(xué)科期刊的文章中被引用的數(shù)量比例，繼續(xù)流向另一個期刊。因此，來自不同領(lǐng)域的引用流以一種不現(xiàn)實的方式混合并從的一個領(lǐng)域移動到另一個領(lǐng)域。例如，圖 2c 說明了來自兩個微生物學(xué)期刊的大多數(shù)引用流如何繼續(xù)流向兩個植物科學(xué)期刊，以至于所有這些期刊最好被分配到同一個領(lǐng)域。因此，基于標(biāo)準(zhǔn)網(wǎng)絡(luò)模型的社區(qū)發(fā)現(xiàn)可能會模糊模塊之間的邊界，并且無法將節(jié)點分配到多個重疊的模塊中。

相比之下，引用流的二階馬爾可夫表示考慮了引用來自哪里，捕捉到了這樣一個事實：大多數(shù)從某一領(lǐng)域流向《自然》的引用流會返回到同一個領(lǐng)域（圖 2b,d）。例如，當(dāng)從一階馬爾可夫表示轉(zhuǎn)向二階馬爾可夫表示時，所有期刊平均而言，經(jīng)過兩步后返回同一期刊的引用流的相對數(shù)量從 11% 增加到 22% [17]。此外，那些不返回的引用流以更現(xiàn)實的方式移動：圖 2b 和 d 說明了微生物學(xué)中的《微生物學(xué)雜志》（Journal of Microbiology）和《細(xì)菌學(xué)雜志》（Journal of Bacteriology）的引用流如何主要返回到這兩個期刊中的任何一個，同樣地，植物科學(xué)中的《植物細(xì)胞》（Plant Cell）和《植物生理學(xué)》（Plant Physiology）的引用流如何主要返回到那些期刊。因此，引用流保持在各自的領(lǐng)域內(nèi)，突顯了《自然》期刊的多學(xué)科特征。將多學(xué)科期刊的狀態(tài)節(jié)點分配到不同的領(lǐng)域，能更好地捕捉二階馬爾可夫表示中的引用流。通過這種方式，非馬爾可夫引用路徑的二階表示對于捕捉多學(xué)科期刊中重疊的研究領(lǐng)域至關(guān)重要。

非馬爾可夫路徑與節(jié)點中心性

開發(fā)識別重要節(jié)點的算法是網(wǎng)絡(luò)科學(xué)的主要成功故事之一。它們幫助我們在網(wǎng)絡(luò)基礎(chǔ)設(shè)施中定位關(guān)鍵元素，在社會系統(tǒng)中識別有影響力的行動者，或在萬維網(wǎng)中找到相關(guān)頁面。這些應(yīng)用的核心是節(jié)點中心性（centrality of nodes）的度量，例如，利用它們在其他節(jié)點之間最短路徑上的出現(xiàn)、在流動過程中的作用，或?qū)討B(tài)過程穩(wěn)態(tài)的影響 [1, 37, 38]。這些方法假設(shè)節(jié)點中心性可以基于系統(tǒng)組件之間成對相互作用的拓?fù)浣Y(jié)構(gòu)來表征。然而，在社會系統(tǒng)中，信息是通過受上下文、偏好和時間影響的特定路徑共享的，僅基于網(wǎng)絡(luò)拓?fù)涫菬o法理解的。同樣，超鏈接的拓?fù)浣Y(jié)構(gòu)不足以解釋人類瀏覽萬維網(wǎng)的復(fù)雜路徑。在生物系統(tǒng)中，細(xì)胞內(nèi)成對相互作用的拓?fù)浣Y(jié)構(gòu)幾乎不足以理解蛋白質(zhì)、神經(jīng)元或基因相互影響的復(fù)雜路徑。

為了真正捕捉節(jié)點的重要性，我們必須超越網(wǎng)絡(luò)模型，并考慮高維、時間分辨數(shù)據(jù)中路徑的復(fù)雜結(jié)構(gòu)。圖 3 展示了一個例子，該例子基于主要開源軟件社區(qū)開發(fā)者之間的時間戳社交互動。這些互動的網(wǎng)絡(luò)模型（圖 3a）允許我們估計節(jié)點的重要性，例如，使用介數(shù)中心性（betweenness centrality），這是一種如果其他節(jié)點對之間的許多最短路徑通過節(jié)點 v v，則賦予節(jié)點 v v 高中心性的度量。由此產(chǎn)生的節(jié)點中心性由圖 3a（底部）中的節(jié)點大小表示，表明節(jié)點 32 是系統(tǒng)中最重要的節(jié)點。

非馬爾可夫路徑與動態(tài)過程

除了使我們能夠推理諸如社區(qū)結(jié)構(gòu)或節(jié)點中心性等拓?fù)涮卣髦猓W(wǎng)絡(luò)科學(xué)還增進(jìn)了我們對系統(tǒng)拓?fù)淙绾斡绊憚討B(tài)過程，進(jìn)而影響系統(tǒng)功能的理解。這項研究大多基于對線性（或可線性化）動態(tài)系統(tǒng)的解析研究，在這些系統(tǒng)中，拉普拉斯矩陣、鄰接矩陣或轉(zhuǎn)移矩陣編碼了系統(tǒng)元素之間直接相互作用的拓?fù)浣Y(jié)構(gòu)。事實上，這使我們能夠以與連續(xù)空間中非常相似的方式處理網(wǎng)絡(luò)中的過程——利用像拉普拉斯矩陣這樣的線性算子將微分算子推廣到任意離散相互作用拓?fù)洹@對物理學(xué)家自然具有吸引力。這些矩陣算子的特征值和特征向量捕捉了系統(tǒng)拓?fù)溆绊憯U散和傳播過程效率的方式，無論它是增強還是減弱動態(tài)系統(tǒng)的穩(wěn)定性，以及它是阻礙還是促進(jìn)集體動力學(xué)。

雖然這為聯(lián)系復(fù)雜系統(tǒng)的結(jié)構(gòu)和動力學(xué)提供了強有力的工具，但代數(shù)方法的應(yīng)用隱含引入的傳遞性、馬爾可夫路徑假設(shè)在許多現(xiàn)實系統(tǒng)中是不合理的。圖 4a 說明了這樣一個復(fù)雜系統(tǒng)的例子，它展示了倫敦地鐵（London Tube）的網(wǎng)絡(luò)模型，其中節(jié)點是火車站，連邊捕捉了車站之間的直達(dá)火車連接。為了理解該交通網(wǎng)絡(luò)的拓?fù)淙绾斡绊懫湫屎汪敯粜裕芯科鋵討B(tài)過程的影響是很常見的。作為一個簡單的例子，讓我們考慮一個離散時間模型，該模型捕捉從時間在單個車站開始旅程的乘客的擴散，每個離散時間步移動一個車站。我們進(jìn)一步根據(jù)倫敦地鐵站之間平均客流量的數(shù)據(jù)調(diào)整每位乘客穿越給定連邊的概率，使其更有可能通過高客流量的連邊繼續(xù)行進(jìn)。圖 4b 中的流程圖顯示了該過程的前五個步驟。假設(shè)傳遞性、馬爾可夫路徑，該圖突出了網(wǎng)絡(luò)拓?fù)渲械穆窂饺绾嗡茉鞌U散過程。然而，真實的乘客路徑顯然不是馬爾可夫的，從而讓人質(zhì)疑網(wǎng)絡(luò)拓?fù)鋵嶋H上能教給我們關(guān)于真實系統(tǒng)屬性的什么知識。或者，利用關(guān)于實際乘客行程的可用數(shù)據(jù)，我們可以基于真實路徑研究這種擴散過程（圖 4c）。這項研究揭示，系統(tǒng)的拓?fù)浣Y(jié)構(gòu)或在連邊上旅行的乘客聚合量都不足以解釋系統(tǒng)中復(fù)雜的非馬爾可夫路徑和流。具體來說，圖 4c 揭示了一種強烈的方向偏好，這種偏好根植于路徑的非馬爾可夫特征和底層地理環(huán)境。這些模式極大地改變了系統(tǒng)中動態(tài)過程的演變，并限制了系統(tǒng)拓?fù)淠芨嬖V我們的關(guān)于真實交通網(wǎng)絡(luò)魯棒性和效率的信息。

高階模型幫助我們克服標(biāo)準(zhǔn)網(wǎng)絡(luò)方法的這些局限性。例如，我們可以將拉普拉斯矩陣和轉(zhuǎn)移矩陣推廣到高維德布魯因圖（De Bruijn graph）模型 [39, 16]，以捕捉系統(tǒng)的因果拓?fù)洌╟ausal topology），這是由路徑的非馬爾可夫特征決定的。這種高階網(wǎng)絡(luò)表示是我們能夠?qū)討B(tài)系統(tǒng)研究中的方法（如特征分解、譜分析或穩(wěn)定性理論）應(yīng)用于具有非馬爾可夫路徑的系統(tǒng)的基礎(chǔ)。它們使我們能夠分析網(wǎng)絡(luò)化系統(tǒng)中時間和拓?fù)渲g復(fù)雜的相互作用，并解釋為什么路徑的非馬爾可夫特征既可以減緩也可以加速動態(tài)過程和集體動力學(xué) [16]。

展望

為了解釋復(fù)雜系統(tǒng)的屬性，理解系統(tǒng)的組件如何相互影響至關(guān)重要。網(wǎng)絡(luò)科學(xué)基于直接的、成對相互作用的網(wǎng)絡(luò)抽象，提供了強大的計算和分析工具來應(yīng)對這一挑戰(zhàn)。這種極其簡單的抽象幫助我們揭示了那些與相互作用拓?fù)涞幕咎卣鞫翘囟ㄏ到y(tǒng)的細(xì)節(jié)緊密相關(guān)的涌現(xiàn)現(xiàn)象。此外，圖論方法與統(tǒng)計物理學(xué)中基于系綜的技術(shù)相結(jié)合，已經(jīng)發(fā)展成為關(guān)系數(shù)據(jù)中統(tǒng)計分析、推斷和機器學(xué)習(xí)任務(wù)的重要基礎(chǔ)。然而，多虧了關(guān)于社會、技術(shù)和生物系統(tǒng)的豐富數(shù)據(jù)，網(wǎng)絡(luò)模型究竟能在多大程度上教會我們要了解真實系統(tǒng)的局限性正變得越來越明顯。這些數(shù)據(jù)凸顯了對先進(jìn)建模技術(shù)的需求，以捕捉在真實系統(tǒng)中觀察到的復(fù)雜的非馬爾可夫相互作用路徑。

一個重要的認(rèn)識論挑戰(zhàn)是，鑒于高維數(shù)據(jù)，尋找推斷復(fù)雜系統(tǒng)最優(yōu)模型的新方法。參照奧卡姆剃刀原理，此類模型應(yīng)當(dāng)是極度簡約的。也就是說，我們要限制我們的假設(shè)，以便得出超越具體研究系統(tǒng)的可推廣陳述。但是，一個好的模型仍然必須足夠復(fù)雜，以解釋在真實系統(tǒng)中觀察到的路徑，而這正是標(biāo)準(zhǔn)網(wǎng)絡(luò)模型往往不足之處。換句話說，我們要尋找的是通過模擬路徑中的共同模式來壓縮可用信息的高階模型，這與網(wǎng)絡(luò)科學(xué)揭示跨廣泛系統(tǒng)的共同拓?fù)淠Ｊ降姆绞椒浅Ｏ嗨啤Ｒ虼耍趶?fù)雜系統(tǒng)的豐富數(shù)據(jù)尋找最優(yōu)模型變成了一個機器學(xué)習(xí)問題，其中標(biāo)準(zhǔn)網(wǎng)絡(luò)模型僅僅是觀察到的路徑的多種可能解釋之一。適當(dāng)調(diào)整的模型選擇和統(tǒng)計學(xué)習(xí)技術(shù)可用于從時間序列數(shù)據(jù)中學(xué)習(xí)高階模型的最優(yōu)階數(shù) [14]，但對于如何解決其他類型模型和數(shù)據(jù)的這一挑戰(zhàn)，目前知之甚少。

隨著模型維度增加，高階模型的規(guī)模可能迅速增長，這一事實引入了必須解決的統(tǒng)計和可擴展性挑戰(zhàn)。對高階模型的可靠推斷潛在地需要海量數(shù)據(jù)，而這些數(shù)據(jù)在許多場景中可能無法獲得。此外，使用固定的單階模型可能會引入風(fēng)險，即在路徑數(shù)據(jù)中同時出現(xiàn)欠擬合和過擬合模式，并不必要地使高階模型復(fù)雜化。這突顯了對利用變階[40, 15] 和多階模型 [14] 的計算和統(tǒng)計方法的需求，以及模型降階技術(shù) [18]，以生成既不過度擬合也不欠擬合數(shù)據(jù)的計算上可處理的模型。

除了這些方法論問題外，對非馬爾可夫路徑的研究也預(yù)示了一類新的高階生成網(wǎng)絡(luò)模型的出現(xiàn)，類似于例如隨機塊模型 [41]、Watts-Strogatz 模型 [42] 或 Barabási-Albert 模型 [43]。在網(wǎng)絡(luò)科學(xué)中，此類生成模型在網(wǎng)絡(luò)結(jié)構(gòu)模式的檢測以及識別它們涌現(xiàn)的極簡機制方面都發(fā)揮著至關(guān)重要的作用。關(guān)于類似的非馬爾可夫模式在不同系統(tǒng)中涌現(xiàn)的機制知之甚少，這是一個潛在富有成果的研究領(lǐng)域。

最后，關(guān)于高階網(wǎng)絡(luò)模型與動態(tài)過程之間關(guān)系的研究有著廣闊的前景。雖然大多數(shù)研究集中在線性擴散過程上，但一些工作已經(jīng)考慮了非馬爾可夫路徑對元種群模型的影響，這類似于網(wǎng)絡(luò)上的反應(yīng)擴散 [44, 45]。具有非馬爾可夫相互作用路徑的一般非線性過程的屬性大多尚未探索。這些包括高階網(wǎng)絡(luò)上的耦合動態(tài)系統(tǒng)（例如振蕩器），當(dāng)主穩(wěn)定性分析等標(biāo)準(zhǔn)工具不適用時，允許局部和非局部模式涌現(xiàn)的條件的識別 [46]，以及使用高階模型研究網(wǎng)絡(luò)控制 [47]。

高階建模技術(shù)使我們能夠利用現(xiàn)有的網(wǎng)絡(luò)方法，將其擴展到最優(yōu)模型，以解釋復(fù)雜系統(tǒng)中的相互作用拓?fù)洹４祟惸Ｐ秃图夹g(shù)不僅為物理學(xué)、計算機科學(xué)和統(tǒng)計學(xué)之間的跨學(xué)科交流創(chuàng)造了新機遇，它們還有助于使復(fù)雜系統(tǒng)社區(qū)與那些對極度簡單的、受物理學(xué)啟發(fā)的模型的（有時是天真的）應(yīng)用表示擔(dān)憂的研究者達(dá)成和解。

原文鏈接：https://arxiv.org/pdf/1806.05977