阮逸潤老松楊 王竣德 白亮 陳立棟

(國防科學(xué)技術(shù)大學(xué),信息系統(tǒng)工程重點實驗室,長沙 410073)(2016年9月20日收到;2016年10月14日收到修改稿)

基于領(lǐng)域相似度的復(fù)雜網(wǎng)絡(luò)節(jié)點重要度評估算法?

阮逸潤?老松楊 王竣德 白亮 陳立棟

(國防科學(xué)技術(shù)大學(xué),信息系統(tǒng)工程重點實驗室,長沙 410073)(2016年9月20日收到;2016年10月14日收到修改稿)

節(jié)點重要性度量對于研究復(fù)雜網(wǎng)絡(luò)魯棒性與脆弱性具有重要意義.大規(guī)模實際復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)往往隨著時間不斷變化,在獲取網(wǎng)絡(luò)全局信息用于評估節(jié)點重要性方面具有局限性.通過量化節(jié)點局部網(wǎng)絡(luò)拓撲的重合程度來定義節(jié)點間的相似性,提出了一種考慮節(jié)點度以及鄰居節(jié)點拓撲重合度的節(jié)點重要性評估算法,算法只需要獲取節(jié)點兩跳內(nèi)的鄰居節(jié)點信息,通過計算鄰居節(jié)點對之間的相似度,便可表征其在復(fù)雜網(wǎng)絡(luò)中的結(jié)構(gòu)重要性.基于六個經(jīng)典的實際網(wǎng)絡(luò)和一個人工的小世界網(wǎng)絡(luò),分別以靜態(tài)與動態(tài)的方式對網(wǎng)絡(luò)進行攻擊,通過對極大連通系數(shù)與網(wǎng)絡(luò)效率兩種評估指標的實驗結(jié)果對比,證明了所提算法優(yōu)于基于局域信息的度指標、半局部度指標、基于節(jié)點度及其鄰居度的W L指標以及基于節(jié)點位置的K-shell指標.

復(fù)雜網(wǎng)絡(luò),魯棒性,節(jié)點重要性,領(lǐng)域相似度

1 引 言

隨著以互聯(lián)網(wǎng)為代表的網(wǎng)絡(luò)信息技術(shù)的高速發(fā)展,人類社會的網(wǎng)絡(luò)化趨勢已十分明顯,人們的日常生活越來越多地依賴于各種復(fù)雜網(wǎng)絡(luò)系統(tǒng)安全可靠的運行.實際復(fù)雜網(wǎng)絡(luò)的無標度特性[1]與小世界特性[2],使得網(wǎng)絡(luò)中的一些特殊節(jié)點對于網(wǎng)絡(luò)的結(jié)構(gòu)和功能有著巨大的影響,我們將這些節(jié)點稱為重要節(jié)點,當(dāng)網(wǎng)絡(luò)中這部分重要節(jié)點失效時,其影響將快速波及到整個網(wǎng)絡(luò).因此,如何準確量化網(wǎng)絡(luò)節(jié)點的重要性,挖掘出其中的關(guān)鍵節(jié)點意義重大.例如,在傳染病傳播網(wǎng)絡(luò)中[3,4]對網(wǎng)絡(luò)關(guān)鍵節(jié)點進行接種免疫可有效抑制病毒傳播,預(yù)防其大規(guī)模爆發(fā);在電力網(wǎng)中,對關(guān)鍵地區(qū)電路采取預(yù)防措施,可有效避免電力網(wǎng)絡(luò)的級聯(lián)失效[5,6];在大規(guī)模路由網(wǎng)絡(luò)中,對關(guān)鍵路由節(jié)點采取有效防護措施,可有效避免路由節(jié)點遭受攻擊時對網(wǎng)絡(luò)的毀滅性破壞.

