基于加權(quán)K-階傳播數(shù)的節(jié)點重要性*

黃麗亞 湯平川 霍宥良 鄭義 成謝鋒2)

1)(南京郵電大學(xué),電子與光學(xué)工程學(xué)院,微電子學(xué)院,南京 210023)

2)(射頻集成與微組裝技術(shù)國家地方聯(lián)合工程實驗室,南京 210003)

1 引 言

復(fù)雜網(wǎng)絡(luò)是現(xiàn)實系統(tǒng)的抽象表達.網(wǎng)絡(luò)節(jié)點依靠邊相互聯(lián)系,通常存在著重要性差異.節(jié)點重要性是分析設(shè)計網(wǎng)絡(luò)結(jié)構(gòu)、提升系統(tǒng)魯棒性等研究的重要基礎(chǔ)[1-3].目前,已有諸多研究各自從不同的角度提出了節(jié)點重要性評價指標.

度中心性法[4]認為節(jié)點擁有的鄰居數(shù)越多,其直接影響力越強.對食物鏈網(wǎng)絡(luò)[5]、P2P網(wǎng)絡(luò)[6]、電子郵件網(wǎng)絡(luò)[7]以及蛋白質(zhì)網(wǎng)絡(luò)[8]的研究指出,當度值較大的節(jié)點被移除后,網(wǎng)絡(luò)結(jié)構(gòu)將變得更加脆弱.此外,度中心性法計算簡便,其時間復(fù)雜度為O(N),適用于網(wǎng)絡(luò)規(guī)模較大的情況.然而,度中心性法未考慮非鄰居節(jié)點的影響,利用的信息較為有限,不能充分地反映網(wǎng)絡(luò)的全局特性和橋連接節(jié)點的重要性.任卓明等[9]在度中心性法的基礎(chǔ)上,將鄰居節(jié)點相互連接的緊密程度,即局部聚類系數(shù)也納入了評價體系(下文簡稱Ren法),結(jié)果雖優(yōu)于度中心性法,但其反映網(wǎng)絡(luò)全局特性的能力仍然有限.此外,Ren法利用趨同化函數(shù)將度與聚類系數(shù)處理后直接加和,并未設(shè)置比例系數(shù),即該方法認為二者同等重要,其合理性有待商榷.為了更充分地利用網(wǎng)絡(luò)結(jié)構(gòu)信息,Chen等[10]提出了一種基于多級鄰居信息指標的半局部中心測度的方法(下文簡稱Chen法),首先確定節(jié)點的一級重要性為最近鄰與次近鄰節(jié)點的個數(shù)之和,再計算節(jié)點的二級重要性為所有鄰居節(jié)點的一級重要性之和,最后定義節(jié)點的三級重要性為所有鄰居節(jié)點的二級重要性之和,并作為最終的重要性評價指標.但為了保證較低的算法復(fù)雜度,Chen法僅將分析范圍擴展到了次近鄰節(jié)點,因而對網(wǎng)絡(luò)全局特性的挖掘也并非十分充分.介數(shù)中心性[11]指網(wǎng)絡(luò)中所有最短路徑通過某節(jié)點的占比,是節(jié)點對網(wǎng)絡(luò)傳播信息的影響或?qū)?jié)點預(yù)期負載的度量.緊密度[12,13]指由某節(jié)點出發(fā),到達其余節(jié)點的最短路徑的和的倒數(shù),是將信息從給定節(jié)點傳播到網(wǎng)絡(luò)中其他可達節(jié)點的時間的度量.介數(shù)中心性與緊密度雖提高了對橋節(jié)點的重視程度,但需要計算任意一對節(jié)點之間的最短路徑,其時間復(fù)雜度為O(N3),不適用于大型網(wǎng)絡(luò),且對隨機網(wǎng)絡(luò)的解釋也不夠充分.特征向量法[14,15]將網(wǎng)絡(luò)鄰接矩陣最大特征值對應(yīng)特征向量的元素作為各個節(jié)點的重要性指標,本質(zhì)上是將單個節(jié)點的拓撲性質(zhì)線性疊加,結(jié)果較為片面.Katz[16]認為節(jié)點的重要性正比于網(wǎng)絡(luò)鄰接矩陣A的冪級數(shù)與單位陣E的差的各列元素之和,其中α為權(quán)重衰減因子.Katz指標雖充分利用了網(wǎng)絡(luò)的全局特性,但α卻無法定量計算,只能根據(jù)不同的網(wǎng)絡(luò)進行人為設(shè)置,且該方法還認為節(jié)點影響力隨路徑的增加呈指數(shù)形式衰減,較為主觀.此外,現(xiàn)實世界中的網(wǎng)絡(luò)均是有限的,而Katz指標為了得到收斂形式,使路徑長度取值無窮大,其結(jié)果包含了大量的冗余信息.為了解決Katz指標存在的問題,Zhang等[17]以網(wǎng)絡(luò)節(jié)點為變量,將其余所有節(jié)點對當前節(jié)點的影響力進行加和,并假設(shè)節(jié)點的影響力隨路徑的增加呈高斯形式衰減.該方法在一定程度上解決了Katz指標的信息冗余等問題,但節(jié)點影響力的衰減形式仍較為主觀.K-核分解法[18,19]試圖遞歸地移去網(wǎng)絡(luò)中度中心性的值小于等于K的節(jié)點,其時間復(fù)雜度為O(N),相比于度中心性、介數(shù)等指標更能反映諸如演員網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等實際網(wǎng)絡(luò)的節(jié)點重要性.但K-核分解法對節(jié)點的排序并不細致,常常賦予大量節(jié)點相同的重要度,不適合于樹狀網(wǎng)絡(luò)和無標度網(wǎng)絡(luò)的分析.PageRank算法[20]認為節(jié)點的重要性與隨機瀏覽者訪問的頻率成正比,被廣泛地應(yīng)用在了網(wǎng)頁排名等領(lǐng)域,但該算法對含孤立節(jié)點或社團結(jié)構(gòu)的網(wǎng)絡(luò)會出現(xiàn)重要性排序不唯一等問題.為了解決該弊端,Lü等[21]提出了LeaderRank算法,在原始網(wǎng)絡(luò)的基礎(chǔ)上,增加了一個與所有節(jié)點雙向連接的Ground節(jié)點.這一操作使網(wǎng)絡(luò)變?yōu)閺娺B通的,其結(jié)果比PageRank算法更加準確,但LeaderRank算法不適用于無向網(wǎng)絡(luò).Zhong等[22]利用網(wǎng)絡(luò)節(jié)點被移除前后流行閾值的差來表征節(jié)點的全局重要性,并利用度中心性來表征節(jié)點的局部重要性,最后將歸一化后的全局和局部重要性結(jié)果進行加權(quán)求和(下文簡稱CI法),并利用美國航空網(wǎng)絡(luò)等九個真實網(wǎng)絡(luò)證明了CI法的有效性.然而CI法中全局和局部重要性的加權(quán)系數(shù)對最終結(jié)果的影響較大.雖然文獻[22]經(jīng)仿真分析歸納指出當加權(quán)系數(shù)近似為0.5時得到的節(jié)點重要性結(jié)果較好,但缺乏更為深入的理論證明.此外,CI法為何選擇度中心性而非其他局部重要性指標有待進一步說明.

