A machine learning approach to predicting dynamicalobservables from network structure

從網(wǎng)絡(luò)結(jié)構(gòu)預(yù)測(cè)動(dòng)力學(xué)可觀測(cè)量的機(jī)器學(xué)習(xí)方法

https://royalsocietypublishing.org/rspa/article/481/2306/20240435/66122/A-machine-learning-approach-to-predicting

從結(jié)構(gòu)特征預(yù)測(cè)給定動(dòng)力學(xué)過(guò)程的結(jié)果，是網(wǎng)絡(luò)科學(xué)中一個(gè)尚未解決的關(guān)鍵挑戰(zhàn)。該目標(biāo)受限于復(fù)雜系統(tǒng)中結(jié)構(gòu)與動(dòng)力學(xué)之間存在的非線性、關(guān)聯(lián)性及反饋效應(yīng)等困難。本研究提出一種基于機(jī)器學(xué)習(xí)算法的方法，為理解網(wǎng)絡(luò)結(jié)構(gòu)與動(dòng)力學(xué)之間的關(guān)系邁出了重要一步：具體而言，該方法僅憑網(wǎng)絡(luò)結(jié)構(gòu)即可預(yù)測(cè)——（1）疾病從單一節(jié)點(diǎn)出發(fā)的傳播規(guī)模；（2）由Kuramoto振子構(gòu)成系統(tǒng)的同步程度。我們揭示了實(shí)現(xiàn)此類預(yù)測(cè)的關(guān)鍵拓?fù)涮卣鳎?duì)網(wǎng)絡(luò)指標(biāo)的重要性進(jìn)行了排序，其準(zhǔn)確度遠(yuǎn)超以往研究：對(duì)流行病傳播而言，k-核（k-core）起決定性作用；而對(duì)同步性而言，介數(shù)中心性（betweenness centrality）與可達(dá)性（accessibility）是與振子狀態(tài)最相關(guān)的度量。

對(duì)所有網(wǎng)絡(luò)，我們發(fā)現(xiàn)隨機(jī)森林均能以高精度預(yù)測(cè)疫情暴發(fā)規(guī)�；蛲綘顟B(tài)，表明網(wǎng)絡(luò)結(jié)構(gòu)在傳播過(guò)程中起著根本性作用。本方法具有普適性，可應(yīng)用于幾乎所有在復(fù)雜網(wǎng)絡(luò)上運(yùn)行的動(dòng)力學(xué)過(guò)程。此外，本研究是將機(jī)器學(xué)習(xí)方法用于揭示復(fù)雜網(wǎng)絡(luò)系統(tǒng)中涌現(xiàn)動(dòng)力學(xué)模式的重要一步。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)，機(jī)器學(xué)習(xí)，動(dòng)力學(xué)過(guò)程

1. 引言
   現(xiàn)代網(wǎng)絡(luò)科學(xué)已成功表明：恰當(dāng)?shù)乜坍嬒到y(tǒng)組分間的相互作用模式，對(duì)理解其功能至關(guān)重要［1–5］。然而，探究支配系統(tǒng)結(jié)構(gòu)與功能關(guān)系的規(guī)律仍是一項(xiàng)艱巨挑戰(zhàn)。實(shí)現(xiàn)這一目標(biāo)不僅要求我們?cè)u(píng)估特定結(jié)構(gòu)模式對(duì)網(wǎng)絡(luò)動(dòng)力學(xué)的影響，更需在僅掌握不完整、且常含噪聲的結(jié)構(gòu)信息前提下，預(yù)測(cè)其動(dòng)力學(xué)結(jié)果。這一問(wèn)題絕非微不足道：從已知結(jié)構(gòu)過(guò)渡到預(yù)判系統(tǒng)動(dòng)力學(xué)響應(yīng)，意味著必須厘清節(jié)點(diǎn)響應(yīng)的非線性、由復(fù)雜連接模式引發(fā)的時(shí)空關(guān)聯(lián)，以及交互所產(chǎn)生的反饋等多重困難。