近年來,節(jié)點重要性度量是網(wǎng)絡(luò)科學(xué)研究的一個熱點,衍生出許多經(jīng)典的節(jié)點重要性排序算法,包括度排序[7]、接近中心性排序[8]、介數(shù)中心性排序[9]、特征向量排序[10],PageRank[11,12],LeaderRank[13]與H指數(shù)[14]等. 其中度(degree centrality)排序方法是一種簡單有效的局部算法,接近中心性算法與介數(shù)中心性算法需要用到網(wǎng)絡(luò)全局信息,算法時間復(fù)雜度過高,在應(yīng)用上具有局限性.Chen等[15]提出半局部中心性(semilocal centrality)指標,該指標有限地擴大了節(jié)點領(lǐng)域的覆蓋范圍,很好地平衡了算法精度與時間復(fù)雜度的關(guān)系.王建偉等[16]認為節(jié)點的重要性由節(jié)點自身及其鄰居節(jié)點的度數(shù)相關(guān)(W L centrality),即節(jié)點及其鄰居的度越大,節(jié)點重要性越高;任卓明等[17]綜合考慮節(jié)點的度數(shù)及其鄰居的集聚程度,提出了一種基于鄰居信息與集聚系數(shù)的節(jié)點重要性評價算法.Ugander等[18]發(fā)現(xiàn)鄰居節(jié)點間的聯(lián)通子圖數(shù)目是節(jié)點重要性的決定因素.Kitsak等[19]提出了K-shell分解算法,該算法類似于剝洋蔥的方法,通過剝離法將網(wǎng)絡(luò)外圍度數(shù)小的節(jié)點逐層剝除,位于內(nèi)層的節(jié)點擁有較高的重要度,然而K-shell分解算法是一種粗?；呐判蚍椒?對于節(jié)點重要性的區(qū)分度不夠.

上述節(jié)點重要性評價指標主要是基于網(wǎng)絡(luò)魯棒性與脆弱性的方法,事實上關(guān)鍵點檢測與具體的研究背景緊密相關(guān),在節(jié)點傳播影響力以及網(wǎng)絡(luò)可控性的背景下,節(jié)點重要性評價方式又有所不同.基于網(wǎng)絡(luò)傳播動力學(xué)模型[20]評價排序算法的研究成果豐碩.Chen等[21]認為節(jié)點影響力不僅由節(jié)點擁有的信息傳播路徑數(shù)量決定,同時還與傳播路徑的多樣性緊密相關(guān);Ruan等[22]通過弱化節(jié)點領(lǐng)域的聚簇性對節(jié)點影響力排序結(jié)果的影響,提出一種基于節(jié)點鄰居核數(shù)與網(wǎng)絡(luò)約束系數(shù)[23]的節(jié)點影響力排序算法;Li等[24]基于馬爾可夫鏈分析,通過分析節(jié)點在網(wǎng)絡(luò)中的動態(tài)行為用于評估節(jié)點影響力;最近,Liu等[25]分析了離散的網(wǎng)絡(luò)SIR(susceptible-infected-recovered)傳播動力學(xué),同時考慮了傳染率、康復(fù)率和有限的時間步三個參數(shù)用于尋找網(wǎng)絡(luò)中最有影響力的節(jié)點.更多基于影響力傳播效率的評價方法,可參見文獻[26].而在復(fù)雜網(wǎng)絡(luò)可控性[27,28]領(lǐng)域,如何尋找最佳的驅(qū)動節(jié)點使得系統(tǒng)達到期望的狀態(tài)是該領(lǐng)域的基本問題,這類驅(qū)動節(jié)點可被認為是網(wǎng)絡(luò)的重要節(jié)點.Zhou等[29]發(fā)現(xiàn)將網(wǎng)絡(luò)的一些度數(shù)小但反饋增益高的節(jié)點作為驅(qū)動節(jié)點,可有效提高網(wǎng)絡(luò)牽制控制的速度;Liu等[30]根據(jù)節(jié)點的出入度情況對節(jié)點在網(wǎng)絡(luò)中的不同重要性做了有效的層級劃分,并基于此提出一種改進策略用于有效打擊網(wǎng)絡(luò)的可控性能;Jia和Pósfai[31]基于隨機抽樣的方法,計算節(jié)點成為驅(qū)動節(jié)點的可能性,發(fā)現(xiàn)節(jié)點的入度越大越不容易成為驅(qū)動節(jié)點.目前有關(guān)網(wǎng)絡(luò)可控性的研究方法已經(jīng)逐漸豐富和全面,理解不同背景下的節(jié)點重要性含義對于將理論研究進行實踐應(yīng)用具有指導(dǎo)意義.

大規(guī)模實際復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)往往隨著時間發(fā)生變化,受技術(shù)條件的限制,對于很多極其復(fù)雜的網(wǎng)絡(luò)獲取其完整的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)依然十分困難,因而通過全局信息定義網(wǎng)絡(luò)節(jié)點重要度具有局限性.通過量化節(jié)點局部網(wǎng)絡(luò)拓撲的重合程度來定義節(jié)點間的相似性,本文提出了一種考慮節(jié)點度以及鄰居節(jié)點拓撲重合度的節(jié)點重要性評估算法,算法只需要獲取節(jié)點兩跳內(nèi)的鄰居節(jié)點信息,通過計算鄰居節(jié)點對之間的相似度,便可表征其在復(fù)雜網(wǎng)絡(luò)系統(tǒng)中的結(jié)構(gòu)重要性,在六個實際網(wǎng)絡(luò)和一個人工小世界網(wǎng)絡(luò)中的實驗表明,所提算法相比度指標degree、半局部度指標semilocal、基于節(jié)點度及其鄰居度的W L指標以及K-shell分解指標更能準確評估節(jié)點的重要性.