以上方法均存在各自的不足,本研究將提出一種新的節(jié)點重要性評價方法,即加權(quán)K-階傳播數(shù)法,并試圖利用WS (Watts-Strogatz)小世界網(wǎng)絡(luò)、海豚網(wǎng)絡(luò)、美國西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)以及小鼠神經(jīng)纖維束網(wǎng)絡(luò)進行仿真分析,以證明該方法的有效性.

2 加權(quán)K-階傳播數(shù)模型

SI (susceptible-infective),SIS (susceptibleinfective-susceptible)和SIR (susceptible-infectiveremoved)等模型[23]被廣泛地應(yīng)用在疾病以及信息傳播等領(lǐng)域,最初均是對某地區(qū)疾病傳播過程的抽象.其中,個體能否恢復(fù)健康和是否具有免疫力是造成上述模型差異的重要因素.SI和SIS模型假設(shè)個體不具備免疫力,將人群分為易感染者和已感染者兩類.此外,SI模型認為個體一旦被傳染便永久處于已感染狀態(tài),而SIS模型則認為個體被傳染后將以一定概率恢復(fù)為易感狀態(tài),并會被再次傳染.SIR模型假設(shè)已感染者可被治愈且將具有終身性的免疫力,將人群分為易感染者、已感染者和免疫移出者三類.然而,以上模型均假設(shè)疾病傳播為隨機接觸,并未考慮個體間的拓撲關(guān)系.受上述模型啟發(fā),本文將結(jié)合復(fù)雜網(wǎng)絡(luò)對已感染者無法恢復(fù)健康且不具有免疫力的最為簡單的疾病傳播過程進行抽象,最終得到加權(quán)K-階傳播數(shù)法來評價節(jié)點的重要性,描述如下.