此外，眾所周知，網(wǎng)絡(luò)性質(zhì)對(duì)動(dòng)力學(xué)系統(tǒng)的影響方式各異——換言之，某些性質(zhì)對(duì)某一動(dòng)力學(xué)過(guò)程的影響遠(yuǎn)大于其他性質(zhì)。例如，在疾病傳播情境中，度分布對(duì)系統(tǒng)臨界特性（即是否存在趨近于零的傳播閾值）起決定性作用，而關(guān)聯(lián)性影響則相對(duì)次要［5, 6］；類似結(jié)論亦適用于謠言傳播［7, 8］與同步現(xiàn)象［4, 9］等其他動(dòng)力學(xué)過(guò)程。識(shí)別出對(duì)系統(tǒng)動(dòng)力學(xué)起關(guān)鍵作用的網(wǎng)絡(luò)性質(zhì)，不僅能提升動(dòng)力學(xué)預(yù)測(cè)的準(zhǔn)確性，還可為應(yīng)對(duì)拓?fù)渥兓驅(qū)嵤┛刂聘深A(yù)、從而引導(dǎo)系統(tǒng)達(dá)成期望的全局狀態(tài)，提供可操作的響應(yīng)策略。其應(yīng)用涵蓋：在傳染病動(dòng)力學(xué)中識(shí)別關(guān)鍵傳播者與核心傳播節(jié)點(diǎn)［10］，以及調(diào)控電網(wǎng)、電子電路和神經(jīng)系統(tǒng)的同步水平［4］。

本文旨在應(yīng)對(duì)上述兩大挑戰(zhàn)：
其一，我們提出一種方法論，可對(duì)兩類典型動(dòng)力學(xué)過(guò)程（疾病傳播與同步）的多種宏觀可觀測(cè)量進(jìn)行預(yù)測(cè)；
其二，我們明確了實(shí)現(xiàn)此類高精度預(yù)測(cè)所依賴的關(guān)鍵拓?fù)湫再|(zhì)。具體而言，我們構(gòu)建了一種通用方法，用于預(yù)測(cè)復(fù)雜網(wǎng)絡(luò)中動(dòng)力學(xué)過(guò)程的相關(guān)變量——即Kuramoto振子的同步程度，以及易感-感染-恢復(fù)（SIR）模型中的疫情暴發(fā)規(guī)模；同時(shí)評(píng)估了各類網(wǎng)絡(luò)性質(zhì)在預(yù)測(cè)這些動(dòng)力學(xué)變量時(shí)的重要性。例如，我們驗(yàn)證了k-核與暴發(fā)規(guī)模具有最強(qiáng)關(guān)聯(lián)性，印證了先前研究結(jié)論；但僅靠該指標(biāo)仍不足以實(shí)現(xiàn)準(zhǔn)確預(yù)測(cè)。我們指出：并無(wú)單一指標(biāo)能有效識(shí)別主要傳播者，而需多種指標(biāo)組合。對(duì)于同步問(wèn)題，介數(shù)中心性（betweenness centrality）與可達(dá)性（accessibility）與振子狀態(tài)（即部分/全局相鎖定或非鎖定）關(guān)聯(lián)最為密切；但各指標(biāo)重要性排序隨同步程度變化而變化。

本方法具普適性，可拓展應(yīng)用于其他需從節(jié)點(diǎn)子集及其動(dòng)力學(xué)出發(fā)預(yù)測(cè)隨機(jī)動(dòng)力學(xué)變量的場(chǎng)景（如［8, 11］）。本文所提出的方法為借助現(xiàn)代機(jī)器學(xué)習(xí)技術(shù)，深入探索復(fù)雜系統(tǒng)的結(jié)構(gòu)與動(dòng)力學(xué)關(guān)系開辟了新路徑。

1. 機(jī)器學(xué)習(xí)模型構(gòu)建

1. 結(jié)果與討論