2 理論算法

節(jié)點在網(wǎng)絡(luò)中的重要性不僅取決于節(jié)點本身的度數(shù),還取決于鄰域節(jié)點對該節(jié)點的依賴程度,這里的鄰域節(jié)點特指兩跳內(nèi)的低階鄰居節(jié)點.如圖1(a)所示,小型網(wǎng)絡(luò)除節(jié)點a可分為被3個大的橢圓包圍的3塊,盡管節(jié)點a度數(shù)小于鄰居節(jié)點b,c和d,但從網(wǎng)絡(luò)瓦解的角度上分析,當(dāng)節(jié)點a遭受攻擊時,該小型網(wǎng)絡(luò)將迅速分離為三個獨立的網(wǎng)絡(luò),對網(wǎng)絡(luò)的破壞性最大.不僅如此,從信息傳播的角度分析,從每一塊中的任一節(jié)點到其他塊中的任一節(jié)點的信息的傳輸都必然要經(jīng)過節(jié)點a,因此信息從節(jié)點a發(fā)起將有更大的概率傳播到網(wǎng)絡(luò)中的大部分區(qū)域.若圖1(a)中節(jié)點a鄰居節(jié)點的鄰域存在如圖1(b)中的交集,即a的鄰居b和c有3個共同鄰居,此時節(jié)點a的樞紐地位受到削弱,網(wǎng)絡(luò)的魯棒性將增強.通過量化節(jié)點局部網(wǎng)絡(luò)拓撲的重合程度,我們定義了節(jié)點領(lǐng)域相似度,節(jié)點領(lǐng)域相似度越高,網(wǎng)絡(luò)對于節(jié)點的依賴程度越低,節(jié)點的結(jié)構(gòu)重要度也越低.圖1(b)中,當(dāng)鄰居節(jié)點b和c之間不存在連邊時,b與c的相似度定義為Jaccard指標[32]值,即sim(b,c)=|n(b)∩n(c)|/|n(b)∪n(c)|,若b和c之間存在連邊如圖1(c),定義sim(b,c)=1,即

sim值介于0和1之間,節(jié)點局部網(wǎng)絡(luò)拓撲的重合程度越高,則節(jié)點相似度值越大.按照(1)式,在圖1(a)中,可得sim(b,c)=1/9,在圖1(b)中,sim(b,c)=4/9.在圖1(c)中,節(jié)點b和c之間存在連邊,則sim(b,c)=1.

節(jié)點的鄰居數(shù)目越多,且鄰居間的網(wǎng)絡(luò)拓撲重合程度越低,節(jié)點在網(wǎng)絡(luò)結(jié)構(gòu)和功能中的作用越不容易被其他節(jié)點所替代,節(jié)點重要度越高.綜合考慮鄰居節(jié)點間的相似性,我們提出了一種基于鄰域相似度的重要度評估指標LLS(i),表示為

n(i)表示節(jié)點i的鄰居節(jié)點,LLS指標綜合考慮了節(jié)點的度與鄰居節(jié)點的相似度,LLS值越大,說明節(jié)點的度越大且其鄰居節(jié)點之間鄰域重合程度越低.仍以圖1中的節(jié)點a為例,在圖1(a)中,

若節(jié)點b和c的鄰域產(chǎn)生如圖1(b)中的交集,則

更進一步,若b與c還發(fā)生了連接,則

可見,節(jié)點a的鄰居節(jié)點間拓撲結(jié)構(gòu)重合度越高,a的結(jié)構(gòu)重要性將越低,計算結(jié)果值驗證了我們的設(shè)想.

圖1 (網(wǎng)刊彩色)節(jié)點a的領(lǐng)域重合情況Fig.1.(color on line)Overlapbetween the topologies of the neighbors of node a.

3 評價標準