首先給定無向網(wǎng)絡(luò)圖G(V,E),其中,V={v1,v2,···,vn}為節(jié)點集,共n個節(jié)點,代表個體;E為邊集,eij表示節(jié)點vi與vj之間的邊.這里假設(shè)疾病傳播過程中該網(wǎng)絡(luò)的結(jié)構(gòu)不會發(fā)生變化,且已感染者只能傳染給與其直接接觸的易感染者.現(xiàn)假設(shè)某節(jié)點vi為已感染者,與其相鄰的易感染者集合記為Γ(vi).對節(jié)點vj∈ Γ(vi)而言,vi將以一定概率 0≤pij≤1 向vj傳播 疾病.同時,vi向vj傳播疾病需要耗費一定時間tij,通常受到邊eij的影響.若除vi外,vj同時受到其他相鄰的已感染者的傳播,還需進行綜合考量.以上描述考慮到了節(jié)點間疾病傳播的概率以及耗時等因素,但若網(wǎng)絡(luò)邊是無權(quán)的,且不考慮節(jié)點以及邊的意義,則可進一步抽象,作出以下假設(shè)：

1)已感染者會向其相鄰的所有易感染者傳播疾病;

2)已感染者向其相鄰的易感染者傳播疾病的耗時相等,并設(shè)為1;

3)易感染者一旦受到其任一相鄰的已感染者的傳播,便轉(zhuǎn)化為已感染者.

在衡量節(jié)點的重要性時,較為常用的方法是分別將各個節(jié)點設(shè)置為傳染源進行疾病傳播,并以網(wǎng)絡(luò)中所有節(jié)點被轉(zhuǎn)化為已感染者的總耗時作為節(jié)點重要性的評價指標,總耗時越少,則證明節(jié)點越重要.然而,當網(wǎng)絡(luò)非連通時,從不同節(jié)點出發(fā)最終能夠傳播到的節(jié)點總數(shù)未必相同.為了保證一致性,另一種節(jié)點重要性衡量方法仍是將各個節(jié)點設(shè)置為傳染源,但比較的是在經(jīng)歷相同的傳播時長K后網(wǎng)絡(luò)中已感染者的數(shù)量,數(shù)量越大則證明該節(jié)點越重要.基于假設(shè)2可將傳播時長K取值離散,并規(guī)定為非負整數(shù),這與SI等模型中時間取值連續(xù)的假設(shè)略有不同.其中,當K=0 時可認為只有傳染源節(jié)點已被感染,但尚未開始傳播.

此外,基于假設(shè)1和3可以得到以vi為傳染源,傳播了時長K后網(wǎng)絡(luò)中已感染者的數(shù)量為

傳播時長K的取值是影響節(jié)點重要性評價結(jié)果的關(guān)鍵.文獻[24]利用并基于信息熵定義了K-階結(jié)構(gòu)熵HK,衡量了網(wǎng)絡(luò)的異構(gòu)性：

結(jié)構(gòu)熵HK取值越小,網(wǎng)絡(luò)的異構(gòu)性越強,并以結(jié)構(gòu)熵序列為依據(jù)研究了WS小世界、BA無標度等網(wǎng)絡(luò)的異構(gòu)性.若從疾病傳播的角度出發(fā),可認為HK取值越大,以各個節(jié)點{v1,v2,·· ·,vn}分別作為傳染源的網(wǎng)絡(luò)K-階傳播數(shù)之間的差異越小,即可認為各節(jié)點重要性的差異越小,反之差異越大.若僅僅以某單一傳播時長下網(wǎng)絡(luò)中已感染者的數(shù)量來衡量節(jié)點的重要性,可能會遺漏其他傳播時長下的有用信息.因此,本文將對K取從0至d間的所有時刻進行綜合考察,定義節(jié)點vi的重要性Qvi為

其中

3 典型網(wǎng)絡(luò)的節(jié)點重要性

為了驗證加權(quán)K-階傳播數(shù)法在節(jié)點重要性評估方面的優(yōu)勢,本文將利用WS小世界網(wǎng)絡(luò)、海豚網(wǎng)絡(luò)、美國西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)以及小鼠神經(jīng)纖維束網(wǎng)絡(luò)進行仿真分析.

3.1 WS小世界網(wǎng)絡(luò)

