一種基于離散數據從局部到全局的網絡重構算法*

徐翔 朱承 朱先強

(國防科技大學, 信息系統工程重點實驗室, 長沙 410073)

1 引 言

網絡作為復雜系統的抽象已經廣泛存在于現實世界, 從生物界的食物網[1]到大腦中的腦網絡[2]、現代社會中的電力網絡[3]、Internet[4]、社交網絡[5]等等.網絡中的節點代表系統中的實體要素, 網絡中各節點間的連邊表示系統中各實體之間的相互作用關系.然而, 人們一般對現實中的復雜系統知之甚少, 不了解系統內部的相關結構, 例如, 生態系統中各個物種之間的相互影響關系以及大腦中各個部分之間的相互作用關系等.雖然系統中各要素之間的作用關系較難獲得, 但隨著系統的逐漸演化, 與系統行為相關的演化數據會被保留下來.例如, 在生態系統演化的過程中, 不同演化時期存在的物種種類和物種數量可以獲得; 2019 年末到2020 年初爆發的新型冠狀病毒在不同城市和國家的感染情況數據[6]也可以得到.通過對系統演化過程中產生的相關數據進行分析和處理, 可以對系統中隱藏的結構和動態過程進行挖掘, 這類研究問題被稱為動力學網絡重構[7-12].在現實世界, 很多網絡中的數據能夠體現網絡上的動態過程, 例如: 交通網絡中的流量、車速, 社交網絡中的點贊數、轉發數等.網絡的結構具有自適應性質, 網絡結構自適應辨識問題[13]對網絡結構重構具有一定的幫助.綜上, 如何根據網絡上可觀測的相關數據對未知結構的網絡進行拓撲重構是一個重要且有研究價值的問題.

目前, 對網絡拓撲進行重構的工作較為豐富,包括格蘭杰因果關系(Granger Causality)[14-17]方法, 通過因果推斷來判斷變量之間的關系, 該方法對成對變量具有較好的適用性, 變量數量達到三個或者以上時, 推斷的結果可能會出現錯誤.壓縮感知(compress sensing)[10,18,19]方法通過將網絡上的動力學過程轉化成壓縮感知方法能夠處理的欠定線性系統, 利用可觀測到的時間序列對網絡的拓撲進行重構.壓縮感知被廣泛應用于電子工程尤其是信號處理中, 用于獲取和重構稀疏或可壓縮的信號.該方法的優勢是通過獲取少量的信號數據重構出原始信號.除此之外, 相關性方法能夠根據網絡節點之間的相關性進行網絡拓撲重構.文獻[20]針對網絡噪音干擾問題提出了一種結合QR 分解（QR decomposition）和壓縮感知的方法對網絡進行結構重構.相關性方法在其他領域也有很多應用[21,22], 該方法的優點是簡單快速, 適合大規模網絡拓撲重構問題, 但對數據的數量和質量要求較高.

在面對網絡結構重構問題時, 一些工作基于信息論[23]進行研究.與簡單的利用相關系數作為節點相關性的依據相比, 與信息論相關的指標能更好地反映不同條件下節點之間的相關性程度.常用的基于信息論的指標有互信息[24](mutual information)、傳輸熵[25](transfer entropy)和因果熵[26,27](causation entropy)等.文獻[28]利用傳輸熵對無線傳感網的拓撲進行了推測, 但該網絡的規模較小.網絡重構的方法還有很多, 文獻[29,30]較為詳細地綜述了相關的方法.

本文通過借鑒文獻[31]中利用SIR 模型產生網絡數據的方法進行網絡拓撲結構還原, 產生數據的具體方法將在第3 節闡述.通過利用產生的初始數據, 我們的貢獻有以下幾點: 第一, 與傳統的利用相關性指標[32]進行節點相關性計算不同, 首先統計被相同感染節點同時感染的不同節點數量, 然后再統計任意兩個節點同時被感染的數量, 綜合考慮了疾病在節點間的傳播過程以及網絡中不同節點之間的相互作用, 更加全面地刻畫了網絡節點之間的相關性; 第二, 與基于時序數據網絡重構[33,34]方法不同, 我們的方法只需要離散的數據,即對數據之間的時間相關性沒有要求, 較大程度降低了獲取數據的難度; 第三, 使用了從局部到全局的結構重構方法, 充分利用了每條數據對網絡結構的影響, 提高了網絡拓撲重構的準確性且計算復雜度較低.

2 網絡重構問題描述

網絡重構問題根據對網絡初始結構的了解程度可以分為兩類: 一類為已知部分初始網絡結構, 對剩余未知部分進行推理或預測, 這類問題一般被稱為鏈路預測[35]問題; 另一類為對初始網絡結構完全未知, 一般需要知道網絡上的動力學過程或能夠獲取網絡上的觀測數據.

