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

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

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

1 引 言

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

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

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

2 加權K-階傳播數模型

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

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

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

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

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

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

此外,基于假設1和3可以得到以vi為傳染源,傳播了時長K后網絡中已感染者的數量為

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

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

其中

3 典型網絡的節(jié)點重要性

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

3.1 WS小世界網絡

圖1 隨機生成的100節(jié)點WS小世界網絡 (a)網絡結構;(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.

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

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

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

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

由前文所述,節(jié)點95和53,31和72之間的長程連接提高了網絡的連通性,若移除上述任一節(jié)點,網絡的特征路徑長度將大為增加,因此加權K-階傳播數法認為以上四個節(jié)點的重要性最高是較為合理的.由于該網絡是基于最近鄰耦合網絡構造的,而最近鄰耦合網絡中每個節(jié)點與其鄰近的左右兩側各兩個節(jié)點相連.因此,與95,53,31,72距離相近的左右各兩個節(jié)點的重要性應當相似,且距離95,53,31,72越遠,節(jié)點的重要性越低.例如,移除91,92,99或98中的任一節(jié)點對網絡結構造成的影響是相似的;此外,同時移除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é)點進行短程通信,或經由31向72等節(jié)點進行長程通信,均需要依賴節(jié)點32,因此其重要性應當較高.最后,35,36,37,38等節(jié)點進行長短程通信時需要依賴33或34;對35,37等奇數節(jié)點而言,通過33或34進行通信的效果相同,但對36,38等偶數節(jié)點而言,通過34進行通信的效率更高,可見34的重要性大于33,這也可以解釋圖2(c)中36的重要性略高于35等現象.

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

圖2 基于加權K-階傳播數法的WS小世界網絡節(jié)點重要性結果 (a)K-階結構熵;(b)權重系數;(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的重要性最低,而加權K-階傳播數法卻認為33和96的重要性較高.由前文分析可知,雖然在33節(jié)點移除后,網絡的長短程通信不會受到顯著影響,但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的重要性應當是相似的;度中心性、Ren法、Chen法、Katz指標、PageRank算法和CI法,尤其是K-核分解法對節(jié)點的排序并不細致,存在節(jié)點重要性相同的情況;此外,介數中心性認為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é)點,均缺乏較為合理的解釋.可見,加權K-階傳播數法對網絡通信的刻畫更為細致,節(jié)點重要性的評估優(yōu)于以上傳統(tǒng)方法.

3.2 海豚網絡

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

表2列出了基于加權K-階傳播數法、Ren法、Chen法、介數中心性、特征向量法、Katz指標(權重衰減因子為1.5倍鄰接矩陣最大特征值的倒數)、PageRank算法(阻尼系數0.85)、CI法(權重系數取0.5)得出的前15個重要節(jié)點的排序結果.由于度中心性和K-核分解法存在節(jié)點重要性相等的情況,其排序結果未在表2列出.其中,基于度中心性法得到的節(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法不同,加權K-階傳播數法認為節(jié)點37相對重要,排在第7位.文獻[27]將該海豚網絡劃分成了若干小社區(qū),指出37號海豚曾消失了一段時間,此時不同海豚社區(qū)間的互動受到了限制,當37號海豚再次出現時,社區(qū)又恢復了普遍聯(lián)系,Lusseau等[27]指出37號海豚是社區(qū)間信息交流的關鍵個體.因此,加權K-階傳播數法認為節(jié)點37相對重要的結論是較為合理的.然而,37號海豚處于社區(qū)邊緣,因此介數中心性認為節(jié)點37重要性最高的結論是值得商榷的.

圖3 基于若干傳統(tǒng)算法的WS小世界網絡節(jié)點重要性評價結果 (a)度中心性;(b)Ren法;(c)Chen法;(d)介數中心性;(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.

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

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

圖4 基于加權K-階傳播數法的海豚網絡節(jié)點重要性結果 (a)K-階結構熵;(b)權重系數;(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 海豚網節(jié)點重要性排序結果Table 2.Node importance ordering result of the dolphin network.

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

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

圖5 K-階結構熵 (a)美國西部電網;(b)芝加哥公路網絡;(c)科學家合作網絡;(d)小鼠神經纖維束網絡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.

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

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

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

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

圖6 網絡效率下降率ε隨攻擊次數的變化情況 (a)美國西部電網;(b)芝加哥公路網絡;(c)網絡科學家合著網絡;(d)小鼠神經纖維束網絡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é)點數γ隨攻擊次數的變化情況 (a)美國西部電網;(b)芝加哥公路網絡;(c)網絡科學家合著網絡;(d)小鼠神經纖維束網絡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.

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

4 結 論

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