一種基于離散數(shù)據(jù)從局部到全局的網(wǎng)絡(luò)重構(gòu)算法*

徐翔 朱承 朱先強(qiáng)

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

1 引 言

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

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

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

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

2 網(wǎng)絡(luò)重構(gòu)問題描述

網(wǎng)絡(luò)重構(gòu)問題根據(jù)對網(wǎng)絡(luò)初始結(jié)構(gòu)的了解程度可以分為兩類: 一類為已知部分初始網(wǎng)絡(luò)結(jié)構(gòu), 對剩余未知部分進(jìn)行推理或預(yù)測, 這類問題一般被稱為鏈路預(yù)測[35]問題; 另一類為對初始網(wǎng)絡(luò)結(jié)構(gòu)完全未知, 一般需要知道網(wǎng)絡(luò)上的動力學(xué)過程或能夠獲取網(wǎng)絡(luò)上的觀測數(shù)據(jù).

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

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

3 基于離散數(shù)據(jù)的網(wǎng)絡(luò)重構(gòu)算法

3.1 網(wǎng)絡(luò)數(shù)據(jù)

網(wǎng)絡(luò)上的動力學(xué)過程有很多, 我們采取了經(jīng)典的SIR 疾病傳播過程[40]來產(chǎn)生網(wǎng)絡(luò)數(shù)據(jù), 具體過程如下.

在未知網(wǎng)絡(luò)中任選一個節(jié)點作為感染節(jié)點, 設(shè)置疾病傳播概率β=0.2 , 節(jié)點恢復(fù)概率μ=1 , 一定時間之后, 統(tǒng)計網(wǎng)絡(luò)中最終穩(wěn)定狀態(tài)下被感染節(jié)點的數(shù)量, 這一過程產(chǎn)生了網(wǎng)絡(luò)的一條數(shù)據(jù), 以此類推, 重復(fù)上述操作, 可以獲得關(guān)于網(wǎng)絡(luò)的多條數(shù)據(jù)信息.文獻(xiàn)[41]使用了和本文相似的數(shù)據(jù)形式,不同的是該論文產(chǎn)生數(shù)據(jù)使用的動力學(xué)過程與本文不同, 且網(wǎng)絡(luò)中節(jié)點的狀態(tài)會以一定的概率相互轉(zhuǎn)移, 即使用的是非終態(tài)數(shù)據(jù).

圖1 網(wǎng)絡(luò)初始二值數(shù)據(jù)矩陣Fig.1.Initial binary data matrix of the network.

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

3.2 相關(guān)定義

為了更方便地介紹我們提出的基于離散數(shù)據(jù)的網(wǎng)絡(luò)重構(gòu)算法, 給出以下相關(guān)定義.

定義1二值數(shù)據(jù)矩陣

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

例如, 一個擁有16 條數(shù)據(jù)8 個節(jié)點的網(wǎng)絡(luò)的二值數(shù)據(jù)矩陣可表示如下:

定義2相同感染源數(shù)量

給定一個圖數(shù)據(jù)矩陣SM×N, 定義網(wǎng)絡(luò)中任意兩節(jié)點的相同感染源數(shù)量為SikSij,k /=j(當(dāng)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(當(dāng)k=j時規(guī)定nkj=0 )為相同感染源矩陣,nkj為節(jié)點k和節(jié)點j的相同感染源數(shù)量,N為二值數(shù)據(jù)圖節(jié)點數(shù)量.

例如, 圖2 所示數(shù)據(jù)矩陣對應(yīng)的相同感染源矩陣為

圖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é)點構(gòu)成的圖為二值數(shù)據(jù)子圖Gi.例如, 由S16×8可以得到數(shù)據(jù)1 對應(yīng)的子圖節(jié)點集合為

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

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

例如, 圖2 數(shù)據(jù)矩陣中數(shù)據(jù)1 對應(yīng)的子圖相同感染源矩陣為

3.3 子圖重構(gòu)

給定任意數(shù)據(jù)i對應(yīng)的子圖相同感染源矩陣Ai, 對矩陣中每一行進(jìn)行最大共同數(shù)據(jù)數(shù)搜索, 對最大數(shù)據(jù)數(shù)處兩節(jié)點進(jìn)行連邊, 得到重構(gòu)子圖其中Vi為子圖節(jié)點集合,Ei為子圖連邊集合,npq為節(jié)點p和節(jié)點q的相同感染源數(shù)量; 當(dāng)出現(xiàn)多個相同的最大共同數(shù)據(jù)數(shù)時, 依次選取其中的每個最大值對應(yīng)的兩節(jié)點進(jìn)行連邊, 對得到的不同子圖進(jìn)行度方差計算, 并將度方差值小的子網(wǎng)絡(luò)作為最終子網(wǎng)的結(jié)構(gòu), 度方差計算公式為