圖2展示了模型（方程2.2）對(duì)以下六類網(wǎng)絡(luò)預(yù)測(cè)的疫情暴發(fā)規(guī)模：(i) 美國(guó)航空運(yùn)輸網(wǎng)絡(luò)（僅含主要機(jī)場(chǎng)，N=500個(gè)機(jī)場(chǎng)，2002年，平均度〈k〉=11.9條邊/機(jī)場(chǎng)）［21］；(ii) Hamsterster社交網(wǎng)絡(luò)（N=1788名用戶，平均度〈k〉=13.95條邊/用戶）［22］；(iii) 政治博客網(wǎng)絡(luò)（N=1222個(gè)博客，平均度〈k〉=27.4個(gè)超鏈接/博客）［23］；(iv) Bitcoin Alpha網(wǎng)絡(luò)（N=3775名用戶，平均度〈k〉=7.5個(gè)連接/用戶）［24］；(v) 某大型歐洲研究機(jī)構(gòu)的電子郵件數(shù)據(jù)（N=986名用戶，平均度〈k〉=32.6個(gè)連接/用戶）［25］；以及(vi) Gnutella點(diǎn)對(duì)點(diǎn)文件共享網(wǎng)絡(luò)（N=6299臺(tái)計(jì)算機(jī)，平均度〈k〉=6.6個(gè)鏈接/計(jì)算機(jī)）［25］。對(duì)于所有網(wǎng)絡(luò)，我們發(fā)現(xiàn)隨機(jī)森林能以高精度預(yù)測(cè)每個(gè)節(jié)點(diǎn)的暴發(fā)規(guī)模，表明網(wǎng)絡(luò)結(jié)構(gòu)在傳播過(guò)程中起著根本性作用。

我們還將隨機(jī)森林方法與傳統(tǒng)的多元線性回歸模型進(jìn)行了比較。如圖3所示，對(duì)于不同的傳播概率β值，隨機(jī)森林在決定系數(shù) （衡量自變量對(duì)因變量方差解釋程度，取值范圍0至1，值越高表示擬合越好）方面提供了更精確的結(jié)果。深度神經(jīng)網(wǎng)絡(luò)給出的結(jié)果與隨機(jī)森林相似。

優(yōu)化［26］。重要的是，隨機(jī)森林算法還能量化各特征的重要性。本質(zhì)上，該重要性是通過(guò)衡量特征在構(gòu)建決策樹時(shí)降低不確定性的有效性來(lái)計(jì)算的。隨機(jī)森林提供的所有特征重要性值之和為1，代表了每個(gè)度量對(duì)預(yù)測(cè)估計(jì)量貢獻(xiàn)的百分比。

圖4展示了當(dāng)疫情暴發(fā)規(guī)模的估計(jì)被分解為特征向量中所用各網(wǎng)絡(luò)度量貢獻(xiàn)函數(shù)時(shí)所得結(jié)果。我們可以看到，每項(xiàng)度量的重要性取決于感染概率β。此外，對(duì)于大多數(shù)網(wǎng)絡(luò)，k-核是預(yù)測(cè)暴發(fā)規(guī)模最決定性的特征——這一結(jié)果與先前關(guān)于網(wǎng)絡(luò)中關(guān)鍵傳播者的分析一致［7］。同時(shí)，可達(dá)性（accessibility）在美國(guó)航空運(yùn)輸網(wǎng)絡(luò)和Gnutella網(wǎng)絡(luò)的傳播能力預(yù)測(cè)中也發(fā)揮重要作用，這已在文獻(xiàn)［10］中得到驗(yàn)證。然而，各度量的貢獻(xiàn)（影響力）強(qiáng)烈依賴于網(wǎng)絡(luò)類型。例如，在電子郵件網(wǎng)絡(luò)中，度（degree）與k-核同樣重要；但在Hamsterster和政治博客網(wǎng)絡(luò)中，k-核則起決定性作用。