圖1 隨機生成的100節(jié)點WS小世界網(wǎng)絡(luò) (a)網(wǎng)絡(luò)結(jié)構(gòu);(b)邊31-33被改連至邊31-72;(c)邊95-96被改連至邊95-53Fig.1.A random WS small-world network with 100 nodes：(a)Network structure;(b)the edge 31-33 is rescheduled to the edge 31-72;(c)the edge 95-96 is rescheduled to the edge 95-53.

小世界網(wǎng)絡(luò)是指同時具有較短特征路徑長度以及較大平均聚類系數(shù)的一種網(wǎng)絡(luò)類型.Watts和Strogatz[25]最早提出了一種構(gòu)造小世界網(wǎng)絡(luò)的方法,即將最近鄰耦合網(wǎng)絡(luò)中的邊依概率進行隨機重連,通常將這種網(wǎng)絡(luò)稱為WS小世界網(wǎng)絡(luò).圖1(a)基于100節(jié)點最近鄰耦合網(wǎng)絡(luò)隨機生成了一個WS小世界網(wǎng)絡(luò),該最近鄰耦合網(wǎng)絡(luò)中每個節(jié)點與其鄰近的左右兩側(cè)各兩個節(jié)點相連.在隨機重連后,邊31-33和95-96分別被改連為31-72和95-53,見圖1(b)和圖1(c),其余邊的位置不變.

表1列出了該WS小世界網(wǎng)絡(luò)與同規(guī)模隨機網(wǎng)絡(luò)的平均聚類系數(shù)、特征路徑長度等參數(shù).可見,該網(wǎng)絡(luò)的特征路徑長度為隨機網(wǎng)絡(luò)的2.49倍,但其平均聚類系數(shù)為隨機網(wǎng)絡(luò)的近20倍,這是由于邊31-72和95-53的長程連接提高了網(wǎng)絡(luò)的連通性.

表1 WS小世界網(wǎng)絡(luò)以及同規(guī)模隨機網(wǎng)絡(luò)的網(wǎng)絡(luò)參數(shù)Table 1.Network features of the WS small-world network and random networks.

現(xiàn)利用加權(quán)K-階傳播數(shù)法對該網(wǎng)絡(luò)節(jié)點的重要性進行分析.圖2(a)為網(wǎng)絡(luò)的K-階結(jié)構(gòu)熵HK,圖2(b)為權(quán)重系數(shù)cK,圖2(c)為歸一化的節(jié)點重要性.此外,圖2(c)中的小圖按色度對重要性進行了標注.

由前文所述,節(jié)點95和53,31和72之間的長程連接提高了網(wǎng)絡(luò)的連通性,若移除上述任一節(jié)點,網(wǎng)絡(luò)的特征路徑長度將大為增加,因此加權(quán)K-階傳播數(shù)法認為以上四個節(jié)點的重要性最高是較為合理的.由于該網(wǎng)絡(luò)是基于最近鄰耦合網(wǎng)絡(luò)構(gòu)造的,而最近鄰耦合網(wǎng)絡(luò)中每個節(jié)點與其鄰近的左右兩側(cè)各兩個節(jié)點相連.因此,與95,53,31,72距離相近的左右各兩個節(jié)點的重要性應(yīng)當相似,且距離95,53,31,72越遠,節(jié)點的重要性越低.例如,移除91,92,99或98中的任一節(jié)點對網(wǎng)絡(luò)結(jié)構(gòu)造成的影響是相似的;此外,同時移除99和98相較同時移除100和1,會有更多的節(jié)點難以通過95進行長程通信,因此99和98的重要性高于100和1是較為合理的.值得注意的是,圖2(c)中97的重要性顯著高于96,這是由于邊96-95被斷開,若依賴96進行長程通信需要借助邊95-94,而97與95直接相連,因此通過97進行長程通信更為便捷.此外,由于邊33-31被斷開,33,34,35等節(jié)點向30,29,28等節(jié)點進行短程通信,或經(jīng)由31向72等節(jié)點進行長程通信,均需要依賴節(jié)點32,因此其重要性應(yīng)當較高.最后,35,36,37,38等節(jié)點進行長短程通信時需要依賴33或34;對35,37等奇數(shù)節(jié)點而言,通過33或34進行通信的效果相同,但對36,38等偶數(shù)節(jié)點而言,通過34進行通信的效率更高,可見34的重要性大于33,這也可以解釋圖2(c)中36的重要性略高于35等現(xiàn)象.