其中表示第i條數(shù)據(jù)對應(yīng)子圖的度方差值;kj表示子圖中節(jié)點的度值;表示子圖的平均度值,Ni為子圖節(jié)點數(shù)量.例如, 數(shù)據(jù)1 對應(yīng)的子圖重構(gòu)過程如圖3 所示.

圖3 子圖重構(gòu)過程Fig.3.Subgraph reconstruction process.

3.4 子圖疊加

對所有數(shù)據(jù)得到的重構(gòu)子圖Gi進(jìn)行疊加, 即對子圖Gi中的相同節(jié)點進(jìn)行重疊, 最終得到圖G的拓?fù)? 即其中V表示圖G的節(jié)點集合,E表示圖G的連邊集合,M表示數(shù)據(jù)數(shù)量,Ei為第i條數(shù)據(jù)對應(yīng)重構(gòu)子圖的連邊集合,V i為第i條數(shù)據(jù)對應(yīng)重構(gòu)子圖的節(jié)點集合, 子圖疊加過程如圖4 所示.對所有數(shù)據(jù)得到的子圖進(jìn)行疊加得到網(wǎng)絡(luò)全局拓?fù)? 即得到網(wǎng)絡(luò)的鄰接矩陣A.

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

子圖疊加數(shù)學(xué)計算過程如下:

網(wǎng)絡(luò)重構(gòu)算法流程如下所示:

AlgorithmNetwork Topology Reconstruction

Input:Binary data matrixSM×N

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

Output:Network topologyG

4 實驗結(jié)果分析

4.1 網(wǎng)絡(luò)重構(gòu)指標(biāo)

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

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

4.2 三種網(wǎng)絡(luò)重構(gòu)效果分析

為了驗證本文算法的適用性, 針對不同規(guī)模的WS 小世界網(wǎng)絡(luò)、BA 無標(biāo)度網(wǎng)絡(luò)[44]和ER 隨機(jī)網(wǎng)絡(luò)[45]進(jìn)行了網(wǎng)絡(luò)重構(gòu)實驗, 網(wǎng)絡(luò)的相關(guān)拓?fù)鋵傩匀绫? 所列, 其中N表示網(wǎng)絡(luò)節(jié)點數(shù)量,E表示網(wǎng)絡(luò)連邊數(shù)量,〈k〉表示網(wǎng)絡(luò)的平均度,C表示網(wǎng)絡(luò)的集聚系數(shù),〈l〉表示網(wǎng)絡(luò)的平均路徑.

表1 三類網(wǎng)絡(luò)的基本拓?fù)涮卣鱐able 1.Basic topological features of the three types of networks.

4.2.1 WS 小世界網(wǎng)絡(luò)實驗

圖5 為不同規(guī)模的WS 小世界網(wǎng)絡(luò)重構(gòu)實驗效果.由圖5 可以發(fā)現(xiàn), 隨著網(wǎng)絡(luò)數(shù)據(jù)的增加, 不同節(jié)點規(guī)模的WS 小世界網(wǎng)絡(luò)重構(gòu)效果也越來越好, 且最終都能夠完全重構(gòu)出網(wǎng)絡(luò)的拓?fù)?還可以發(fā)現(xiàn), 隨著網(wǎng)絡(luò)規(guī)模的增加, 需要的網(wǎng)絡(luò)數(shù)據(jù)量也隨之增加, 但從最終達(dá)到平衡的數(shù)據(jù)數(shù)量來看, 需要的信息數(shù)量與網(wǎng)絡(luò)節(jié)點呈線性變化, 即對網(wǎng)絡(luò)數(shù)據(jù)數(shù)量的需求與網(wǎng)絡(luò)節(jié)點數(shù)量是同一個數(shù)量級.從對WS 小世界網(wǎng)絡(luò)的重構(gòu)實驗結(jié)果可以看出,本文算法對網(wǎng)絡(luò)拓?fù)溥€原具有較高的準(zhǔn)確性, 能夠適應(yīng)不同規(guī)模的網(wǎng)絡(luò), 且對網(wǎng)絡(luò)數(shù)據(jù)數(shù)量的要求不高.