針對網絡結構部分已知的情況, 可以利用鏈路預測相關方法進行網絡結構的重構, 典型的鏈路預測方法包括最大似然估計[36]和概率模型[37]等.鏈路預測的思想是對給定的一個網絡, 為網絡中沒有連邊的節點對 (x,y) 賦予一個得分值Sxy, 對網絡中所有沒有連邊的節點對的得分值按照從大到小排序, 排在最前面的節點對形成的連邊概率最大.鏈路預測的思想可以用于網絡拓撲重構, 需要做的是盡可能保證每條鏈路預測準確性以及預測鏈路的完整性.利用鏈路預測中的相似性[38]概念, 通過對相似節點進行判斷從而獲得相似節點間的連邊關系.

對網絡進行重構有以下幾點困難: 第一, 網絡結構的復雜性, 實際中的很多網絡具有節點數量多、連接關系復雜的結構特點; 第二, 網絡各節點之間的交互關系一般為非線性; 第三, 關于網絡動態過程的數據較難獲得, 包括數據的數量和質量.同時, 在獲取網絡數據過程中還會存在一定的干擾數據, 即噪聲會對網絡重構的精度產生影響; 第四, 實際存在的網絡大多數為時序動態網絡, 且存在雙層甚至多層的結構, 因此如何對時序網絡和多層網絡結構進行重構[39]也是一個重要的問題.

3 基于離散數據的網絡重構算法

3.1 網絡數據

網絡上的動力學過程有很多, 我們采取了經典的SIR 疾病傳播過程[40]來產生網絡數據, 具體過程如下.

在未知網絡中任選一個節點作為感染節點, 設置疾病傳播概率β=0.2 , 節點恢復概率μ=1 , 一定時間之后, 統計網絡中最終穩定狀態下被感染節點的數量, 這一過程產生了網絡的一條數據, 以此類推, 重復上述操作, 可以獲得關于網絡的多條數據信息.文獻[41]使用了和本文相似的數據形式,不同的是該論文產生數據使用的動力學過程與本文不同, 且網絡中節點的狀態會以一定的概率相互轉移, 即使用的是非終態數據.

圖1 網絡初始二值數據矩陣Fig.1.Initial binary data matrix of the network.

為了更加直觀地表示網絡數據并便于后續的相關計算, 將網絡中被感染的節點狀態設置為“1”,未被感染的節點設置為“0”, 則可以得到網絡初始二值數據矩陣, 數據格式如圖1 所示.其中每一行代表不同的數據, 即不同的感染節點, 每一列表示網絡中不同的節點.從該數據矩陣可以看出, 不同數據之間相互獨立, 不存在時間上的相關性, 即數據是離散的.

3.2 相關定義

為了更方便地介紹我們提出的基于離散數據的網絡重構算法, 給出以下相關定義.

定義1二值數據矩陣

給定一個圖G=(V,E,S) ,V表示圖中的節點集合,E表示圖中的連邊集合,S表示圖中各節點的狀態集合, 當節點j被第i次選取的感染源節點感染時,Sij=1 , 反之Sij=0.二值數 據 矩 陣SM×N=(Sij)M×N, 其中M表示網絡中數據的數量,N為網絡節點數量.

例如, 一個擁有16 條數據8 個節點的網絡的二值數據矩陣可表示如下:

定義2相同感染源數量

給定一個圖數據矩陣SM×N, 定義網絡中任意兩節點的相同感染源數量為SikSij,k /=j(當k=j時 規 定nkj=0 ), 其 中Sik表示節點k在第i次選取感染源節點時的狀態,Sij表示節點j在第i次選取感染源節點時的狀態,M表示數據數量.兩節點的相同感染源數量越大,則兩節點間的相似性越高, 兩節點間存在連邊的概率越大, 反之亦然.例如, 圖2 中n12=4.

定義3相同感染源矩陣

給定一個二值數據圖G=(V,S) 和圖數據矩陣SM×N, 稱AG=(nkj)N×N, k /=j(當k=j時規定nkj=0 )為相同感染源矩陣,nkj為節點k和節點j的相同感染源數量,N為二值數據圖節點數量.

例如, 圖2 所示數據矩陣對應的相同感染源矩陣為

圖2 節點1 和節點2 的相同感染源數量Fig.2.The same number of infection sources in node 1 and node 2.

定義4二值數據子圖

給定一個二值數據圖G=(V,S) 和圖數據矩陣SM×N, 針對任意數據i, 稱節點集合V i={vj|Sij=1}中的節點構成的圖為二值數據子圖Gi.例如, 由S16×8可以得到數據1 對應的子圖節點集合為

定義5子圖相同感染源矩陣