常用來評價節(jié)點重要性排序算法的方法有基于網(wǎng)絡(luò)的傳播動力學(xué)模型以及基于網(wǎng)絡(luò)魯棒性與脆弱性的方法.在不同的評價模型中,節(jié)點重要性的含義有所區(qū)別,在SIS(susceptible-infectioussusceptible)[19]模型中一個節(jié)點的重要度由穩(wěn)態(tài)下該節(jié)點被感染的概率決定;在SIR[33]模型中,一個節(jié)點的重要度由該節(jié)點的平均傳播范圍決定.本文基于網(wǎng)絡(luò)魯棒性對算法排序結(jié)果進行評價,主要研究滲流中的最大連通子圖,采用極大連通系數(shù)與網(wǎng)絡(luò)效率指標量化移除節(jié)點后對于網(wǎng)絡(luò)結(jié)構(gòu)與功能的影響,以此評價節(jié)點的結(jié)構(gòu)重要性.

1)極大連通系數(shù):將節(jié)點按照重要度評估算法從大到小進行排序,觀察移除一部分節(jié)點后對網(wǎng)絡(luò)極大連通子集(網(wǎng)絡(luò)巨片)[34]的影響,計算公式如下:

其中,N表示網(wǎng)絡(luò)中節(jié)點總數(shù),R表示移除一部分節(jié)點后的網(wǎng)絡(luò)巨片的節(jié)點數(shù),網(wǎng)絡(luò)巨片規(guī)模隨著節(jié)點移除而變小的趨勢越明顯,表明采用該方法攻擊網(wǎng)絡(luò)的效果越好.

2)網(wǎng)絡(luò)效率:考察移除節(jié)點對于網(wǎng)絡(luò)效率的影響[35,36],網(wǎng)絡(luò)效率可用于評價網(wǎng)絡(luò)的連通性強弱,移除網(wǎng)絡(luò)中的節(jié)點及其對應(yīng)的所有邊,使得網(wǎng)絡(luò)中的某些路徑被中斷而導(dǎo)致一些節(jié)點之間的最短路徑變大,進而使整個網(wǎng)絡(luò)的平均路徑長度增大,影響網(wǎng)絡(luò)連通性.網(wǎng)絡(luò)效率表示為

其中,ηij=1/dij,dij表示節(jié)點i和j之間的最短路徑,N表示網(wǎng)絡(luò)節(jié)點數(shù).本文通過刪除網(wǎng)絡(luò)中一定比例的特定節(jié)點,模擬網(wǎng)絡(luò)遭受攻擊的仿真效果,計算網(wǎng)絡(luò)遭受攻擊前后的網(wǎng)絡(luò)效率下降比例用以量化各個節(jié)點重要性評價指標的準確性.網(wǎng)絡(luò)效率下降比例表示為:μ=1?η/η0,η表示移除節(jié)點后的網(wǎng)絡(luò)效率,η0表示原始的網(wǎng)絡(luò)效率,0≤μ≤1.μ的值越大,表示移除節(jié)點后網(wǎng)絡(luò)效率變得越差.

4 實驗數(shù)據(jù)集

為了驗證LLS指標評估節(jié)點重要性的效果,本文選取6個具有不同拓撲結(jié)構(gòu)特性的真實網(wǎng)絡(luò)以及一個5000個節(jié)點規(guī)模的人工小世界網(wǎng)絡(luò),網(wǎng)絡(luò)的拓撲結(jié)構(gòu)統(tǒng)計特征如表1所列:1)Facebook網(wǎng)絡(luò)數(shù)據(jù),SlavoZitnik的臉譜網(wǎng)朋友圈關(guān)系數(shù)據(jù)[37];2)USAir美國航空網(wǎng)絡(luò)[38];3)Infectious人群感染網(wǎng)絡(luò)[39];4)Email郵件網(wǎng)絡(luò)[40];5)Yeast蛋白質(zhì)相互作用網(wǎng)絡(luò)[41];6)Power美國國家電力網(wǎng)絡(luò)[42].表1中N與M分別代表網(wǎng)絡(luò)節(jié)點總數(shù)與連邊數(shù);〈k〉代表網(wǎng)絡(luò)平均度大小;ksmax表示K-shell分解后網(wǎng)絡(luò)核心層的核值,ksmin表示K-shell分解后網(wǎng)絡(luò)最外層的核值;L為節(jié)點間平均最短路徑長度.

表1 六個真實網(wǎng)絡(luò)和一個人工小世界網(wǎng)絡(luò)的拓撲特征Tab le 1.Structu ral properties of six real networks and one artifi cial small-world network.

圖2 (網(wǎng)刊彩色)利用不同指標攻擊網(wǎng)絡(luò)重要節(jié)點后極大連通系數(shù)G的變化 (a)美國航空網(wǎng)絡(luò);(b)臉譜網(wǎng);(c)人群感染網(wǎng);(d)郵件網(wǎng)絡(luò);(e)蛋白質(zhì)相互作用網(wǎng)絡(luò);(f)美國西部電力網(wǎng);(g)小世界網(wǎng)絡(luò)Fig.2.(color online)The relative size of giant component(G)sub jectswith diff erent static attack strategies:(a)USAir;(b)Facebook;(c)In fectious;(d)Email;(e)Yeast;(f)Power;(g)Small-world network.