圖5 不同規(guī)模的WS 小世界網(wǎng)絡(luò)重構(gòu)實驗效果Fig.5.Experimental results of WS small world network reconstruction with different scales.

圖6 不同規(guī)模的WS 小世界網(wǎng)絡(luò)重構(gòu)誤差分析Fig.6.Error analysis of WS small world network reconstruction with different scales.

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

如圖6 所示, 在不同節(jié)點規(guī)模的WS 小世界網(wǎng)絡(luò)重構(gòu)實驗過程中, 隨著實驗數(shù)據(jù)的增加, 網(wǎng)絡(luò)重構(gòu)實驗的多邊重構(gòu)誤差eFP和少邊重構(gòu)誤差eFN逐漸減小, 最終趨近于0, 該實驗誤差分析進(jìn)一步說明了本文算法的準(zhǔn)確性.

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

圖8 不同規(guī)模的BA 無標(biāo)度網(wǎng)絡(luò)重構(gòu)實驗效果Fig.8.Experimental results of BA scale-free network reconstruction with different scales.

圖9 不同規(guī)模的BA 小世界網(wǎng)絡(luò)重構(gòu)誤差分析Fig.9.Error analysis of BA scale-free network reconstruction with different scales.

圖10 BA 無標(biāo)度網(wǎng)絡(luò)不同平均度值對網(wǎng)絡(luò)重構(gòu)實驗效果的影響Fig.10.The influence of different average degree values of BA scale-free network on network reconstruction experiment.

4.2.2 BA 無標(biāo)度網(wǎng)絡(luò)實驗

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

4.2.3 ER 隨機(jī)網(wǎng)絡(luò)實驗

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

圖11 不同規(guī)模的ER 隨機(jī)網(wǎng)絡(luò)重構(gòu)實驗效果Fig.11.Experimental results of ER random network reconstruction with different scales.

圖12 不同規(guī)模的ER 小世界網(wǎng)絡(luò)重構(gòu)誤差分析Fig.12.Error analysis of ER random network reconstruction with different scales.

4.2.4 三種網(wǎng)絡(luò)對比實驗

為了更直觀地比較不同網(wǎng)絡(luò)重構(gòu)效果, 同時對WS, BA 和ER 網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)重構(gòu)實驗, 實驗結(jié)果見圖14.從圖14 可以看出, 在相同網(wǎng)絡(luò)數(shù)據(jù)下可以發(fā)現(xiàn)WS 和BA 網(wǎng)絡(luò)的重構(gòu)效果類似, ER 網(wǎng)絡(luò)則需要更多的網(wǎng)絡(luò)數(shù)據(jù).

4.3 三種實際網(wǎng)絡(luò)重構(gòu)效果分析

為了更好地說明本文算法的適用性, 選取了三個實際網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)重構(gòu)實驗, 三個網(wǎng)絡(luò)的具體屬性數(shù)據(jù)如表2 所列.其中, Euroroad 和Minnesota 為公路網(wǎng)數(shù)據(jù)集, 相關(guān)數(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)絡(luò)在相同數(shù)據(jù)下的重構(gòu)效果對比Fig.14.Comparison of reconstruction effects of three different networks under the same data.

圖15 三個實際網(wǎng)絡(luò)重構(gòu)實驗效果Fig.15.Experimental results of three practical network reconstruction.

圖16 三個實際網(wǎng)絡(luò)重構(gòu)誤差分析Fig.16.Error analysis of three practical network reconstruction.

表2 三個實際網(wǎng)絡(luò)的基本拓?fù)涮卣鱐able 2.Basic topological characteristics of three practical networks.

圖15 展示了三個實際網(wǎng)絡(luò)的重構(gòu)效果, 可以發(fā)現(xiàn)網(wǎng)絡(luò)邊數(shù)(節(jié)點)越多, 重構(gòu)網(wǎng)絡(luò)需要的數(shù)據(jù)越多, 隨著使用數(shù)據(jù)的增加, 網(wǎng)絡(luò)的重構(gòu)效果也逐步提高.圖16 展示了三個實際網(wǎng)絡(luò)對應(yīng)的重構(gòu)誤差變化曲線, 可以看出, 三個實際網(wǎng)絡(luò)的重構(gòu)誤差隨著數(shù)據(jù)量的增加都呈現(xiàn)下降趨勢, 最終都趨近于0.

5 總結(jié)與展望

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