為了進一步證明加權(quán)K-階傳播數(shù)法的有效性,圖3繪制了度中心性、Ren法、Chen法、介數(shù)中心性、特征向量法、Katz指標(權(quán)重衰減因子取1.5倍鄰接矩陣最大特征值的倒數(shù))、PageRank算法(阻尼系數(shù)取0.85)以及CI法(權(quán)重系數(shù)取0.5)得出的節(jié)點重要性結(jié)果.由于K-核分解法得到的所有節(jié)點的重要性相同,因此其結(jié)果未在圖3給出.

圖2 基于加權(quán)K-階傳播數(shù)法的WS小世界網(wǎng)絡(luò)節(jié)點重要性結(jié)果 (a)K-階結(jié)構(gòu)熵;(b)權(quán)重系數(shù);(c)節(jié)點重要性Fig.2.Node importance of the WS small-world network based on the weightedK-order propagation number algorithm：(a)TheK-order structure entropy;(b)the weight coefficient;(c)the importance of nodes.

由圖3可知,以上方法認為33或96的重要性最低,而加權(quán)K-階傳播數(shù)法卻認為33和96的重要性較高.由前文分析可知,雖然在33節(jié)點移除后,網(wǎng)絡(luò)的長短程通信不會受到顯著影響,但27,28,29等節(jié)點與34,35,36等節(jié)點間的短程通信,或34,35,36等節(jié)點依靠31進行長程通信只能依賴邊32-34進行;同樣,當96被移除后,邊95-97將參與所有通信,可見33和96的存在降低了其余重要節(jié)點或邊的負載,起到了分流的作用,因此認為33或96在所有節(jié)點中重要性最低是值得商榷的;度中心性、特征向量法、Katz指標、PageRank算法和CI法認為72和53的重要性遠高于31和95,但長程通信需要同時依賴以上4個節(jié)點進行,因此節(jié)點31和72或95和53的重要性應(yīng)當是相似的;度中心性、Ren法、Chen法、Katz指標、PageRank算法和CI法,尤其是K-核分解法對節(jié)點的排序并不細致,存在節(jié)點重要性相同的情況;此外,介數(shù)中心性認為10,11,12等節(jié)點的重要性高于52,54,71,73等節(jié)點,49,51,55,57,74,76等節(jié)點的重要性高于50,52,54,56,73,75等節(jié)點,PageRank算法認為61,62,63等節(jié)點的重要性高于52,54,71,73等節(jié)點,均缺乏較為合理的解釋.可見,加權(quán)K-階傳播數(shù)法對網(wǎng)絡(luò)通信的刻畫更為細致,節(jié)點重要性的評估優(yōu)于以上傳統(tǒng)方法.

3.2 海豚網(wǎng)絡(luò)

為了進一步驗證加權(quán)K-階傳播數(shù)法的有效性,本文以海豚網(wǎng)絡(luò)為例進行研究.Lusseau等[26,27]對新西蘭道特富爾峽灣(Doubtful Sound)62只寬吻海豚進行研究并構(gòu)建了海豚社會網(wǎng)絡(luò).基于加權(quán)K-階傳播數(shù)法的海豚網(wǎng)絡(luò)節(jié)點重要性結(jié)果如圖4所示,圖4(a)為網(wǎng)絡(luò)的K-階結(jié)構(gòu)熵HK,圖4(b)為權(quán)重系數(shù)cK,圖4(c)為歸一化后的節(jié)點重要性.網(wǎng)絡(luò)中節(jié)點代表海豚,邊表示海豚間的相關(guān)接觸.

表2列出了基于加權(quán)K-階傳播數(shù)法、Ren法、Chen法、介數(shù)中心性、特征向量法、Katz指標(權(quán)重衰減因子為1.5倍鄰接矩陣最大特征值的倒數(shù))、PageRank算法(阻尼系數(shù)0.85)、CI法(權(quán)重系數(shù)取0.5)得出的前15個重要節(jié)點的排序結(jié)果.由于度中心性和K-核分解法存在節(jié)點重要性相等的情況,其排序結(jié)果未在表2列出.其中,基于度中心性法得到的節(jié)點重要性排序結(jié)果(前20個重要節(jié)點)為15 ＞ 38=46 ＞ 34=52 ＞ 18=21=30=58 ＞ 2=14=39=41 ＞ 10=16=19=37=44=51=55;K-核分解法認為1,2,7,8,9等37個節(jié)點的重要性最高且相等.