5 實驗結(jié)果與分析

基于上述6個真實網(wǎng)絡(luò)以及人工小世界網(wǎng)絡(luò),本文對LLS指標與同樣是采用局域信息的度排序方法(degree)、半局域度排序方法(semilocal)、基于節(jié)點度及其鄰居度的排序方法(W L)以及基于節(jié)點位置信息的K-shell分解方法進行了比較和分析.根據(jù)五種算法的排序結(jié)果,分別以靜態(tài)攻擊與動態(tài)攻擊的方式移除一定比例p排名靠前的節(jié)點,模擬網(wǎng)絡(luò)遭受蓄意攻擊時極大聯(lián)通子圖規(guī)模與網(wǎng)絡(luò)效率的變化情況,從而評價各個排序算法的準確性.在靜態(tài)攻擊模式中,節(jié)點重要度指標值保持與原始網(wǎng)絡(luò)中各指標計算結(jié)果值一樣,不隨網(wǎng)絡(luò)結(jié)構(gòu)變化而重新計算;反之,在動態(tài)攻擊模式中,每移除一個節(jié)點或一定比例的節(jié)點,節(jié)點的各個重要度指標需要重新計算一次.

5.1 靜態(tài)攻擊效果

在模擬蓄意攻擊網(wǎng)絡(luò)對網(wǎng)絡(luò)極大連通系數(shù)的影響的實驗中,分別對6個真實網(wǎng)絡(luò)采用degree指標、K-shell分解指標、semilocal指標、W L指標以及本文提出的LLS指標移除排名靠前的節(jié)點,實驗結(jié)果如圖2(a)—(g)所示.在所有的網(wǎng)絡(luò)中,LLS指標導(dǎo)致網(wǎng)絡(luò)極大連通系數(shù)變小的總體趨勢最為明顯,尤其在圖2(e)蛋白質(zhì)互作用網(wǎng)絡(luò)中,LLS指標在網(wǎng)絡(luò)靜態(tài)攻擊的初始過程就表現(xiàn)出相比其他指標更好的攻擊效果.圖2(f)紅色曲線為模擬通過K-shell分解方法找出的網(wǎng)絡(luò)核心節(jié)點用于攻擊Power網(wǎng)絡(luò)的結(jié)果,曲線中存在部分網(wǎng)絡(luò)極大連通系數(shù)不隨著最大K-shell節(jié)點的移除而下降的情況,這是由于在靜態(tài)攻擊模式中,原本重要度排序靠前的節(jié)點其真實重要度已隨著網(wǎng)絡(luò)結(jié)構(gòu)的變化而變化,且K-shell方法容易將局域連接過于緊密的小團體判斷為網(wǎng)絡(luò)核心節(jié)點[43,44],而這些偽核心節(jié)點并不在網(wǎng)絡(luò)極大連通子圖中.在圖2(g)小世界網(wǎng)絡(luò)的巨片瓦解實驗中,K-shell分解方法瓦解網(wǎng)絡(luò)的效率最差,類似隨機攻擊的結(jié)果,其原因是小世界網(wǎng)絡(luò)中節(jié)點度分布較為均勻,K-shell分解方法對于網(wǎng)絡(luò)節(jié)點重要度的區(qū)分能力有限.

圖3 (網(wǎng)刊彩色)利用不同的節(jié)點重要性指標刪除一定比例排序靠前的節(jié)點后網(wǎng)絡(luò)效率下降率μ的變化 (a)美國航空網(wǎng)絡(luò);(b)臉譜網(wǎng);(c)人群感染網(wǎng);(d)郵件網(wǎng)絡(luò);(e)蛋白質(zhì)相互作用網(wǎng)絡(luò);(f)美國西部電力網(wǎng);(g)小世界網(wǎng)絡(luò)Fig.3.(color on line)The relation between decline rate of network effi ciencyμand the number of key nodes removed fromthe network,the ranking lists are produced by diff erent ranking ind ices:(a)USAir;(b)Facebook;(c)In fectious;(d)Email;(e)Yeast;(f)Power;(g)Small-world network.