給定一個二值數據子圖Gi, 稱Ai=(nkj)Ni×Ni,(當k=j時規定nkj=0 )為二值相同感染源矩陣, 其中k,j ∈V i,Ni為第i次選取感染源節點時對應的二值數據子圖節點數量.

例如, 圖2 數據矩陣中數據1 對應的子圖相同感染源矩陣為

3.3 子圖重構

給定任意數據i對應的子圖相同感染源矩陣Ai, 對矩陣中每一行進行最大共同數據數搜索, 對最大數據數處兩節點進行連邊, 得到重構子圖其中Vi為子圖節點集合,Ei為子圖連邊集合,npq為節點p和節點q的相同感染源數量; 當出現多個相同的最大共同數據數時, 依次選取其中的每個最大值對應的兩節點進行連邊, 對得到的不同子圖進行度方差計算, 并將度方差值小的子網絡作為最終子網的結構, 度方差計算公式為

其中表示第i條數據對應子圖的度方差值;kj表示子圖中節點的度值;表示子圖的平均度值,Ni為子圖節點數量.例如, 數據1 對應的子圖重構過程如圖3 所示.

圖3 子圖重構過程Fig.3.Subgraph reconstruction process.

3.4 子圖疊加

對所有數據得到的重構子圖Gi進行疊加, 即對子圖Gi中的相同節點進行重疊, 最終得到圖G的拓撲, 即其中V表示圖G的節點集合,E表示圖G的連邊集合,M表示數據數量,Ei為第i條數據對應重構子圖的連邊集合,V i為第i條數據對應重構子圖的節點集合, 子圖疊加過程如圖4 所示.對所有數據得到的子圖進行疊加得到網絡全局拓撲, 即得到網絡的鄰接矩陣A.

圖4 子圖疊加過程Fig.4.Subgraph superposition process.

子圖疊加數學計算過程如下:

網絡重構算法流程如下所示:

AlgorithmNetwork Topology Reconstruction

Input:Binary data matrixSM×N

為主動適應高等教育國際化的要求，加快研究生培養國際化進程，拓展研究生的國際視野，提高研究生培養質量，中國藥科大學自2013年起在同類高校中率先面向博士生研究生正式開設本校第一門國際化公開課《Scientific Methodology》，迄今已經6年，其中2013～2017年共開設18門公開課，每門課程資助5萬元，投入經費90萬元。2018年已正式立項7門，每門課程同樣資助經費5萬元。已經開設的中國藥科大學研究生國際化公開課詳情參見表1。

Output:Network topologyG

4 實驗結果分析

4.1 網絡重構指標

采用真正例率(true positive rate, TPR)和假正例率(false positive rate, FPR)分別表示網絡重構的準確率和誤差, TPR 指標越高, FPR 指標越小則說明網絡重構的效果越好[42-43].TPR 和FPR指標計算公式如下:

其 中TP(true positive), FP(false positive), TN(true negative)和FN(false negative)分別表示真正例數、假正例數、真反例數和假反例數.

4.2 三種網絡重構效果分析

為了驗證本文算法的適用性, 針對不同規模的WS 小世界網絡、BA 無標度網絡[44]和ER 隨機網絡[45]進行了網絡重構實驗, 網絡的相關拓撲屬性如表1 所列, 其中N表示網絡節點數量,E表示網絡連邊數量,〈k〉表示網絡的平均度,C表示網絡的集聚系數,〈l〉表示網絡的平均路徑.

表1 三類網絡的基本拓撲特征Table 1.Basic topological features of the three types of networks.

4.2.1 WS 小世界網絡實驗

圖5 為不同規模的WS 小世界網絡重構實驗效果.由圖5 可以發現, 隨著網絡數據的增加, 不同節點規模的WS 小世界網絡重構效果也越來越好, 且最終都能夠完全重構出網絡的拓撲.還可以發現, 隨著網絡規模的增加, 需要的網絡數據量也隨之增加, 但從最終達到平衡的數據數量來看, 需要的信息數量與網絡節點呈線性變化, 即對網絡數據數量的需求與網絡節點數量是同一個數量級.從對WS 小世界網絡的重構實驗結果可以看出,本文算法對網絡拓撲還原具有較高的準確性, 能夠適應不同規模的網絡, 且對網絡數據數量的要求不高.

圖5 不同規模的WS 小世界網絡重構實驗效果Fig.5.Experimental results of WS small world network reconstruction with different scales.

圖6 不同規模的WS 小世界網絡重構誤差分析Fig.6.Error analysis of WS small world network reconstruction with different scales.

為更直觀地反映算法的重構效果, 定義了多邊重構誤差eFP和少邊重構誤差eFN指標, 計算公式如下:

如圖6 所示, 在不同節點規模的WS 小世界網絡重構實驗過程中, 隨著實驗數據的增加, 網絡重構實驗的多邊重構誤差eFP和少邊重構誤差eFN逐漸減小, 最終趨近于0, 該實驗誤差分析進一步說明了本文算法的準確性.

圖7 WS 小世界網絡不同平均度值對網絡重構實驗效果的影響Fig.7.Influence of different average degrees of WS small world network on network reconstruction experiment.

圖8 不同規模的BA 無標度網絡重構實驗效果Fig.8.Experimental results of BA scale-free network reconstruction with different scales.

圖9 不同規模的BA 小世界網絡重構誤差分析Fig.9.Error analysis of BA scale-free network reconstruction with different scales.

圖10 BA 無標度網絡不同平均度值對網絡重構實驗效果的影響Fig.10.The influence of different average degree values of BA scale-free network on network reconstruction experiment.

4.2.2 BA 無標度網絡實驗

從圖8 可以看出, 與WS 小世界網絡類似, 隨著網絡數據的增加網絡重構效果也越來越好.圖9展示了實驗誤差曲線, 總體上來說網絡重構誤差隨著實驗數據的增加逐漸減小.從圖10 可以看出,在相同網絡數據的情況下, 網絡平均度值越大, 網絡的重構效果越差, 且平均度值越大網絡重構需要的數據越大.

4.2.3 ER 隨機網絡實驗

圖11 展示了不同規模的ER 隨機網絡重構效果, 相比同等規模的WS 小世界和BA 無標度網絡, ER 隨機網絡需要更多的網絡數據.圖12 展示了兩種重構誤差的變化情況, 可以發現, 兩種重構誤差變化的趨勢基本一致, 誤差隨實驗數據的增加逐漸減小.除此之外, 對具有不同平均度值的ER隨機網絡進行網絡重構實驗, 發現網絡重構的效果與網絡的平均度值基本沒有關系, 從圖13 可以發現三條曲線基本重合.

圖11 不同規模的ER 隨機網絡重構實驗效果Fig.11.Experimental results of ER random network reconstruction with different scales.

圖12 不同規模的ER 小世界網絡重構誤差分析Fig.12.Error analysis of ER random network reconstruction with different scales.

4.2.4 三種網絡對比實驗

為了更直觀地比較不同網絡重構效果, 同時對WS, BA 和ER 網絡進行網絡重構實驗, 實驗結果見圖14.從圖14 可以看出, 在相同網絡數據下可以發現WS 和BA 網絡的重構效果類似, ER 網絡則需要更多的網絡數據.

4.3 三種實際網絡重構效果分析

為了更好地說明本文算法的適用性, 選取了三個實際網絡進行網絡重構實驗, 三個網絡的具體屬性數據如表2 所列.其中, Euroroad 和Minnesota 為公路網數據集, 相關數據可以在http://networkrepository.com/road.php 上獲取; Power Grid 數據集由Duncan Watts 和Steven Strogatz 編制, 數據可在http://cdg.columbia.edu/cdg/datasets 上獲取.

圖14 三種不同網絡在相同數據下的重構效果對比Fig.14.Comparison of reconstruction effects of three different networks under the same data.

圖15 三個實際網絡重構實驗效果Fig.15.Experimental results of three practical network reconstruction.

圖16 三個實際網絡重構誤差分析Fig.16.Error analysis of three practical network reconstruction.

表2 三個實際網絡的基本拓撲特征Table 2.Basic topological characteristics of three practical networks.

圖15 展示了三個實際網絡的重構效果, 可以發現網絡邊數(節點)越多, 重構網絡需要的數據越多, 隨著使用數據的增加, 網絡的重構效果也逐步提高.圖16 展示了三個實際網絡對應的重構誤差變化曲線, 可以看出, 三個實際網絡的重構誤差隨著數據量的增加都呈現下降趨勢, 最終都趨近于0.

5 總結與展望

針對網絡結構完全未知, 網絡上的動力學過程已知的網絡結構重構問題, 提出了一種基于離散數據從局部到全局的網絡重構算法.通過在網絡上模擬SIR 疾病傳播過程來產生網絡數據, 利用產生的數據從局部還原到全局疊加, 最終重構出整個網絡的拓撲.我們提出的算法具有快速, 簡單的優勢,且適用于不同網絡類型.為了驗證算法的準確性和適用性, 在具有不同節點數量的WS, BA 和ER 網絡上進行了仿真實驗, 實驗結果表明我們的方法能夠準確地還原出不同規模大小的網絡拓撲.為了驗算法的適用范圍, 還對三個實際網絡進行了重構實驗, 由實驗結果可以發現, 本文提出的算法同樣可行.目前我們研究的對象屬于單層靜態網絡, 以后的工作可能會考慮如何對動態和多層網絡進行拓撲重構.