吳亞麗,任遠光,董昂,周傲然,吳學金,鄭帥龍
1.西安理工大學 自動化與信息工程學院,西安 710048
2.陜西省復(fù)雜系統(tǒng)控制與智能信息處理重點實驗室,西安 710048
現(xiàn)實生活中的許多復(fù)雜系統(tǒng)如電力網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、疾病網(wǎng)絡(luò)、社交網(wǎng)絡(luò)和生物網(wǎng)絡(luò)等均可以抽象為復(fù)雜網(wǎng)絡(luò),其中存在著一些重要的節(jié)點對于網(wǎng)絡(luò)的結(jié)構(gòu)功能、結(jié)構(gòu)特性以及信息流通起主導(dǎo)作用[1]。例如,電力網(wǎng)絡(luò)[2]中,保護樞紐節(jié)點可以避免發(fā)生級聯(lián)故障[3],從而預(yù)防大規(guī)模停電事故;交通網(wǎng)絡(luò)[4-5]中,關(guān)鍵節(jié)點的癱瘓或失效都會對整個交通網(wǎng)絡(luò)的連通性、通行效率和運力分配產(chǎn)生重大影響,引發(fā)交通擁堵和經(jīng)濟損失等問題;疾病網(wǎng)絡(luò)[6-7]中,通過追蹤和管理關(guān)鍵人員,可以有效地阻止疾病擴散。因此,準確和高效地識別復(fù)雜網(wǎng)絡(luò)中具有影響力的節(jié)點一直是復(fù)雜網(wǎng)絡(luò)研究的熱點問題。
目前國內(nèi)外學者提出了許多識別復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點的方法,如度中心性(degree centrality,DC)[8],特征向量中心性(eigenvector centrality,EC)[9],介數(shù)中心性(betweenness centrality,BC)[10]和接近中心性(closeness centrality,CC)[11];度中心性認為節(jié)點的重要性取決于其鄰居節(jié)點的數(shù)量,計算復(fù)雜度低,適用于大規(guī)模網(wǎng)絡(luò),然而忽視了節(jié)點鄰域的拓撲信息,準確性通常較低;特征向量中心性基于隨機游走的思想,考慮了節(jié)點的度及其鄰居節(jié)點包含的信息;介數(shù)中心性和接近中心性是兩種基于網(wǎng)絡(luò)全局特性的方法,但隨著網(wǎng)絡(luò)規(guī)模的爆發(fā)式增長,這兩種方法的計算復(fù)雜度往往較高,并且難以處理網(wǎng)絡(luò)中的一些孤立節(jié)點。
Kitsak 等人[12]于2013 年提出的K 殼分解法(K-shell decomposition,K-shell)根據(jù)節(jié)點在網(wǎng)絡(luò)中的位置對所有節(jié)點的重要性進行分層,并且認為越接近網(wǎng)絡(luò)核心位置的節(jié)點重要性越高。在大規(guī)模網(wǎng)絡(luò)得到了廣泛使用,但其不足之處在于無法區(qū)分處于相同殼層節(jié)點的重要性。為解決這一問題,研究人員在K-shell 方法的基礎(chǔ)上又提出了一些改進的方法。Zeng 等人[13]提出混合度分解方法(mixed degree decomposition,MDD),該方法考慮已移除節(jié)點對于指定節(jié)點的影響,通過耗盡度和剩余度對節(jié)點的重要性進行評估;Bae 和Kim[14]在2016 年提出了鄰域核心中心度方法(the coreness centrality,Cnc+),該方法通過對鄰居節(jié)點的Ks值求和來評估節(jié)點的重要性;Wang 等人[15]考慮了K-shell 分解中產(chǎn)生的迭代信息,提出了一種K-shell迭代因子方法(the K-shell iteration factor,KS_IF);朱曉霞等人[16]在K-shell方法的基礎(chǔ)上,考慮到邊和鄰居節(jié)點的差異貢獻性對節(jié)點重要性的影響,提出加權(quán)度方法(modified K-shell,MKS);Qiu等人[17]提出一種基于全局和局部影響的關(guān)鍵節(jié)點識別方法(the local influence and global influence,LGI),根據(jù)節(jié)點的度、聚類系數(shù)和位置信息對節(jié)點的重要性進行排序;Lai等人[18]綜合考慮節(jié)點度、鄰域節(jié)點度以及K-shell信息,提出加權(quán)K-shell 度鄰域識別方法(the weighted k-shell degree neighborhood identification method,KSD)。上述方法雖然對于關(guān)鍵節(jié)點識別的準確性得到提升,然而對節(jié)點鄰居Ks值累加的形式不能充分考慮鄰域信息對于節(jié)點重要性的貢獻,影響關(guān)鍵節(jié)點識別能力。
為了更充分地利用節(jié)點鄰域的信息,本文提出了一種基于節(jié)點鄰域K-shell 分布的關(guān)鍵節(jié)點識別方法(Kshell distribution of neighbours,KDN)。該方法通過節(jié)點鄰域的Ks值定義節(jié)點的熵,來反映鄰居節(jié)點的Kshell 分布特征,認為節(jié)點的鄰居節(jié)點越多,鄰居節(jié)點的Ks值越大且分布越均勻(更多的鄰居節(jié)點處于網(wǎng)絡(luò)核心),則該節(jié)點重要性越高。為了驗證所提方法的有效性,本文基于易感-感染-恢復(fù)模型(susceptible-infectedrecovered,SIR)[19-22],在11 個真實網(wǎng)絡(luò)數(shù)據(jù)集上進行了仿真和驗證,并與部分現(xiàn)有關(guān)鍵節(jié)點識別方法對比分析,實驗結(jié)果表明本文所提出KDN方法的優(yōu)越性。
K-shell方法主要利用節(jié)點的位置信息,根據(jù)網(wǎng)絡(luò)中節(jié)點所處位置(處于網(wǎng)絡(luò)核心或邊緣),劃分不同殼值來評價節(jié)點重要性,該方法步驟如下:
首先,去除掉網(wǎng)絡(luò)中度為1 的節(jié)點及其連邊,然后迭代至整個網(wǎng)絡(luò)中不存在度為1的節(jié)點,將此次去除的節(jié)點歸為1-shell 層,并分配Ks值為1。重復(fù)執(zhí)行該過程,可以得到2-shell、3-shell等層,最終將網(wǎng)絡(luò)中所有節(jié)點劃分為不同的層,每個節(jié)點都相應(yīng)地分配了Ks值。其中Ks值最大的節(jié)點所在的層即為核心層,而核心層節(jié)點的影響力大于非核心層節(jié)點。
圖1 所示為一個小型網(wǎng)絡(luò)的K-shell 分解示例圖。K-shell方法將網(wǎng)絡(luò)分成了3層,節(jié)點1,2,3,4的Ks值為3,節(jié)點5,6,7,8 的Ks值為2,節(jié)點9,10,11,12,13,14,15的Ks值為1,K-shell方法將擁有相同Ks值的節(jié)點視為具有相同的重要性。
圖1 K-shell分解示例圖Fig.1 Example diagram of K-shell decomposition
在混合度分解方法中,用耗盡度來衡量已去除節(jié)點對于指定節(jié)點的影響。這種采用混合Ks值的改進方法,既增加了網(wǎng)絡(luò)分層的層數(shù),又提高了關(guān)鍵節(jié)點識別的準確性,該方法可以表示為:
其中,λ是一個可調(diào)參數(shù),λ∈[0,1]。當λ=0 時,MDD方法與K-shell 方法相同。當λ=1 時,MDD 方法與DC方法一致,Km(i)為混合Ks值,Kr(i)為剩余度,Ke(i)為耗盡度。
K-shell方法是識別復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點的方法之一,但該方法只考慮節(jié)點的位置信息,忽視了節(jié)點鄰域的拓撲信息,無法準確評估網(wǎng)絡(luò)中節(jié)點的傳播能力。考慮鄰居節(jié)點的Ks值可以提高對于節(jié)點重要性的識別能力,具有高Ks值鄰居節(jié)點的節(jié)點更加關(guān)鍵[16]。
如圖2 的小型網(wǎng)絡(luò)圖,節(jié)點1 和節(jié)點2 度值相同和Ks值相同(度為5,Ks值為2),且鄰居節(jié)點的Ks之和相等,但是節(jié)點1的傳播能力(spreading capability,SC)卻明顯優(yōu)于節(jié)點2,SC1>SC2。節(jié)點1的和節(jié)點2的鄰居Ks值分布分別為[2,2,2,2,2]和[3,2,2,1,2]。在這種情況下,可以合理假設(shè),如果節(jié)點具有更多的鄰居節(jié)點且鄰居節(jié)點的Ks值既高又均勻,則該節(jié)點的傳播能力更強,重要性也更高。
圖2 示例網(wǎng)絡(luò)Fig.2 Schematic network
信息熵[23]是用來衡量信息不確定性或信息量的量化指標,信息量越多,熵值越大,反之則越小。在離散的事件集合中,信息熵與事件發(fā)生的概率分布、可能事件的數(shù)量之間存在密切關(guān)系。為了更充分地利用節(jié)點的信息,本文以信息熵作為載體,通過節(jié)點全局信息Ks值定義概率分布pi,計算得到節(jié)點vi的鄰域Ks熵。熵值的大小可以反映節(jié)點的鄰居節(jié)點數(shù)量和鄰域節(jié)點位置分布的均勻性。鄰居節(jié)點越多,熵值越大;鄰域Ks值分布越均勻,熵值也會變大。
美國學者香農(nóng)于1948年提出了信息熵(information entropy)[23]的概念。熵值的大小可以反映事件包含信息量的多少,X表示可能事件x1,x2,…,xn的集合,pi表示事件xi的概率。X的信息熵可由式(2)計算:
一方面,X分布更均勻,熵值更大。另一方面,n不斷增加,熵值也會隨之增大。
如果一個節(jié)點有更多的鄰居節(jié)點位于網(wǎng)絡(luò)的核心位置,即擁有較高的Ks值,并且鄰居節(jié)點Ks值的分布更加均勻,則該節(jié)點在網(wǎng)絡(luò)中傳播能力更強,同時具有更高的重要性。節(jié)點vi的Ks值用Ks(vi)表示,Ni表示節(jié)點vi的鄰居節(jié)點集合,節(jié)點vi鄰居節(jié)點的Ks值之和用Ks'(vi)來表示,計算公式為:
通過式(4)計算得到節(jié)點vi的鄰域Ks熵E(vi):
節(jié)點vi的影響能力(influence ability,IA)為其鄰居節(jié)點的熵E(vi)之和:
最終,節(jié)點的KDN(vi)值計算公式如式(6)所示:
節(jié)點vi的KDN值越大,說明節(jié)點的重要性越高。
本文使用示例網(wǎng)絡(luò)和不同類型的真實網(wǎng)絡(luò)進行實驗和仿真,其中10 個真實網(wǎng)絡(luò)由網(wǎng)絡(luò)數(shù)據(jù)庫(https://networkrepository.com/index.php)提供。
11 個網(wǎng)絡(luò)分別為:(1)Schematic 網(wǎng)絡(luò);(2)Karate網(wǎng) 絡(luò);(3)Dolphins 網(wǎng)絡(luò);(4)Train 網(wǎng)絡(luò);(5)Jazz 網(wǎng)絡(luò);(6)USAir97 網(wǎng)絡(luò);(7)Netscience 網(wǎng)絡(luò);(8)Email 網(wǎng)絡(luò);(9)Euroroad網(wǎng)絡(luò);(10)Hamsterster網(wǎng)絡(luò);(11)PowerGrid網(wǎng)絡(luò)。11 個網(wǎng)絡(luò)的信息如表1 所示,其中N表示網(wǎng)絡(luò)的節(jié)點數(shù)量,E表示網(wǎng)絡(luò)的邊數(shù),表示網(wǎng)絡(luò)的平均度,表示網(wǎng)絡(luò)的最短平均距離,c表示網(wǎng)絡(luò)的集聚系數(shù),Ksmax表示利用K-shell方法對網(wǎng)絡(luò)進行分解之后網(wǎng)絡(luò)核心層的核值,βth表示網(wǎng)絡(luò)的流行閾值。
表1 11個網(wǎng)絡(luò)的統(tǒng)計特性Table 1 Statistical characteristics of 11 complex networks
為了評估不同方法對節(jié)點重要性的區(qū)分能力,使用DM(distinct metric)[24]指標進行檢驗。當DM=1,表示所有節(jié)點具有不同的重要性。DM 值越接近1,說明對節(jié)點重要性的區(qū)分能力越強。通過式(7)計算DM值:
表2 總結(jié)了不同方法在11 個復(fù)雜網(wǎng)絡(luò)上的DM值。KDN 方法在7個網(wǎng)絡(luò)中DM值是最高的,在Karate網(wǎng)絡(luò)和Hamsterster網(wǎng)絡(luò)中,KDN方法與LGI方法接近,在Euroroad 網(wǎng)絡(luò)和Powergrid 網(wǎng)絡(luò)中DM 值較低,原因是在Euroroad 網(wǎng)絡(luò)和Powergrid 網(wǎng)絡(luò)節(jié)點數(shù)量眾多,但其最大Ks值分別為2和5,表明在K-shell分解中有很多節(jié)點被分在相同的層級,這間接導(dǎo)致KDN 方法在這兩個網(wǎng)絡(luò)中的區(qū)分能力并不高。圖3為不同方法top節(jié)點的DM 值變化曲線,其中在Dolphins 網(wǎng)絡(luò)、USAir97 網(wǎng)絡(luò)和Email 網(wǎng)絡(luò)中,KDN 方法對前10%、前20%、…所有節(jié)點重要性的區(qū)分能力上有著明顯的優(yōu)勢,僅在Netscience 網(wǎng)絡(luò)中對少部分top 節(jié)點重要性的區(qū)分能力低于BC方法。
表2 不同方法在11個網(wǎng)絡(luò)中的DM值Table 2 DM values of different methods on 11 complex networks
圖3 不同方法top節(jié)點的DM值變化曲線Fig.3 DM values curve of top nodes with different methods
除DM 指標以外,使用單調(diào)性函數(shù)(monotonicity function,M)[14]來對不同關(guān)鍵節(jié)點識別方法的區(qū)分度進行分析,M指標的計算如式(8)所示:
其中,R表示需要排序的數(shù)據(jù)向量,n表示R中不同等級的數(shù)目,nr表示相同等級節(jié)點的個數(shù),如果所有節(jié)點的重要性都被分配在同一等級上,那么M=0;如果所有節(jié)點的重要性都被分配到不同的等級上,則M=1。
表3 為不同方法在11 個網(wǎng)絡(luò)上的M 值,KDN 方法在7個網(wǎng)絡(luò)中的M值最高,在其他4個網(wǎng)絡(luò)中KDN方法的M值和最高的M值接近。圖4為不同方法top節(jié)點的M 值變化曲線圖,從圖中可以看出KDN 方法不僅對于少部分關(guān)鍵節(jié)點重要性的區(qū)分效果顯著,對所有節(jié)點重要性的區(qū)分能力也有著明顯的優(yōu)勢。綜上所述,KDN方法對于節(jié)點重要性的區(qū)分能力較好。
表3 不同方法在11個網(wǎng)絡(luò) 中的M值Table 3 M values obtained by different methods on 11 complex networks
圖4 不同方法top節(jié)點的M值變化曲線Fig.4 M values curve of top nodes with different methods
此外,為了更直觀地展示不同方法的區(qū)分能力。圖5顯示了不同方法在Train網(wǎng)絡(luò)、USAir97網(wǎng)絡(luò)、Netscience網(wǎng)絡(luò)和Email網(wǎng)絡(luò)中節(jié)點等級數(shù)量以及每個等級占據(jù)節(jié)點數(shù)的頻率分布。KDN 方法在4 個網(wǎng)絡(luò)中提供的排名包含更多等級,而每個等級所涵蓋的節(jié)點數(shù)量又低于其他方法,這表明KDN方法可以更好地區(qū)分節(jié)點的重要性。
圖5 同方法的等級頻次分布圖Fig.5 Graded frequency distribution offered by different methods
關(guān)鍵節(jié)點識別的準確性直接反映方法的性能,是最重要的指標之一。為了驗證KDN方法對節(jié)點重要性識別的準確性,本實驗將每個方法得到的節(jié)點重要性排序結(jié)果與經(jīng)過SIR模擬得到的排序結(jié)果進行比較,并計算對應(yīng)的Kendall系數(shù)值[25-26]。
(1)SIR感染模型
在SIR 模型中[19-22],網(wǎng)絡(luò)中的每個節(jié)點可能處于三種不同的狀態(tài):易感狀態(tài)(susceptible state),即健康狀態(tài),該狀態(tài)節(jié)點有一定概率被疾病傳播所感染;感染狀態(tài)(infected state),處于該狀態(tài)的節(jié)點具有感染能力,可以感染易感態(tài)節(jié)點;恢復(fù)狀態(tài)(recovered state),該狀態(tài)表示感染狀態(tài)節(jié)點已經(jīng)從感染狀態(tài)下恢復(fù),不再具有感染能力。
在SIR傳播模型初期,網(wǎng)絡(luò)中僅有一個節(jié)點處于感染狀態(tài),其余節(jié)點均處于易感狀態(tài)。在每個時間步長中,感染節(jié)點以一定的感染概率β對其周圍鄰居節(jié)點進行感染,使其進入感染狀態(tài),隨后該節(jié)點會轉(zhuǎn)變?yōu)榛謴?fù)狀態(tài),而處于恢復(fù)狀態(tài)的節(jié)點則不再被感染。該過程一直持續(xù),直到網(wǎng)絡(luò)中不存在任何處于感染狀態(tài)的節(jié)點。在SIR過程結(jié)束后,將處于恢復(fù)狀態(tài)的節(jié)點數(shù)量視為節(jié)點的傳播能力,并通過重復(fù)此過程計算每個節(jié)點的傳播能力,從大到小排序后得出SIR 排序列表。在SIR 傳播過程中,β的取值和網(wǎng)絡(luò)的傳播閾值βth有關(guān),當β大于βth,疾病可以在網(wǎng)絡(luò)中大范圍傳播;當β較小,疾病只能在小范圍內(nèi)傳播[27],流行閾值βth的計算公式如下:
(2)準確性評價
在SIR 過程中,當 |E|<100 時,將SIR 過程重復(fù)進行10 000次;當100<|E|<10 000,將SIR過程重復(fù)執(zhí)行1 000 次;當 |E|>10 000 時,將SIR 過程重復(fù)進行100次[27]。將SIR排序結(jié)果與其他排序方法的結(jié)果做比較,計算得到Kendall 系數(shù)值來度量它們之間的相關(guān)性。Kendall 系數(shù)越大,說明與SIR 排序結(jié)果相關(guān)性越高,即方法的識別結(jié)果具有更高的準確性。Kendall相關(guān)系數(shù)τ的定義如下:
其中,X和Y分別表示兩個排序列表,nc表示排序列表中一致對的數(shù)目,nd表示排序列表中非一致對的數(shù)目,n為排序列表中包含的元素數(shù)。
表4為不同方法與SIR模擬結(jié)果對比得到的Kendall系數(shù)值,表中β為網(wǎng)絡(luò)的感染率。在11個網(wǎng)絡(luò)中,KDN方法的Kendall 系數(shù)值在所有方法中均最高,識別結(jié)果具有更高的準確性。
表4 不同方法的排序列表和SIR排序列表的Kendall系數(shù)值Table 4 Kendall coefficient values of ranking lists of different methods and SIR ranking lists
在接下來的實驗中,通過改變感染率β,在Karate網(wǎng)絡(luò)、Dolphins 網(wǎng)絡(luò)、Netscience 網(wǎng)絡(luò)和Euroroad 網(wǎng)絡(luò)中進行SIR 模擬,以驗證KDN 方法識別關(guān)鍵節(jié)點的準確性,通過使用Kendall 系數(shù)值比較不同方法與不同感染率下SIR的排序結(jié)果。圖6為不同方法得到的排序結(jié)果與不同感染率下SIR排序結(jié)果之間的Kendall系數(shù)變化情況,βth在圖中用虛線進行表示。在βth附近,KDN方法在四個網(wǎng)絡(luò)中的Kendall 系數(shù)值均高于其他方法,因此KDN方法對于關(guān)鍵節(jié)點的識別具有較高的準確性。
圖6 不同 方法排序結(jié)果與SIR排序結(jié)果的Kendall變化曲線Fig6 Cauve of viaion of Kendall coefficient between ranking results obtained by different methods and SIR ranking results
Kendall相關(guān)系數(shù)實驗考慮了網(wǎng)絡(luò)中所有節(jié)點的排名。然而,關(guān)鍵節(jié)點通常關(guān)注小部分數(shù)量節(jié)點,因此在接下來的實驗中,使用排序相似函數(shù)(ranking similarity function,F(xiàn)(L))[28]來評估KDN 方法對于前r位節(jié)點排名的準確性。排序相似函數(shù)通過式(11)進行計算:
其中,L(r)和L'(r)表示在各自排序列表中的前r個節(jié)點。
如圖7 所示,KDN 方法在USAir97 網(wǎng)絡(luò)、Email 網(wǎng)絡(luò)、Euroroad網(wǎng)絡(luò)和Hamsterster網(wǎng)絡(luò)中始終保持較高的排序相似函數(shù)值,證明該方法對于前r個節(jié)點的排序列表具有較高的精確度,進一步說明KDN 方法識別關(guān)鍵節(jié)點的準確性優(yōu)于其他方法。
圖7 前r個節(jié)點的排序相似函數(shù)變化曲線Fig.7 Curve of variation of ranking similarity function on top rnodes
為了評價KDN 方法的時間性能,本文對不同方法在不同網(wǎng)絡(luò)中的運行時間進行了比較。計算機配置為Intel Core i5-8250U@1.80 GHz、8 GB RAM,64 位Windows10 系統(tǒng),在此電腦上運行了Python 3.10 環(huán)境下的實驗程序。
在不同網(wǎng)絡(luò)上進行100 次重復(fù)實驗并計算平均時間得出運行時間,結(jié)果如表5 所示。DC 方法僅考慮節(jié)點鄰居節(jié)點的數(shù)目,雖然運行時間很短,但識別的準確性和區(qū)分度較低,因此不關(guān)注該方法的時間性能。Kshell方法原理簡單,計算復(fù)雜度僅為O(n),但不能區(qū)分同層節(jié)點的重要性。除K-shell方法與Cnc+方法,KDN方法在不同網(wǎng)絡(luò)上的運行時間最短,具有較好的時間性能。
表5 11個網(wǎng)絡(luò)中不同方法的運行時間Table 5 Running times of different methods on 11 networks 單位:s
圖8為不同方法在6個網(wǎng)絡(luò)中運行時間結(jié)果圖。KDN方法的運行時間明顯低于MDD方法、BC方法、CC方法和LGI方法,略高于K-shell方法和Cnc+方法。其中BC方法和CC方法考慮整個網(wǎng)絡(luò)的路徑信息,運行時間明顯高于其他方法。綜合考慮,KDN方法在時間指標方面表現(xiàn)出良好的性能。
圖8 不同方法在6個網(wǎng)絡(luò)中的運行時間Fig.8 Running times of different methods on six networks
精準識別復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點一直是復(fù)雜網(wǎng)絡(luò)領(lǐng)域的研究熱點。本文通過綜合考慮節(jié)點的全局信息和局部信息,提出了一種基于鄰域K-shell分布的關(guān)鍵節(jié)點識別方法,并在11個網(wǎng)絡(luò)數(shù)據(jù)集上進行實驗驗證。結(jié)果表明,所提方法的識別結(jié)果在11個網(wǎng)絡(luò)數(shù)據(jù)集上均取得了最高的準確性,并且具有良好的區(qū)分度和時間性能。在當前大多數(shù)網(wǎng)絡(luò)都是動態(tài)變化的背景下,如何進一步利用節(jié)點位置信息和結(jié)構(gòu)特點來評估動態(tài)網(wǎng)絡(luò)中節(jié)點的重要性將是未來的一個重要研究方向。