圖3反映的是利用不同的節(jié)點重要性指標刪除一定比例排序靠前的節(jié)點后,網(wǎng)絡(luò)效率下降率μ的變化,移除重要節(jié)點后網(wǎng)絡(luò)連通性越差,網(wǎng)絡(luò)效率的下降趨勢越明顯.實驗結(jié)果如圖3(a)—(g)所示,采用LLS指標刪除排序靠前的節(jié)點導(dǎo)致網(wǎng)絡(luò)效率下降的幅度最大,其后依次是度指標、半局部度指標、W L指標、K-shell指標.例如在圖3(f)的美國西部電力網(wǎng)中,選擇性刪除各個指標排序靠前的1%至10%的節(jié)點,與其他指標相比,利用LLS指標刪除節(jié)點后,網(wǎng)絡(luò)效率變得最差.

圖4 (網(wǎng)刊彩色)利用不同指標動態(tài)攻擊網(wǎng)絡(luò)重要節(jié)點后極大連通系數(shù)G的變化 (a)美國航空網(wǎng)絡(luò);(b)臉譜網(wǎng);(c)人群感染網(wǎng);(d)郵件網(wǎng)絡(luò);(e)蛋白質(zhì)相互作用網(wǎng)絡(luò);(f)美國西部電力網(wǎng);(g)小世界網(wǎng)絡(luò)Fig.4.(color on line)The relative size of giant component(G)sub jects with d iff erent dynamic attack strategies:(a)USAir;(b)Facebook;(c)In fectious;(d)Email;(e)Yeast;(f)Power;(g)Small-world network.

5.2 動態(tài)攻擊效果

網(wǎng)絡(luò)遭受蓄意攻擊時結(jié)構(gòu)會發(fā)生變化,因此節(jié)點的重要度排序結(jié)果也將隨之改變,靜態(tài)攻擊方式不考慮網(wǎng)絡(luò)結(jié)構(gòu)變化對節(jié)點重要度排序結(jié)果的影響,是一種相對簡單的攻擊方式,與之對應(yīng)的動態(tài)攻擊方法則是在每一輪網(wǎng)絡(luò)攻擊后重新計算網(wǎng)絡(luò)中各節(jié)點的重要度.基于上述四個網(wǎng)絡(luò),本文比較了LLS指標、degree指標、semilocal指標、W L指標以及K-shell指標對網(wǎng)絡(luò)進行動態(tài)攻擊時的效果,如圖4和圖5所示,在網(wǎng)絡(luò)極大連通系數(shù)與網(wǎng)絡(luò)效率的實驗中,利用LLS指標動態(tài)移除排序靠前的節(jié)點,網(wǎng)絡(luò)碎片化效果最明顯,攻擊效果最佳.同時,通過將圖2與圖4、圖3與圖5進行對比,不難發(fā)現(xiàn),對于一種特定的重要度排序方法,動態(tài)攻擊的效果總是好于靜態(tài)攻擊的效果.尤其在小世界網(wǎng)絡(luò)中的對比更為明顯,觀察圖2(g)與圖4(g)兩種攻擊模式下的網(wǎng)絡(luò)瓦解效果,發(fā)現(xiàn)動態(tài)攻擊方式明顯優(yōu)于靜態(tài)攻擊.

圖5 (網(wǎng)刊彩色)利用不同的節(jié)點重要性指標動態(tài)刪除一定比例排序靠前的節(jié)點后網(wǎng)絡(luò)效率下降率μ的變化,節(jié)點重要度在每一輪攻擊行為發(fā)生后都進行了重新計算 (a)美國航空網(wǎng)絡(luò);(b)臉譜網(wǎng);(c)人群感染網(wǎng);(d)郵件網(wǎng)絡(luò);(e)蛋白質(zhì)相互作用網(wǎng)絡(luò);(f)美國西部電力網(wǎng);(g)小世界網(wǎng)絡(luò)Fig.5.(color on line)The relation between decline rate of network effi ciencyμand a certain proportion of themost important nodes removed fromthe network,the ranking lists are recalcu lated after each round of attack behavior:(a)USAir;(b)Facebook;(c)In fectious;(d)Email;(e)Yeast;(f)Power;(g)Small-world network.

6 結(jié) 論