因此，不存在單一指標(biāo)可識(shí)別此類主要傳播者，而需綜合多個(gè)指標(biāo)共同作用。這種網(wǎng)絡(luò)屬性的影響還依賴于傳播概率β。因此，我們的分析比以往研究（如［7,10］）更具普適性，并顯著提升了對(duì)最具影響力傳播者的識(shí)別能力。本方法允許同時(shí)比較任意數(shù)量網(wǎng)絡(luò)屬性的影響——即當(dāng)它們的作用被一并考慮并組合使用時(shí)，可使預(yù)測(cè)效果更優(yōu)。

(b) 同步現(xiàn)象

Kuramoto模型（KM）是研究同步現(xiàn)象的一個(gè)典范模型［4］。在復(fù)雜網(wǎng)絡(luò)中，KM由以下方程組描述：

對(duì)于較小的耦合強(qiáng)度，可達(dá)性（accessibility）度量在預(yù)測(cè)中起關(guān)鍵作用；然而，隨著 λ λ 增大，PageRank中心性在預(yù)測(cè)節(jié)點(diǎn)狀態(tài)時(shí)扮演更重要的角色。事實(shí)上，PageRank與可達(dá)性是與振子狀態(tài)最相關(guān)的兩項(xiàng)度量。

1. 結(jié)論

綜上所述，我們已證明：僅通過(guò)少量節(jié)點(diǎn)提取的結(jié)構(gòu)特征，即可有效估計(jì)復(fù)雜網(wǎng)絡(luò)中的動(dòng)力學(xué)結(jié)果。本文提出的方法具有高度普適性，可精準(zhǔn)適用于兩類截然不同的動(dòng)力學(xué)過(guò)程——疾病傳播與耦合振子同步。本研究成果對(duì)網(wǎng)絡(luò)上動(dòng)力學(xué)過(guò)程的分析具有重要意義，并為僅憑結(jié)構(gòu)信息預(yù)測(cè)系統(tǒng)動(dòng)力學(xué)行為開辟了新路徑。

本工作對(duì)復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)研究具有重要啟示，且具備多方面拓展?jié)摿Γ豪�，可將該方法�?yīng)用于合作演化［29］、謠言傳播或其他流行病模型［30］的研究；在時(shí)序網(wǎng)絡(luò)［31］中，可用于預(yù)測(cè)未來(lái)連接關(guān)系及動(dòng)力學(xué)過(guò)程的演化；在自適應(yīng)動(dòng)態(tài)網(wǎng)絡(luò)［32］中，可預(yù)測(cè)底層動(dòng)力學(xué)過(guò)程如何驅(qū)動(dòng)網(wǎng)絡(luò)結(jié)構(gòu)演變；還可進(jìn)一步探究網(wǎng)絡(luò)中多種動(dòng)力學(xué)過(guò)程共存且相互作用的情形［33,34］——如謠言對(duì)疫情傳播的影響，或合作行為對(duì)觀點(diǎn)演化的作用；最后，本文方法亦可拓展至高階結(jié)構(gòu)網(wǎng)絡(luò)［35,36］研究，從而揭示單純復(fù)形（simplicial complexes）等高階拓?fù)鋵?duì)動(dòng)力學(xué)演化的影響。

總之，借助機(jī)器學(xué)習(xí)研究復(fù)雜網(wǎng)絡(luò)中的動(dòng)力學(xué)過(guò)程，有助于深入理解結(jié)構(gòu)與動(dòng)力學(xué)之間的內(nèi)在關(guān)聯(lián)，從而通過(guò)調(diào)控網(wǎng)絡(luò)結(jié)構(gòu)實(shí)現(xiàn)對(duì)動(dòng)力學(xué)過(guò)程的有效引導(dǎo)與控制。本研究具有一般性，可廣泛應(yīng)用于各類動(dòng)力學(xué)過(guò)程與復(fù)雜網(wǎng)絡(luò)，包括時(shí)序網(wǎng)絡(luò)、多層網(wǎng)絡(luò)、自適應(yīng)網(wǎng)絡(luò)以及具高階結(jié)構(gòu)的網(wǎng)絡(luò)。

https://royalsocietypublishing.org/rspa/article/481/2306/20240435/66122/A-machine-learning-approach-to-predicting