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

阮逸潤(rùn)老松楊 王竣德 白亮 陳立棟

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

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

阮逸潤(rùn)?老松楊 王竣德 白亮 陳立棟

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

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

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

1 引 言

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

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

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

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

2 理論算法

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

sim值介于0和1之間,節(jié)點(diǎn)局部網(wǎng)絡(luò)拓?fù)涞闹睾铣潭仍礁?則節(jié)點(diǎn)相似度值越大.按照(1)式,在圖1(a)中,可得sim(b,c)=1/9,在圖1(b)中,sim(b,c)=4/9.在圖1(c)中,節(jié)點(diǎn)b和c之間存在連邊,則sim(b,c)=1.

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

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

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

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

可見(jiàn),節(jié)點(diǎn)a的鄰居節(jié)點(diǎn)間拓?fù)浣Y(jié)構(gòu)重合度越高,a的結(jié)構(gòu)重要性將越低,計(jì)算結(jié)果值驗(yàn)證了我們的設(shè)想.

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

3 評(píng)價(jià)標(biāo)準(zhǔn)

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

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

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

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

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

4 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證LLS指標(biāo)評(píng)估節(jié)點(diǎn)重要性的效果,本文選取6個(gè)具有不同拓?fù)浣Y(jié)構(gòu)特性的真實(shí)網(wǎng)絡(luò)以及一個(gè)5000個(gè)節(jié)點(diǎn)規(guī)模的人工小世界網(wǎng)絡(luò),網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)統(tǒng)計(jì)特征如表1所列:1)Facebook網(wǎng)絡(luò)數(shù)據(jù),SlavoZitnik的臉譜網(wǎng)朋友圈關(guān)系數(shù)據(jù)[37];2)USAir美國(guó)航空網(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美國(guó)國(guó)家電力網(wǎng)絡(luò)[42].表1中N與M分別代表網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)與連邊數(shù);〈k〉代表網(wǎng)絡(luò)平均度大小;ksmax表示K-shell分解后網(wǎng)絡(luò)核心層的核值,ksmin表示K-shell分解后網(wǎng)絡(luò)最外層的核值;L為節(jié)點(diǎn)間平均最短路徑長(zhǎng)度.

表1 六個(gè)真實(shí)網(wǎng)絡(luò)和一個(gè)人工小世界網(wǎng)絡(luò)的拓?fù)涮卣鱐ab le 1.Structu ral properties of six real networks and one artifi cial small-world network.

圖2 (網(wǎng)刊彩色)利用不同指標(biāo)攻擊網(wǎng)絡(luò)重要節(jié)點(diǎn)后極大連通系數(shù)G的變化 (a)美國(guó)航空網(wǎng)絡(luò);(b)臉譜網(wǎng);(c)人群感染網(wǎng);(d)郵件網(wǎng)絡(luò);(e)蛋白質(zhì)相互作用網(wǎng)絡(luò);(f)美國(guó)西部電力網(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 實(shí)驗(yàn)結(jié)果與分析

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

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

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

圖3 (網(wǎng)刊彩色)利用不同的節(jié)點(diǎn)重要性指標(biāo)刪除一定比例排序靠前的節(jié)點(diǎn)后網(wǎng)絡(luò)效率下降率μ的變化 (a)美國(guó)航空網(wǎng)絡(luò);(b)臉譜網(wǎng);(c)人群感染網(wǎng);(d)郵件網(wǎng)絡(luò);(e)蛋白質(zhì)相互作用網(wǎng)絡(luò);(f)美國(guó)西部電力網(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é)點(diǎn)重要性指標(biāo)刪除一定比例排序靠前的節(jié)點(diǎn)后,網(wǎng)絡(luò)效率下降率μ的變化,移除重要節(jié)點(diǎn)后網(wǎng)絡(luò)連通性越差,網(wǎng)絡(luò)效率的下降趨勢(shì)越明顯.實(shí)驗(yàn)結(jié)果如圖3(a)—(g)所示,采用LLS指標(biāo)刪除排序靠前的節(jié)點(diǎn)導(dǎo)致網(wǎng)絡(luò)效率下降的幅度最大,其后依次是度指標(biāo)、半局部度指標(biāo)、W L指標(biāo)、K-shell指標(biāo).例如在圖3(f)的美國(guó)西部電力網(wǎng)中,選擇性刪除各個(gè)指標(biāo)排序靠前的1%至10%的節(jié)點(diǎn),與其他指標(biāo)相比,利用LLS指標(biāo)刪除節(jié)點(diǎn)后,網(wǎng)絡(luò)效率變得最差.

圖4 (網(wǎng)刊彩色)利用不同指標(biāo)動(dòng)態(tài)攻擊網(wǎng)絡(luò)重要節(jié)點(diǎn)后極大連通系數(shù)G的變化 (a)美國(guó)航空網(wǎng)絡(luò);(b)臉譜網(wǎng);(c)人群感染網(wǎng);(d)郵件網(wǎng)絡(luò);(e)蛋白質(zhì)相互作用網(wǎng)絡(luò);(f)美國(guó)西部電力網(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 動(dòng)態(tài)攻擊效果

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

圖5 (網(wǎng)刊彩色)利用不同的節(jié)點(diǎn)重要性指標(biāo)動(dòng)態(tài)刪除一定比例排序靠前的節(jié)點(diǎn)后網(wǎng)絡(luò)效率下降率μ的變化,節(jié)點(diǎn)重要度在每一輪攻擊行為發(fā)生后都進(jìn)行了重新計(jì)算 (a)美國(guó)航空網(wǎng)絡(luò);(b)臉譜網(wǎng);(c)人群感染網(wǎng);(d)郵件網(wǎng)絡(luò);(e)蛋白質(zhì)相互作用網(wǎng)絡(luò);(f)美國(guó)西部電力網(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é) 論

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

本文從結(jié)構(gòu)的角度分析了單層網(wǎng)絡(luò)中的節(jié)點(diǎn)重要性,近年來(lái),越來(lái)越多的網(wǎng)絡(luò)科學(xué)工作者將研究的目光從孤立的單層網(wǎng)絡(luò)轉(zhuǎn)移到相互依存的網(wǎng)絡(luò)上[45],在相依網(wǎng)絡(luò)中一旦某個(gè)節(jié)點(diǎn)遭到破壞而失效,網(wǎng)絡(luò)間的依存關(guān)系將會(huì)使得失效的影響被傳播和放大,最終一個(gè)很小的故障就可能導(dǎo)致整個(gè)網(wǎng)絡(luò)的癱瘓.因此如何在相互關(guān)聯(lián)的網(wǎng)絡(luò)中分析節(jié)點(diǎn)對(duì)于網(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é)報(bào)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é)報(bào)50 822]

[17]Ren ZM,ShaoF,Liu JG,GuoQ,W ang BH2013Acta Phys.Sin.62 128901(in Chinese)[任卓明,邵鳳,劉建國(guó),郭強(qiáng),汪秉宏2013物理學(xué)報(bào)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é)通報(bào) 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

?國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào):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