識別復(fù)雜網(wǎng)絡(luò)中的關(guān)鍵節(jié)點可以幫助我們有效地設(shè)計防護策略用于提高網(wǎng)絡(luò)樞紐節(jié)點的安全防護能力,對于提升網(wǎng)絡(luò)抗毀性與結(jié)構(gòu)穩(wěn)定性有重要作用.通過量化節(jié)點局部網(wǎng)絡(luò)拓撲的重合程度來定義節(jié)點間的相似性,本文提出了一種考慮節(jié)點度以及鄰居節(jié)點拓撲重合度的節(jié)點重要性評估算法,算法只需要獲取節(jié)點二跳內(nèi)的鄰居信息就可計算出節(jié)點的重要度值,因而對于刻畫大規(guī)模網(wǎng)絡(luò)的抗毀性與結(jié)構(gòu)可靠性具有現(xiàn)實意義.在實際網(wǎng)絡(luò)和人工的小世界網(wǎng)絡(luò)中,通過對極大連通系數(shù)與網(wǎng)絡(luò)效率兩種評估指標的實驗結(jié)果對比,證明了所提算法優(yōu)于基于局域信息的度指標、半局部度指標、基于節(jié)點與鄰居度的W L指標以及基于節(jié)點位置的K-shell指標.

本文從結(jié)構(gòu)的角度分析了單層網(wǎng)絡(luò)中的節(jié)點重要性,近年來,越來越多的網(wǎng)絡(luò)科學(xué)工作者將研究的目光從孤立的單層網(wǎng)絡(luò)轉(zhuǎn)移到相互依存的網(wǎng)絡(luò)上[45],在相依網(wǎng)絡(luò)中一旦某個節(jié)點遭到破壞而失效,網(wǎng)絡(luò)間的依存關(guān)系將會使得失效的影響被傳播和放大,最終一個很小的故障就可能導(dǎo)致整個網(wǎng)絡(luò)的癱瘓.因此如何在相互關(guān)聯(lián)的網(wǎng)絡(luò)中分析節(jié)點對于網(wǎng)絡(luò)的結(jié)構(gòu)魯棒性與功能穩(wěn)定性的影響具有重要意義,這是我們下一步研究的方向.

[1]Barabási AL,Albert R 1999Science286 509

[2]W atts D J,Strogatz S H1998Nature393 440

[3]Pastor-Satorras R,Vespignani A2001Phys.Rev.Lett.86 3200

[4]Rogers T2015Europhys.Lett.109 28005

[5]Kinney R,Crucitti P,Albert R,Latora V 2005Eur.Phys.J.B46 101

[6]W ang G Z,CaoY J,BaoZ J,Han Z X 2009Acta Phys.Sin.58 3597(in Chinese)[王光增,曹一家,包哲靜,韓禎祥2009物理學(xué)報58 3597]

[7]Albert R,Jeong H,Barabási AL 1999Nature401 130

[8]Sabidussi G 1966Psychometrika31 581

[9]Freeman L C 1977Sociometry40 35

[10]Newman ME J 2006Phys.Rev.E74 036104

[11]Brin S and Page L 1998Comput.Networks.Isdn.30 107

[12]Radicchi F,FortunatoS,Markines B,VespignaniA2009Phys.Rev.E80 056103

[13]LüL Y,Zhang Y C,Yeung C H,Zhou T2011P loSOne6 e21202

[14]LüL Y,Zhang Q M,Stanley HE 2016Nat.Commun.7 10168

[15]Chen D B,Lu L Y,Shang MS,Zhang Y C,Zhou T2012Physica A391 1777

[16]W ang JW,Rong L L,GuoTZ 2010J.Da lian Un iv.Technol.50 822(in Chinese)[王建偉,榮莉莉,郭天柱2010大連理工大學(xué)學(xué)報50 822]

[17]Ren ZM,ShaoF,Liu JG,GuoQ,W ang BH2013Acta Phys.Sin.62 128901(in Chinese)[任卓明,邵鳳,劉建國,郭強,汪秉宏2013物理學(xué)報62 128901]

[18]Ugander J,BackstromL,MarlowC,Kleinberg J 2012Proc.Natl.Acad.Sci.109 5962

[19]Kitsak M,Gallos L K,Hav lin S,Liljeros F,Muchnik L,Stan ley HE,Makse HA2010Nat.Phys.6 888

[20]Ren X L,LüL Y 2014Sci.Bu ll.59 1175(in Chinese)[任曉龍,呂琳媛 2014科學(xué)通報 59 1175]

[21]Chen D B,X iaoR,Zeng A,Zhang Y C 2014Europhys.Lett.104 68006

[22]Ruan Y R,LaoS Y,X iaoY D,W ang J D,Bai L 2016Chin.Phys.Lett.33 028901

[23]Bu rt R S 2009Structure Holes:the Social Structure of Competition(London:Harvard University Press)p53

[24]Li P,Zhang J,Xu X K,Small M2012Chin.Phys.Lett.29 048903

[25]Liu JG,Lin JH,GuoQ,Zhou T2016Sci.Rep.6 21380