與度中心性、Ren法、Chen法、特征向量法、Katz指標、PageRank算法和CI法不同,加權(quán)K-階傳播數(shù)法認為節(jié)點37相對重要,排在第7位.文獻[27]將該海豚網(wǎng)絡(luò)劃分成了若干小社區(qū),指出37號海豚曾消失了一段時間,此時不同海豚社區(qū)間的互動受到了限制,當37號海豚再次出現(xiàn)時,社區(qū)又恢復(fù)了普遍聯(lián)系,Lusseau等[27]指出37號海豚是社區(qū)間信息交流的關(guān)鍵個體.因此,加權(quán)K-階傳播數(shù)法認為節(jié)點37相對重要的結(jié)論是較為合理的.然而,37號海豚處于社區(qū)邊緣,因此介數(shù)中心性認為節(jié)點37重要性最高的結(jié)論是值得商榷的.

圖3 基于若干傳統(tǒng)算法的WS小世界網(wǎng)絡(luò)節(jié)點重要性評價結(jié)果 (a)度中心性;(b)Ren法;(c)Chen法;(d)介數(shù)中心性;(e)特征向量法;(f)Katz指標法;(g)PageRank算法;(h)CI法Fig.3.Node importance of the WS small-world network based on some traditional algorithms：(a)Degree centrality;(b)Ren method;(c)Chen method;(d)betweenness centrality;(e)eigenvector method;(f)Katz index;(g)PageRank;(h)CI method.

此外,加權(quán)K-階傳播數(shù)法提高了對節(jié)點2和21的重視程度,分別排在第11和第4位,而2和21處于各自海豚社區(qū)偏中心位置,又與37等負責(zé)信息交流的節(jié)點直接相連,因此該結(jié)論是較為合理的;Ren法、Chen法、特征向量法、Katz指標法和CI法認為節(jié)點22相對重要,但該節(jié)點的度中心性與介數(shù)均是較低的;最后,度中心性法和K-核分解法存在節(jié)點重要性相同的情況,排序不細致.可見,加權(quán)K-階傳播數(shù)法在評價海豚網(wǎng)絡(luò)節(jié)點重要性時適當?shù)靥岣吡藢ｋ嗌鐓^(qū)間信息交流起到關(guān)鍵作用的節(jié)點的重視程度,結(jié)果更為合理.

3.3 基于節(jié)點重要性的蓄意攻擊研究

圖4 基于加權(quán)K-階傳播數(shù)法的海豚網(wǎng)絡(luò)節(jié)點重要性結(jié)果 (a)K-階結(jié)構(gòu)熵;(b)權(quán)重系數(shù);(c)節(jié)點重要性Fig.4.Node importance of the dolphin network based on the weightedK-order propagation number algorithm：(a)TheK-order structure entropy;(b)the weight coefficient;(c)the importance of nodes.

表2 海豚網(wǎng)節(jié)點重要性排序結(jié)果Table 2.Node importance ordering result of the dolphin network.

為了進一步驗證加權(quán)K-階傳播數(shù)法的優(yōu)越性,本文對美國西部電網(wǎng)[25]、芝加哥公路網(wǎng)絡(luò)[28]、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)[29]以及小鼠神經(jīng)纖維束網(wǎng)絡(luò)(Kasthuri_graph_v4)[30]進行了節(jié)點重要性研究.其中美國西部電網(wǎng)共有4941個節(jié)點和6594條邊,描述了美國西部的高壓輸電電網(wǎng)結(jié)構(gòu);芝加哥公路網(wǎng)絡(luò)共有1467個節(jié)點和1298條邊,描述了美國芝加哥地區(qū)的公路運輸情況;網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)共有1589個節(jié)點和2742條邊,描述了從事網(wǎng)絡(luò)理論和實驗的科學(xué)家合著關(guān)系;小鼠神經(jīng)纖維束網(wǎng)絡(luò)共有1029個節(jié)點和1700條邊,描述了小鼠部分腦皮層中神經(jīng)元間的軸突束連接.美國西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)和網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)均是無權(quán)無向的;小鼠神經(jīng)纖維束網(wǎng)絡(luò)是有權(quán)無向的,為了適應(yīng)加權(quán)K-階傳播數(shù)法,本文忽略了該網(wǎng)絡(luò)的邊權(quán)信息.以上網(wǎng)絡(luò)的K-階結(jié)構(gòu)熵HK如圖5所示.

