徐翔 朱承 朱先強
(國防科技大學, 信息系統(tǒng)工程重點實驗室, 長沙 410073)
網(wǎng)絡作為復雜系統(tǒng)的抽象已經(jīng)廣泛存在于現(xiàn)實世界, 從生物界的食物網(wǎng)[1]到大腦中的腦網(wǎng)絡[2]、現(xiàn)代社會中的電力網(wǎng)絡[3]、Internet[4]、社交網(wǎng)絡[5]等等.網(wǎng)絡中的節(jié)點代表系統(tǒng)中的實體要素, 網(wǎng)絡中各節(jié)點間的連邊表示系統(tǒng)中各實體之間的相互作用關系.然而, 人們一般對現(xiàn)實中的復雜系統(tǒng)知之甚少, 不了解系統(tǒng)內部的相關結構, 例如, 生態(tài)系統(tǒng)中各個物種之間的相互影響關系以及大腦中各個部分之間的相互作用關系等.雖然系統(tǒng)中各要素之間的作用關系較難獲得, 但隨著系統(tǒng)的逐漸演化, 與系統(tǒng)行為相關的演化數(shù)據(jù)會被保留下來.例如, 在生態(tài)系統(tǒng)演化的過程中, 不同演化時期存在的物種種類和物種數(shù)量可以獲得; 2019 年末到2020 年初爆發(fā)的新型冠狀病毒在不同城市和國家的感染情況數(shù)據(jù)[6]也可以得到.通過對系統(tǒng)演化過程中產生的相關數(shù)據(jù)進行分析和處理, 可以對系統(tǒng)中隱藏的結構和動態(tài)過程進行挖掘, 這類研究問題被稱為動力學網(wǎng)絡重構[7-12].在現(xiàn)實世界, 很多網(wǎng)絡中的數(shù)據(jù)能夠體現(xiàn)網(wǎng)絡上的動態(tài)過程, 例如: 交通網(wǎng)絡中的流量、車速, 社交網(wǎng)絡中的點贊數(shù)、轉發(fā)數(shù)等.網(wǎng)絡的結構具有自適應性質, 網(wǎng)絡結構自適應辨識問題[13]對網(wǎng)絡結構重構具有一定的幫助.綜上, 如何根據(jù)網(wǎng)絡上可觀測的相關數(shù)據(jù)對未知結構的網(wǎng)絡進行拓撲重構是一個重要且有研究價值的問題.
目前, 對網(wǎng)絡拓撲進行重構的工作較為豐富,包括格蘭杰因果關系(Granger Causality)[14-17]方法, 通過因果推斷來判斷變量之間的關系, 該方法對成對變量具有較好的適用性, 變量數(shù)量達到三個或者以上時, 推斷的結果可能會出現(xiàn)錯誤.壓縮感知(compress sensing)[10,18,19]方法通過將網(wǎng)絡上的動力學過程轉化成壓縮感知方法能夠處理的欠定線性系統(tǒng), 利用可觀測到的時間序列對網(wǎng)絡的拓撲進行重構.壓縮感知被廣泛應用于電子工程尤其是信號處理中, 用于獲取和重構稀疏或可壓縮的信號.該方法的優(yōu)勢是通過獲取少量的信號數(shù)據(jù)重構出原始信號.除此之外, 相關性方法能夠根據(jù)網(wǎng)絡節(jié)點之間的相關性進行網(wǎng)絡拓撲重構.文獻[20]針對網(wǎng)絡噪音干擾問題提出了一種結合QR 分解(QR decomposition)和壓縮感知的方法對網(wǎng)絡進行結構重構.相關性方法在其他領域也有很多應用[21,22], 該方法的優(yōu)點是簡單快速, 適合大規(guī)模網(wǎng)絡拓撲重構問題, 但對數(shù)據(jù)的數(shù)量和質量要求較高.
在面對網(wǎng)絡結構重構問題時, 一些工作基于信息論[23]進行研究.與簡單的利用相關系數(shù)作為節(jié)點相關性的依據(jù)相比, 與信息論相關的指標能更好地反映不同條件下節(jié)點之間的相關性程度.常用的基于信息論的指標有互信息[24](mutual information)、傳輸熵[25](transfer entropy)和因果熵[26,27](causation entropy)等.文獻[28]利用傳輸熵對無線傳感網(wǎng)的拓撲進行了推測, 但該網(wǎng)絡的規(guī)模較小.網(wǎng)絡重構的方法還有很多, 文獻[29,30]較為詳細地綜述了相關的方法.
本文通過借鑒文獻[31]中利用SIR 模型產生網(wǎng)絡數(shù)據(jù)的方法進行網(wǎng)絡拓撲結構還原, 產生數(shù)據(jù)的具體方法將在第3 節(jié)闡述.通過利用產生的初始數(shù)據(jù), 我們的貢獻有以下幾點: 第一, 與傳統(tǒng)的利用相關性指標[32]進行節(jié)點相關性計算不同, 首先統(tǒng)計被相同感染節(jié)點同時感染的不同節(jié)點數(shù)量, 然后再統(tǒng)計任意兩個節(jié)點同時被感染的數(shù)量, 綜合考慮了疾病在節(jié)點間的傳播過程以及網(wǎng)絡中不同節(jié)點之間的相互作用, 更加全面地刻畫了網(wǎng)絡節(jié)點之間的相關性; 第二, 與基于時序數(shù)據(jù)網(wǎng)絡重構[33,34]方法不同, 我們的方法只需要離散的數(shù)據(jù),即對數(shù)據(jù)之間的時間相關性沒有要求, 較大程度降低了獲取數(shù)據(jù)的難度; 第三, 使用了從局部到全局的結構重構方法, 充分利用了每條數(shù)據(jù)對網(wǎng)絡結構的影響, 提高了網(wǎng)絡拓撲重構的準確性且計算復雜度較低.
網(wǎng)絡重構問題根據(jù)對網(wǎng)絡初始結構的了解程度可以分為兩類: 一類為已知部分初始網(wǎng)絡結構, 對剩余未知部分進行推理或預測, 這類問題一般被稱為鏈路預測[35]問題; 另一類為對初始網(wǎng)絡結構完全未知, 一般需要知道網(wǎng)絡上的動力學過程或能夠獲取網(wǎng)絡上的觀測數(shù)據(jù).
針對網(wǎng)絡結構部分已知的情況, 可以利用鏈路預測相關方法進行網(wǎng)絡結構的重構, 典型的鏈路預測方法包括最大似然估計[36]和概率模型[37]等.鏈路預測的思想是對給定的一個網(wǎng)絡, 為網(wǎng)絡中沒有連邊的節(jié)點對 (x,y) 賦予一個得分值Sxy, 對網(wǎng)絡中所有沒有連邊的節(jié)點對的得分值按照從大到小排序, 排在最前面的節(jié)點對形成的連邊概率最大.鏈路預測的思想可以用于網(wǎng)絡拓撲重構, 需要做的是盡可能保證每條鏈路預測準確性以及預測鏈路的完整性.利用鏈路預測中的相似性[38]概念, 通過對相似節(jié)點進行判斷從而獲得相似節(jié)點間的連邊關系.
對網(wǎng)絡進行重構有以下幾點困難: 第一, 網(wǎng)絡結構的復雜性, 實際中的很多網(wǎng)絡具有節(jié)點數(shù)量多、連接關系復雜的結構特點; 第二, 網(wǎng)絡各節(jié)點之間的交互關系一般為非線性; 第三, 關于網(wǎng)絡動態(tài)過程的數(shù)據(jù)較難獲得, 包括數(shù)據(jù)的數(shù)量和質量.同時, 在獲取網(wǎng)絡數(shù)據(jù)過程中還會存在一定的干擾數(shù)據(jù), 即噪聲會對網(wǎng)絡重構的精度產生影響; 第四, 實際存在的網(wǎng)絡大多數(shù)為時序動態(tài)網(wǎng)絡, 且存在雙層甚至多層的結構, 因此如何對時序網(wǎng)絡和多層網(wǎng)絡結構進行重構[39]也是一個重要的問題.
網(wǎng)絡上的動力學過程有很多, 我們采取了經(jīng)典的SIR 疾病傳播過程[40]來產生網(wǎng)絡數(shù)據(jù), 具體過程如下.
在未知網(wǎng)絡中任選一個節(jié)點作為感染節(jié)點, 設置疾病傳播概率β=0.2 , 節(jié)點恢復概率μ=1 , 一定時間之后, 統(tǒng)計網(wǎng)絡中最終穩(wěn)定狀態(tài)下被感染節(jié)點的數(shù)量, 這一過程產生了網(wǎng)絡的一條數(shù)據(jù), 以此類推, 重復上述操作, 可以獲得關于網(wǎng)絡的多條數(shù)據(jù)信息.文獻[41]使用了和本文相似的數(shù)據(jù)形式,不同的是該論文產生數(shù)據(jù)使用的動力學過程與本文不同, 且網(wǎng)絡中節(jié)點的狀態(tài)會以一定的概率相互轉移, 即使用的是非終態(tài)數(shù)據(jù).
圖1 網(wǎng)絡初始二值數(shù)據(jù)矩陣Fig.1.Initial binary data matrix of the network.
為了更加直觀地表示網(wǎng)絡數(shù)據(jù)并便于后續(xù)的相關計算, 將網(wǎng)絡中被感染的節(jié)點狀態(tài)設置為“1”,未被感染的節(jié)點設置為“0”, 則可以得到網(wǎng)絡初始二值數(shù)據(jù)矩陣, 數(shù)據(jù)格式如圖1 所示.其中每一行代表不同的數(shù)據(jù), 即不同的感染節(jié)點, 每一列表示網(wǎng)絡中不同的節(jié)點.從該數(shù)據(jù)矩陣可以看出, 不同數(shù)據(jù)之間相互獨立, 不存在時間上的相關性, 即數(shù)據(jù)是離散的.
為了更方便地介紹我們提出的基于離散數(shù)據(jù)的網(wǎng)絡重構算法, 給出以下相關定義.
定義1二值數(shù)據(jù)矩陣
給定一個圖G=(V,E,S) ,V表示圖中的節(jié)點集合,E表示圖中的連邊集合,S表示圖中各節(jié)點的狀態(tài)集合, 當節(jié)點j被第i次選取的感染源節(jié)點感染時,Sij=1 , 反之Sij=0.二值數(shù) 據(jù) 矩 陣SM×N=(Sij)M×N, 其中M表示網(wǎng)絡中數(shù)據(jù)的數(shù)量,N為網(wǎng)絡節(jié)點數(shù)量.
例如, 一個擁有16 條數(shù)據(jù)8 個節(jié)點的網(wǎng)絡的二值數(shù)據(jù)矩陣可表示如下:
定義2相同感染源數(shù)量
給定一個圖數(shù)據(jù)矩陣SM×N, 定義網(wǎng)絡中任意兩節(jié)點的相同感染源數(shù)量為SikSij,k /=j(當k=j時 規(guī) 定nkj=0 ), 其 中Sik表示節(jié)點k在第i次選取感染源節(jié)點時的狀態(tài),Sij表示節(jié)點j在第i次選取感染源節(jié)點時的狀態(tài),M表示數(shù)據(jù)數(shù)量.兩節(jié)點的相同感染源數(shù)量越大,則兩節(jié)點間的相似性越高, 兩節(jié)點間存在連邊的概率越大, 反之亦然.例如, 圖2 中n12=4.
定義3相同感染源矩陣
給定一個二值數(shù)據(jù)圖G=(V,S) 和圖數(shù)據(jù)矩陣SM×N, 稱AG=(nkj)N×N, k /=j(當k=j時規(guī)定nkj=0 )為相同感染源矩陣,nkj為節(jié)點k和節(jié)點j的相同感染源數(shù)量,N為二值數(shù)據(jù)圖節(jié)點數(shù)量.
例如, 圖2 所示數(shù)據(jù)矩陣對應的相同感染源矩陣為
圖2 節(jié)點1 和節(jié)點2 的相同感染源數(shù)量Fig.2.The same number of infection sources in node 1 and node 2.
定義4二值數(shù)據(jù)子圖
給定一個二值數(shù)據(jù)圖G=(V,S) 和圖數(shù)據(jù)矩陣SM×N, 針對任意數(shù)據(jù)i, 稱節(jié)點集合V i={vj|Sij=1}中的節(jié)點構成的圖為二值數(shù)據(jù)子圖Gi.例如, 由S16×8可以得到數(shù)據(jù)1 對應的子圖節(jié)點集合為
定義5子圖相同感染源矩陣
給定一個二值數(shù)據(jù)子圖Gi, 稱Ai=(nkj)Ni×Ni,(當k=j時規(guī)定nkj=0 )為二值相同感染源矩陣, 其中k,j ∈V i,Ni為第i次選取感染源節(jié)點時對應的二值數(shù)據(jù)子圖節(jié)點數(shù)量.
例如, 圖2 數(shù)據(jù)矩陣中數(shù)據(jù)1 對應的子圖相同感染源矩陣為
給定任意數(shù)據(jù)i對應的子圖相同感染源矩陣Ai, 對矩陣中每一行進行最大共同數(shù)據(jù)數(shù)搜索, 對最大數(shù)據(jù)數(shù)處兩節(jié)點進行連邊, 得到重構子圖其中Vi為子圖節(jié)點集合,Ei為子圖連邊集合,npq為節(jié)點p和節(jié)點q的相同感染源數(shù)量; 當出現(xiàn)多個相同的最大共同數(shù)據(jù)數(shù)時, 依次選取其中的每個最大值對應的兩節(jié)點進行連邊, 對得到的不同子圖進行度方差計算, 并將度方差值小的子網(wǎng)絡作為最終子網(wǎng)的結構, 度方差計算公式為
其中表示第i條數(shù)據(jù)對應子圖的度方差值;kj表示子圖中節(jié)點的度值;表示子圖的平均度值,Ni為子圖節(jié)點數(shù)量.例如, 數(shù)據(jù)1 對應的子圖重構過程如圖3 所示.
圖3 子圖重構過程Fig.3.Subgraph reconstruction process.
對所有數(shù)據(jù)得到的重構子圖Gi進行疊加, 即對子圖Gi中的相同節(jié)點進行重疊, 最終得到圖G的拓撲, 即其中V表示圖G的節(jié)點集合,E表示圖G的連邊集合,M表示數(shù)據(jù)數(shù)量,Ei為第i條數(shù)據(jù)對應重構子圖的連邊集合,V i為第i條數(shù)據(jù)對應重構子圖的節(jié)點集合, 子圖疊加過程如圖4 所示.對所有數(shù)據(jù)得到的子圖進行疊加得到網(wǎng)絡全局拓撲, 即得到網(wǎng)絡的鄰接矩陣A.
圖4 子圖疊加過程Fig.4.Subgraph superposition process.
子圖疊加數(shù)學計算過程如下:
網(wǎng)絡重構算法流程如下所示:
AlgorithmNetwork Topology Reconstruction
Input:Binary data matrixSM×N
為主動適應高等教育國際化的要求,加快研究生培養(yǎng)國際化進程,拓展研究生的國際視野,提高研究生培養(yǎng)質量,中國藥科大學自2013年起在同類高校中率先面向博士生研究生正式開設本校第一門國際化公開課《Scientific Methodology》,迄今已經(jīng)6年,其中2013~2017年共開設18門公開課,每門課程資助5萬元,投入經(jīng)費90萬元。2018年已正式立項7門,每門課程同樣資助經(jīng)費5萬元。已經(jīng)開設的中國藥科大學研究生國際化公開課詳情參見表1。
Output:Network topologyG
采用真正例率(true positive rate, TPR)和假正例率(false positive rate, FPR)分別表示網(wǎng)絡重構的準確率和誤差, TPR 指標越高, FPR 指標越小則說明網(wǎng)絡重構的效果越好[42-43].TPR 和FPR指標計算公式如下:
其 中TP(true positive), FP(false positive), TN(true negative)和FN(false negative)分別表示真正例數(shù)、假正例數(shù)、真反例數(shù)和假反例數(shù).
為了驗證本文算法的適用性, 針對不同規(guī)模的WS 小世界網(wǎng)絡、BA 無標度網(wǎng)絡[44]和ER 隨機網(wǎng)絡[45]進行了網(wǎng)絡重構實驗, 網(wǎng)絡的相關拓撲屬性如表1 所列, 其中N表示網(wǎng)絡節(jié)點數(shù)量,E表示網(wǎng)絡連邊數(shù)量,〈k〉表示網(wǎng)絡的平均度,C表示網(wǎng)絡的集聚系數(shù),〈l〉表示網(wǎng)絡的平均路徑.
表1 三類網(wǎng)絡的基本拓撲特征Table 1.Basic topological features of the three types of networks.
4.2.1 WS 小世界網(wǎng)絡實驗
圖5 為不同規(guī)模的WS 小世界網(wǎng)絡重構實驗效果.由圖5 可以發(fā)現(xiàn), 隨著網(wǎng)絡數(shù)據(jù)的增加, 不同節(jié)點規(guī)模的WS 小世界網(wǎng)絡重構效果也越來越好, 且最終都能夠完全重構出網(wǎng)絡的拓撲.還可以發(fā)現(xiàn), 隨著網(wǎng)絡規(guī)模的增加, 需要的網(wǎng)絡數(shù)據(jù)量也隨之增加, 但從最終達到平衡的數(shù)據(jù)數(shù)量來看, 需要的信息數(shù)量與網(wǎng)絡節(jié)點呈線性變化, 即對網(wǎng)絡數(shù)據(jù)數(shù)量的需求與網(wǎng)絡節(jié)點數(shù)量是同一個數(shù)量級.從對WS 小世界網(wǎng)絡的重構實驗結果可以看出,本文算法對網(wǎng)絡拓撲還原具有較高的準確性, 能夠適應不同規(guī)模的網(wǎng)絡, 且對網(wǎng)絡數(shù)據(jù)數(shù)量的要求不高.
圖5 不同規(guī)模的WS 小世界網(wǎng)絡重構實驗效果Fig.5.Experimental results of WS small world network reconstruction with different scales.
圖6 不同規(guī)模的WS 小世界網(wǎng)絡重構誤差分析Fig.6.Error analysis of WS small world network reconstruction with different scales.
為更直觀地反映算法的重構效果, 定義了多邊重構誤差eFP和少邊重構誤差eFN指標, 計算公式如下:
如圖6 所示, 在不同節(jié)點規(guī)模的WS 小世界網(wǎng)絡重構實驗過程中, 隨著實驗數(shù)據(jù)的增加, 網(wǎng)絡重構實驗的多邊重構誤差eFP和少邊重構誤差eFN逐漸減小, 最終趨近于0, 該實驗誤差分析進一步說明了本文算法的準確性.
圖7 WS 小世界網(wǎng)絡不同平均度值對網(wǎng)絡重構實驗效果的影響Fig.7.Influence of different average degrees of WS small world network on network reconstruction experiment.
圖8 不同規(guī)模的BA 無標度網(wǎng)絡重構實驗效果Fig.8.Experimental results of BA scale-free network reconstruction with different scales.
圖9 不同規(guī)模的BA 小世界網(wǎng)絡重構誤差分析Fig.9.Error analysis of BA scale-free network reconstruction with different scales.
圖10 BA 無標度網(wǎng)絡不同平均度值對網(wǎng)絡重構實驗效果的影響Fig.10.The influence of different average degree values of BA scale-free network on network reconstruction experiment.
4.2.2 BA 無標度網(wǎng)絡實驗
從圖8 可以看出, 與WS 小世界網(wǎng)絡類似, 隨著網(wǎng)絡數(shù)據(jù)的增加網(wǎng)絡重構效果也越來越好.圖9展示了實驗誤差曲線, 總體上來說網(wǎng)絡重構誤差隨著實驗數(shù)據(jù)的增加逐漸減小.從圖10 可以看出,在相同網(wǎng)絡數(shù)據(jù)的情況下, 網(wǎng)絡平均度值越大, 網(wǎng)絡的重構效果越差, 且平均度值越大網(wǎng)絡重構需要的數(shù)據(jù)越大.
4.2.3 ER 隨機網(wǎng)絡實驗
圖11 展示了不同規(guī)模的ER 隨機網(wǎng)絡重構效果, 相比同等規(guī)模的WS 小世界和BA 無標度網(wǎng)絡, ER 隨機網(wǎng)絡需要更多的網(wǎng)絡數(shù)據(jù).圖12 展示了兩種重構誤差的變化情況, 可以發(fā)現(xiàn), 兩種重構誤差變化的趨勢基本一致, 誤差隨實驗數(shù)據(jù)的增加逐漸減小.除此之外, 對具有不同平均度值的ER隨機網(wǎng)絡進行網(wǎng)絡重構實驗, 發(fā)現(xiàn)網(wǎng)絡重構的效果與網(wǎng)絡的平均度值基本沒有關系, 從圖13 可以發(fā)現(xiàn)三條曲線基本重合.
圖11 不同規(guī)模的ER 隨機網(wǎng)絡重構實驗效果Fig.11.Experimental results of ER random network reconstruction with different scales.
圖12 不同規(guī)模的ER 小世界網(wǎng)絡重構誤差分析Fig.12.Error analysis of ER random network reconstruction with different scales.
4.2.4 三種網(wǎng)絡對比實驗
為了更直觀地比較不同網(wǎng)絡重構效果, 同時對WS, BA 和ER 網(wǎng)絡進行網(wǎng)絡重構實驗, 實驗結果見圖14.從圖14 可以看出, 在相同網(wǎng)絡數(shù)據(jù)下可以發(fā)現(xiàn)WS 和BA 網(wǎng)絡的重構效果類似, ER 網(wǎng)絡則需要更多的網(wǎng)絡數(shù)據(jù).
為了更好地說明本文算法的適用性, 選取了三個實際網(wǎng)絡進行網(wǎng)絡重構實驗, 三個網(wǎng)絡的具體屬性數(shù)據(jù)如表2 所列.其中, Euroroad 和Minnesota 為公路網(wǎng)數(shù)據(jù)集, 相關數(shù)據(jù)可以在http://networkrepository.com/road.php 上獲取; Power Grid 數(shù)據(jù)集由Duncan Watts 和Steven Strogatz 編制, 數(shù)據(jù)可在http://cdg.columbia.edu/cdg/datasets 上獲取.
圖14 三種不同網(wǎng)絡在相同數(shù)據(jù)下的重構效果對比Fig.14.Comparison of reconstruction effects of three different networks under the same data.
圖15 三個實際網(wǎng)絡重構實驗效果Fig.15.Experimental results of three practical network reconstruction.
圖16 三個實際網(wǎng)絡重構誤差分析Fig.16.Error analysis of three practical network reconstruction.
表2 三個實際網(wǎng)絡的基本拓撲特征Table 2.Basic topological characteristics of three practical networks.
圖15 展示了三個實際網(wǎng)絡的重構效果, 可以發(fā)現(xiàn)網(wǎng)絡邊數(shù)(節(jié)點)越多, 重構網(wǎng)絡需要的數(shù)據(jù)越多, 隨著使用數(shù)據(jù)的增加, 網(wǎng)絡的重構效果也逐步提高.圖16 展示了三個實際網(wǎng)絡對應的重構誤差變化曲線, 可以看出, 三個實際網(wǎng)絡的重構誤差隨著數(shù)據(jù)量的增加都呈現(xiàn)下降趨勢, 最終都趨近于0.
針對網(wǎng)絡結構完全未知, 網(wǎng)絡上的動力學過程已知的網(wǎng)絡結構重構問題, 提出了一種基于離散數(shù)據(jù)從局部到全局的網(wǎng)絡重構算法.通過在網(wǎng)絡上模擬SIR 疾病傳播過程來產生網(wǎng)絡數(shù)據(jù), 利用產生的數(shù)據(jù)從局部還原到全局疊加, 最終重構出整個網(wǎng)絡的拓撲.我們提出的算法具有快速, 簡單的優(yōu)勢,且適用于不同網(wǎng)絡類型.為了驗證算法的準確性和適用性, 在具有不同節(jié)點數(shù)量的WS, BA 和ER 網(wǎng)絡上進行了仿真實驗, 實驗結果表明我們的方法能夠準確地還原出不同規(guī)模大小的網(wǎng)絡拓撲.為了驗算法的適用范圍, 還對三個實際網(wǎng)絡進行了重構實驗, 由實驗結果可以發(fā)現(xiàn), 本文提出的算法同樣可行.目前我們研究的對象屬于單層靜態(tài)網(wǎng)絡, 以后的工作可能會考慮如何對動態(tài)和多層網(wǎng)絡進行拓撲重構.