[26]LüL Y,Chen D B,Ren X L,Zhang Q M,Zhang Y C,Zhou T2016Phys.Rep.650 1

[27]Liu Y Y,Slotine J J,Barabási AL 2011Nature473 167

[28]Orouskhani Y,JaliliM,Yu X H2016Sci.Rep.6 24252

[29]Zhou MY,ZhuoZ,LiaoH,Fu Z Q,Cai SM2015Sci.Rep.5 17459

[30]Liu Y Y,Slotine J J,Barabasi AL 2012PloS One7 e44459

[31]Jia T,PósfaiM2014Sci.Rep.4 5379

[32]Jaccad P 1901Bu ll.Torrey Bot.C lub37 547

[33]CastellanoC and Pastor-Satorras R 2010Phys.Rev.Lett.105 218701

[34]Dereich S,M?rters P 2013Ann.Prob.41 329

[35]Vragovic I,Louis E,D iaz-Guilera A2005Phys.Rev.E71 036122

[36]Latora V,MarchioriM2007NewJ.Phys.9 188

[37]Blagus N,?ubelj L,Bajec M2012Physica A391 2794

[38]Batagelj V,Mrvar A1998Connections21 47

[39]Isella L,StehléJ,Barrat A,CattutoC,Pinton J F 2011J.Theor.Biol.271 166

[40]Guimera R,Danon L,D iaz-Guilera A,G iralt F,Arenas A2003Phys.Rev.E68 065103

[41]Von Mering C,Krause R,Snel B,Cornell M,Oliver S G,Fields S,Bork P 2002Nature417 399

[42]W atts D J,Strogatz S H1998Nature393 440

[43]Liu Y,Tang M,Zhou T,DoY 2015Sci.Rep.5 9602

[44]Liu Y,Tang M,Zhou T,DoY 2015Sci.Rep.5 13172

[45]Bu ldy rev S V,Parshani R,Pau l G,Stan ley HE,Hav lin S 2010Nature464 1025

PACS:89.75.Fb,89.75.HcDOI:10.7498/aps.66.038902

N ode importance measu rement based on neighborhood similarity in complex network?

Ruan Yi-Run?LaoSong-Yang Wang Jun-De Bai Liang Chen Li-Dong

(Science and Technology on Information Systems Engineering Laboratory,National University ofDefense Technology,Changsha 410073,China)(Received 20 September 2016;revised manuscript received 14 October 2016)

Ranking node importance is of great signifi cance for studying the robustness and vulnerability of complex network.Over the recent years,various centrality indices such as degree,semilocal,K-shell,betweenness and closeness centrality have been employed tomeasure node importance in the network.Among them,some well-known globalmeasures such as betweenness centrality and closeness centrality can achieve generally higher accuracy in ranking nodes,while their computation complexity is relatively high,and alsothe global information is not readily available in a large-scaled network.In this paper,we propose a newlocalmetric which on ly needs toobtain the neighborhood information within twohops of the node torank node importance.Firstly,we calculate the similarity of node neighbors by quantifying the overlapof their topological structures with Jaccard index;second ly,the similarity between pairs of neighbor nodes is calculated synthetically,and the redundancy of the local link of nodes is obtained.Finally,by reducing the in fluence of densely local links on ranking node importance,a newlocal index named LLS that considers both neighborhood similarity and node degree is proposed.Tocheck the eff ectiveness of the proposed method of ranking node importance,we carry out it on six realworld networks and one artificial small-world network by static attacks and dynamic attacks.In the static attack mode,the ranking value of each node is the same as that in the original network.In the dynamic attack mode,once the nodes are removed,the centrality of each node needs recalculating.The relative size of the giant component and the network effi ciency are used for network connectivity assessment during the attack.Afaster decrease in the size of the giant component and a faster decay of network effi ciency indicate a more eff ective attack strategy.By comparing the decline rates of these twoindices toevaluate the connectedness of all networks,we find that the proposed method ismore effi cient than traditional localmetrics such as degree centrality,semilocal centrality,K-shell decomposition method,nomatter whether it is in the static or dynamicmanner.And for a certain rankingmethod,the resu lts of the dynamic attack are always better than those of the static attack.This work can shed some light on howthe local densely connections aff ect the node centrality in maintaining network robustness.

complex network,robustness,node importance,neighborhood similarity

10.7498/aps.66.038902

?國家自然科學(xué)基金(批準號:61571453)資助的課題.

?通信作者.E-mail:ruanyirun@163.com

*Project supported by the National Natural Science Foundation of China(G rant No.61571453).

?Corresponding author.E-mail:ruanyirun@163.com