由于以上四個網(wǎng)絡(luò)的節(jié)點數(shù)較多,本文擬采用蓄意攻擊策略對節(jié)點重要性進行研究[31-33].蓄意攻擊策略是指基于節(jié)點重要性由高到低的排序依次攻擊網(wǎng)絡(luò),即移除與節(jié)點相連的所有邊,通過網(wǎng)絡(luò)結(jié)構(gòu)隨攻擊次數(shù)的變化情況來評價節(jié)點重要性算法的各自特點.由于在蓄意攻擊后網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生了變化,因此僅僅依據(jù)原始網(wǎng)絡(luò)的節(jié)點重要性進行研究會存在偏差.為了解決此問題,本文在每次蓄意攻擊后更新節(jié)點排序結(jié)果.此外,若存在重要性相等的情況,將選擇編號最小的節(jié)點進行攻擊.

圖5 K-階結(jié)構(gòu)熵 (a)美國西部電網(wǎng);(b)芝加哥公路網(wǎng)絡(luò);(c)科學(xué)家合作網(wǎng)絡(luò);(d)小鼠神經(jīng)纖維束網(wǎng)絡(luò)Fig.5.TheK-order structure entropy：(a)The western power grid of the United States;(b)the road transportation network of the Chicago region;(c)the co-authorship network in network science;(d)the axonal tracts network between neurons of mouse.

由于網(wǎng)絡(luò)被攻擊后可能會出現(xiàn)孤立節(jié)點,因此選用網(wǎng)絡(luò)效率來評價網(wǎng)絡(luò)的連通性.網(wǎng)絡(luò)效率的表達式為

其 中dvivj是 指 節(jié) 點vi和vj之間的最短路徑長度.由(6)式可知,e值越大,網(wǎng)絡(luò)效率越高;當網(wǎng)絡(luò)由孤立節(jié)點組成時e=0,取值最小.攻擊節(jié)點可能造成網(wǎng)絡(luò)連接通路的中斷,節(jié)點間的最短路徑將有所增大,網(wǎng)絡(luò)效率則會隨之降低.為了更為直觀地反映被攻擊后網(wǎng)絡(luò)效率的降低情況,依照文獻[9]定義網(wǎng)絡(luò)效率下降率ε為

其中e0為未被攻擊的原始網(wǎng)絡(luò)的網(wǎng)絡(luò)效率.由(7)式可見,ε的取值為[ 0,1],當網(wǎng)絡(luò)未被攻擊時ε=0,當網(wǎng)絡(luò)被攻擊時ε會隨之升高;最終,當所有的邊被刪除時網(wǎng)絡(luò)效率降至最低,此時ε=1 .此外,為了進一步分析攻擊前后網(wǎng)絡(luò)拓撲結(jié)構(gòu)的變化情況,依照文獻[33]將網(wǎng)絡(luò)最大子圖節(jié)點數(shù)設(shè)為γ.圖6和圖7分別繪制了美國西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)以及小鼠神經(jīng)纖維束網(wǎng)絡(luò)基于不同節(jié)點重要性的排序方法,其網(wǎng)絡(luò)效率下降率ε和最大子圖節(jié)點數(shù)γ隨攻擊次數(shù)的變化曲線.其中,Katz指標的權(quán)重衰減因子為1.5倍鄰接矩陣最大特征值的倒數(shù);PageRank算法的阻尼系數(shù)取0.85;CI法的權(quán)重系數(shù)取0.5.

對美國西部電網(wǎng)而言,依照加權(quán)K-階傳播數(shù)法和介數(shù)中心性法的排序結(jié)果進行攻擊,網(wǎng)絡(luò)效率下降得最為迅速,僅攻擊約100次后,網(wǎng)絡(luò)效率便下降了近90%;而依據(jù)度中心性、Ren法、Chen法、特征向量法、Katz指標、PageRank算法和CI法則需約300次,K-核分解法需約550次,才能達到同等效果.此外,基于加權(quán)K-階傳播數(shù)法和介數(shù)中心性對網(wǎng)絡(luò)進行攻擊,最大子圖節(jié)點數(shù)降低的速率遠遠高于其他方法.以加權(quán)K-階傳播數(shù)法為例,當網(wǎng)絡(luò)被攻擊200次后,最大子圖節(jié)點數(shù)僅為154,為原始網(wǎng)絡(luò)節(jié)點數(shù)的3%,可認為網(wǎng)絡(luò)基本癱瘓.而度中心性、Ren法、Chen法、特征向量法、Katz指標和CI法則需攻擊近400次,PageRank算法需650次,K-核分解法需1000次才能達到相同效果;對芝加哥公路網(wǎng)絡(luò)而言,依據(jù)加權(quán)K-階傳播數(shù)法、介數(shù)中心性、Chen法、特征向量法、Katz指標和CI法進行蓄意攻擊,網(wǎng)絡(luò)被破壞的程度較為接近,且優(yōu)于度中心性、Ren法、PageRank算法和K-核分解法.其中,依據(jù)加權(quán)K-階傳播數(shù)法進行蓄意攻擊,網(wǎng)絡(luò)效率下降得最為迅速;對網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)而言,依照加權(quán)K-階傳播數(shù)法和介數(shù)中心性進行蓄意攻擊,網(wǎng)絡(luò)被破壞的程度較為接近,且優(yōu)于其他算法;對小鼠神經(jīng)纖維束網(wǎng)絡(luò)而言,依據(jù)加權(quán)K-階傳播數(shù)法、度中心性、介數(shù)中心性、特征向量法、Katz指標、PageRank算法和CI法進行蓄意攻擊,網(wǎng)絡(luò)被破壞的程度較為接近,且優(yōu)于Ren法、Chen法和K-核分解法.其中,依據(jù)加權(quán)K-階傳播數(shù)法和介數(shù)中心性進行蓄意攻擊,網(wǎng)絡(luò)最大子圖節(jié)點數(shù)下降得最為迅速,略優(yōu)于其他算法.

