基于領域相似度的復雜網絡節點重要度評估算法?

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

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

基于領域相似度的復雜網絡節點重要度評估算法?

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

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

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

復雜網絡,魯棒性,節點重要性,領域相似度

1 引 言

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

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

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

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

2 理論算法

節點在網絡中的重要性不僅取決于節點本身的度數,還取決于鄰域節點對該節點的依賴程度,這里的鄰域節點特指兩跳內的低階鄰居節點.如圖1(a)所示,小型網絡除節點a可分為被3個大的橢圓包圍的3塊,盡管節點a度數小于鄰居節點b,c和d,但從網絡瓦解的角度上分析,當節點a遭受攻擊時,該小型網絡將迅速分離為三個獨立的網絡,對網絡的破壞性最大.不僅如此,從信息傳播的角度分析,從每一塊中的任一節點到其他塊中的任一節點的信息的傳輸都必然要經過節點a,因此信息從節點a發起將有更大的概率傳播到網絡中的大部分區域.若圖1(a)中節點a鄰居節點的鄰域存在如圖1(b)中的交集,即a的鄰居b和c有3個共同鄰居,此時節點a的樞紐地位受到削弱,網絡的魯棒性將增強.通過量化節點局部網絡拓撲的重合程度,我們定義了節點領域相似度,節點領域相似度越高,網絡對于節點的依賴程度越低,節點的結構重要度也越低.圖1(b)中,當鄰居節點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之間,節點局部網絡拓撲的重合程度越高,則節點相似度值越大.按照(1)式,在圖1(a)中,可得sim(b,c)=1/9,在圖1(b)中,sim(b,c)=4/9.在圖1(c)中,節點b和c之間存在連邊,則sim(b,c)=1.

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

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

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

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

可見,節點a的鄰居節點間拓撲結構重合度越高,a的結構重要性將越低,計算結果值驗證了我們的設想.

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

3 評價標準

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

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

其中,N表示網絡中節點總數,R表示移除一部分節點后的網絡巨片的節點數,網絡巨片規模隨著節點移除而變小的趨勢越明顯,表明采用該方法攻擊網絡的效果越好.

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

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

4 實驗數據集

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

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

圖2 (網刊彩色)利用不同指標攻擊網絡重要節點后極大連通系數G的變化 (a)美國航空網絡;(b)臉譜網;(c)人群感染網;(d)郵件網絡;(e)蛋白質相互作用網絡;(f)美國西部電力網;(g)小世界網絡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 實驗結果與分析

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

5.1 靜態攻擊效果

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

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

圖4 (網刊彩色)利用不同指標動態攻擊網絡重要節點后極大連通系數G的變化 (a)美國航空網絡;(b)臉譜網;(c)人群感染網;(d)郵件網絡;(e)蛋白質相互作用網絡;(f)美國西部電力網;(g)小世界網絡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 動態攻擊效果

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

圖5 (網刊彩色)利用不同的節點重要性指標動態刪除一定比例排序靠前的節點后網絡效率下降率μ的變化,節點重要度在每一輪攻擊行為發生后都進行了重新計算 (a)美國航空網絡;(b)臉譜網;(c)人群感染網;(d)郵件網絡;(e)蛋白質相互作用網絡;(f)美國西部電力網;(g)小世界網絡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 結 論

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

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

[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物理學報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大連理工大學學報50 822]

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

?國家自然科學基金(批準號: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