圖6 網(wǎng)絡(luò)效率下降率ε隨攻擊次數(shù)的變化情況 (a)美國西部電網(wǎng);(b)芝加哥公路網(wǎng)絡(luò);(c)網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò);(d)小鼠神經(jīng)纖維束網(wǎng)絡(luò)Fig.6.Change of the network efficiency decrease rateεwith attacking times：(a)The western power grid of the United States;(b)the road transportation network of the Chicago region;(c)the co-authorship network in network science;(d)the axonal tracts network between neurons of mouse.

圖7 最大子圖節(jié)點數(shù)γ隨攻擊次數(shù)的變化情況 (a)美國西部電網(wǎng);(b)芝加哥公路網(wǎng)絡(luò);(c)網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò);(d)小鼠神經(jīng)纖維束網(wǎng)絡(luò)Fig.7.Change of the node number of the maximum sub-graphεwith attacking times：(a)The western power grid of the United States;(b)the road transportation network of the Chicago region;(c)the co-authorship network in network science;(d)the axonal tracts network between neurons of mouse.

綜上所述,無論對美國西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)還是小鼠神經(jīng)纖維束網(wǎng)絡(luò)而言,基于加權(quán)K-階傳播數(shù)法進行蓄意攻擊,僅需移除少量重要節(jié)點便可實現(xiàn)對網(wǎng)絡(luò)結(jié)構(gòu)的充分破壞.

4 結(jié) 論

本文考慮到個體間的相關(guān)關(guān)系,基于網(wǎng)絡(luò)拓撲結(jié)構(gòu)重新描述了傳染病模型,并將各個節(jié)點分別設(shè)置為傳染源進行疾病傳播,提出了加權(quán)K-階傳播數(shù)法.通過對WS小世界網(wǎng)絡(luò)的仿真分析發(fā)現(xiàn),加權(quán)K-階傳播數(shù)法相較于傳統(tǒng)的節(jié)點重要性評價指標能夠更為綜合地考量長程連接對網(wǎng)絡(luò)長、短程通信的影響;此外,加權(quán)K-階傳播數(shù)法不僅認為海豚網(wǎng)絡(luò)社區(qū)中心的重要性較高,且適當?shù)靥岣吡藢ι鐓^(qū)間的信息交流起到關(guān)鍵作用的海豚的受重視程度.最后,本文還基于蓄意攻擊策略以美國西部電網(wǎng)、芝加哥公路網(wǎng)絡(luò)、網(wǎng)絡(luò)科學(xué)家合著網(wǎng)絡(luò)以及小鼠神經(jīng)纖維束網(wǎng)絡(luò)為實例進行了研究.然而,由于目前加權(quán)K-階傳播數(shù)法的求解依賴于網(wǎng)絡(luò)鄰接矩陣的K-階多項式,需要進行K—1次矩陣乘法和K次矩陣加法,時間復(fù)雜度較高.因此需要進一步探索K-階傳播數(shù)的物理意義以提出更為便捷的求解方案.此外,小鼠神經(jīng)纖維束網(wǎng)絡(luò)原為有權(quán)網(wǎng)絡(luò),為了適應(yīng)加權(quán)K-階傳播數(shù)法,本文忽略了該網(wǎng)絡(luò)的邊權(quán)信息.因此將加權(quán)K-階傳播數(shù)法進行改進,使其適用于有向有權(quán)網(wǎng)絡(luò),也是后續(xù)研究的重點.