復(fù)雜網(wǎng)絡(luò)的魯棒性與中心性指標(biāo)的研究

陸靖橋 傅秀芬 蒙在橋

復(fù)雜網(wǎng)絡(luò)的魯棒性與中心性指標(biāo)的研究

陸靖橋1傅秀芬1蒙在橋2

1(廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 廣東 廣州 510006)

2(中山大學(xué)信息科學(xué)與技術(shù)學(xué)院 廣東 廣州 510006)

網(wǎng)絡(luò)魯棒性是指網(wǎng)絡(luò)遭到隨機(jī)故障或蓄意攻擊時(shí)仍能維持其功能的能力，理解復(fù)雜網(wǎng)絡(luò)部分結(jié)構(gòu)的失效對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和功能的影響有著非常重要的意義。針對(duì)不同的開放數(shù)據(jù)集和爬取的新浪微博數(shù)據(jù)集，通過(guò)計(jì)算移除部分節(jié)點(diǎn)后的巨片和連通子圖數(shù)目等指標(biāo)，著重分析蓄意攻擊對(duì)網(wǎng)絡(luò)的影響，發(fā)現(xiàn)度攻擊策略對(duì)不同網(wǎng)絡(luò)結(jié)構(gòu)影響均較大，緊密度和介數(shù)攻擊策略對(duì)網(wǎng)絡(luò)結(jié)構(gòu)的影響有明顯區(qū)別。實(shí)驗(yàn)表明，非微博網(wǎng)絡(luò)的蓄意攻擊中，采用度和介數(shù)攻擊策略效果較好，而微博網(wǎng)絡(luò)應(yīng)采用度和緊密度攻擊策略。

復(fù)雜網(wǎng)絡(luò) 中心性指標(biāo) 魯棒性 蓄意攻擊

0 引 言

復(fù)雜系統(tǒng)出現(xiàn)在很多自然和社會(huì)科學(xué)領(lǐng)域，以及許多技術(shù)領(lǐng)域。復(fù)雜網(wǎng)絡(luò)是復(fù)雜系統(tǒng)的抽象，幾乎所有的復(fù)雜系統(tǒng)均可以抽象為復(fù)雜網(wǎng)絡(luò)，這些抽象后的網(wǎng)絡(luò)一般擁有大量的節(jié)點(diǎn)，同時(shí)對(duì)應(yīng)的節(jié)點(diǎn)間存在復(fù)雜的連邊關(guān)系[1]。復(fù)雜網(wǎng)絡(luò)的一項(xiàng)基礎(chǔ)領(lǐng)域是研究在網(wǎng)絡(luò)部分結(jié)構(gòu)失效后對(duì)網(wǎng)絡(luò)整體結(jié)構(gòu)和功能的影響[2]，其稱為網(wǎng)絡(luò)的魯棒性。

復(fù)雜系統(tǒng)強(qiáng)調(diào)從結(jié)構(gòu)角度分析系統(tǒng)的功能，事實(shí)上復(fù)雜系統(tǒng)的拓?fù)浣Y(jié)構(gòu)是系統(tǒng)所具有的內(nèi)在、本質(zhì)的特性，系統(tǒng)的功能與其拓?fù)涿芮邢嚓P(guān)。復(fù)雜系統(tǒng)可能會(huì)受到各種事件的攻擊，影響系統(tǒng)正常的結(jié)構(gòu)和功能。如2003年8月，美國(guó)俄亥俄州克利夫蘭市的超高壓輸電線路相繼過(guò)載燒斷使得上千萬(wàn)人陷入黑暗長(zhǎng)達(dá)15小時(shí)，經(jīng)濟(jì)損失高達(dá)數(shù)百億美元。再如，2008年1月的大雪造成中國(guó)南方的高速道路、各個(gè)城市的街道陷入癱瘓，造成行人和物資無(wú)法流通，給社會(huì)和經(jīng)濟(jì)帶來(lái)了極大的損失。因此，研究復(fù)雜網(wǎng)絡(luò)的魯棒性具有重要的理論和現(xiàn)實(shí)意義。

Albert等[3]開創(chuàng)性地分別將隨機(jī)網(wǎng)絡(luò)(ER模型)和無(wú)標(biāo)度網(wǎng)絡(luò)(BA模型)置于隨機(jī)故障和蓄意攻擊兩種攻擊策略之下，結(jié)果顯示無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)隨機(jī)故障比隨機(jī)網(wǎng)絡(luò)具有更強(qiáng)的魯棒性，但對(duì)蓄意攻擊卻較脆弱，并指出其根源在于無(wú)標(biāo)度網(wǎng)絡(luò)中度分布的不均勻性。柳虹等[4]分析供應(yīng)鏈網(wǎng)絡(luò)遭到攻擊時(shí)的脆弱性和魯棒性，得出傳遞攻擊能夠較好地模擬供應(yīng)鏈網(wǎng)絡(luò)中的供求失敗。周漩等[5]利用節(jié)點(diǎn)效率評(píng)估復(fù)雜網(wǎng)絡(luò)的功能魯棒性，實(shí)現(xiàn)對(duì)大型復(fù)雜網(wǎng)絡(luò)可以獲得較理想的計(jì)算能力。王凱[6]對(duì)電力網(wǎng)絡(luò)的復(fù)雜性和魯棒性進(jìn)行研究，提出了用于電網(wǎng)關(guān)鍵節(jié)點(diǎn)和關(guān)鍵路線識(shí)別的結(jié)構(gòu)重要度指標(biāo)和計(jì)算方法。Schneider等[7]以歐洲電力網(wǎng)絡(luò)和全球因特網(wǎng)的服務(wù)提供者網(wǎng)絡(luò)為研究對(duì)象，提出了一種新的有效減緩攻擊的方法，在網(wǎng)絡(luò)拓?fù)湫薷淖钚『筒辉黾舆B邊的情況下顯著提高網(wǎng)絡(luò)的魯棒性。Iyer等[8]除采用度和介數(shù)中心性，還引入緊密度和特征向量等全局指標(biāo)，結(jié)合聚類系數(shù)和同配系數(shù)，分析合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)遭到隨機(jī)攻擊和蓄意攻擊時(shí)的魯棒性，發(fā)現(xiàn)度和介數(shù)攻擊策略均具有不錯(cuò)的效果。吳敏等[9]對(duì)BBS回復(fù)網(wǎng)絡(luò)進(jìn)行分析，發(fā)現(xiàn)BBS用戶回復(fù)網(wǎng)絡(luò)抗毀能力遠(yuǎn)不及隨機(jī)網(wǎng)絡(luò)和無(wú)標(biāo)度網(wǎng)絡(luò)，蓄意攻擊能在短時(shí)間內(nèi)使網(wǎng)絡(luò)崩潰。

目前不少學(xué)者采用平均最短路徑、聚集系數(shù)和網(wǎng)絡(luò)效率等作為衡量指標(biāo)[10]，廣泛探討了網(wǎng)絡(luò)的魯棒性和災(zāi)難(故障)對(duì)網(wǎng)絡(luò)的影響。Barrat等在文獻(xiàn)[11]中指出“確定最中心節(jié)點(diǎn)是刻畫網(wǎng)絡(luò)各種特征研究的最主要問(wèn)題”，依據(jù)這一思想，另一種重要的網(wǎng)絡(luò)魯棒性研究方法考察網(wǎng)絡(luò)在移除部分節(jié)點(diǎn)后的巨片大小[7]，即先移除一定比例高中心性值的節(jié)點(diǎn)，再計(jì)算最大連通子圖包含節(jié)點(diǎn)數(shù)目。

本文采用巨片指標(biāo)，同時(shí)引入連通子圖數(shù)目這一新指標(biāo)，用以刻畫網(wǎng)絡(luò)“破碎”程度，力求更全面地對(duì)比分析不同網(wǎng)絡(luò)的魯棒性。目前復(fù)雜網(wǎng)絡(luò)的魯棒性研究大多針對(duì)電力、航空等數(shù)據(jù)集，較少關(guān)注微博網(wǎng)絡(luò)。復(fù)雜網(wǎng)絡(luò)的隨機(jī)攻擊在文獻(xiàn)[3]等已有詳細(xì)描述，本文不予累贅?lè)治?，重點(diǎn)在于分析不同網(wǎng)絡(luò)的蓄意攻擊。實(shí)驗(yàn)對(duì)象采用開放數(shù)據(jù)集和爬取的新浪微博數(shù)據(jù)集。

1 相關(guān)定義

1.1 中心性指標(biāo)

度刻畫網(wǎng)絡(luò)的局部特征，屬于無(wú)標(biāo)度網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的最基本參數(shù)，用于描述靜態(tài)網(wǎng)絡(luò)節(jié)點(diǎn)的直接影響力。節(jié)點(diǎn)v的度kv定義為與其直接相連的節(jié)點(diǎn)數(shù)目，節(jié)點(diǎn)的kv越大說(shuō)明該節(jié)點(diǎn)越重要。在擁有n個(gè)節(jié)點(diǎn)的有向網(wǎng)絡(luò)中，節(jié)點(diǎn)最大的可能度為n-1，則節(jié)點(diǎn)v的度中心性歸一化值為:

(1)

介數(shù)刻畫網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)于信息流動(dòng)的影響力，屬于網(wǎng)絡(luò)的全局特征。在n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，經(jīng)過(guò)給定節(jié)點(diǎn)v的最短路徑的最大數(shù)目情形是任意兩個(gè)其他節(jié)點(diǎn)之間的最短路徑均經(jīng)過(guò)該節(jié)點(diǎn)，即(n-1)(n-2)/2。節(jié)點(diǎn)v的介數(shù)中心性歸一化定義為：

(2)

其中，δst表示節(jié)點(diǎn)s到節(jié)點(diǎn)t的最短路徑數(shù)目，δst(v)表示從節(jié)點(diǎn)s到節(jié)點(diǎn)t之間經(jīng)過(guò)節(jié)點(diǎn)v的最短路徑數(shù)目。

緊密中心性刻畫節(jié)點(diǎn)v到達(dá)其他節(jié)點(diǎn)的難易程度，定義為v到達(dá)其他節(jié)點(diǎn)的最短路徑之和的倒數(shù)：

(3)

特征向量中心性認(rèn)為一個(gè)節(jié)點(diǎn)的重要性既取決于其鄰居節(jié)點(diǎn)的數(shù)量(度)，同時(shí)也取決于每個(gè)鄰居節(jié)點(diǎn)的重要性，定義節(jié)點(diǎn)vi的特征向量值xi為:

(4)

其中，僅當(dāng)vi和vj相鄰時(shí)，aij=1，否則aij=0。c為一個(gè)比例常量。從定義發(fā)現(xiàn)，特征向量更加強(qiáng)調(diào)節(jié)點(diǎn)所處的周圍環(huán)境。

1.2 連通子圖

連通子圖[3]表示網(wǎng)絡(luò)G在攻擊后，v1,v2,…,vm-1,vm(1≤m≤n)與網(wǎng)絡(luò)其他節(jié)點(diǎn)失去連接，導(dǎo)致網(wǎng)絡(luò)G破碎成多個(gè)互不連通的獨(dú)立子圖G1,G2,…,Gs-1,Gs(1≤s≤n)，其中的最大連通子圖稱為“巨片”。

對(duì)于復(fù)雜網(wǎng)絡(luò)而言，巨片在描述網(wǎng)絡(luò)受到攻擊后的“殘留”連通能力方面有一定局限性。如圖1是同一網(wǎng)絡(luò)受到相同攻擊后的兩種不同破碎狀態(tài)：左圖破碎為6個(gè)不連通子圖，巨片包含5個(gè)節(jié)點(diǎn)，右圖破碎為4個(gè)不連通子圖，巨片包含3個(gè)節(jié)點(diǎn)。明顯發(fā)現(xiàn)，右圖的子圖(節(jié)點(diǎn)數(shù)大于1)內(nèi)部節(jié)點(diǎn)間仍可以局部溝通，而左圖的子圖多數(shù)為孤立幾點(diǎn)，完全無(wú)法與其他節(jié)點(diǎn)溝通。所以，左圖的巨片雖包含較多節(jié)點(diǎn)，但整體破碎程度遠(yuǎn)高于右圖，攻擊策略對(duì)其的攻擊效果更好。本文結(jié)合巨片和連通子圖數(shù)目，希望較全面的分析網(wǎng)絡(luò)面對(duì)蓄意攻擊時(shí)的魯棒性。

圖1 相同攻擊策略對(duì)同一網(wǎng)絡(luò)造成的兩種破碎狀態(tài)

1.3 網(wǎng)絡(luò)魯棒性R-指標(biāo)

本文采用R-指標(biāo)[8]刻畫網(wǎng)絡(luò)的魯棒性，其思想是移除網(wǎng)絡(luò)一定比例的節(jié)點(diǎn)后，計(jì)算網(wǎng)絡(luò)中屬于巨片的節(jié)點(diǎn)數(shù)目：

(5)

其中，N表示網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)，δ(Q)表示移除Q=qN(q為移除的節(jié)點(diǎn)比例)節(jié)點(diǎn)后巨片包含的節(jié)點(diǎn)數(shù)占網(wǎng)絡(luò)總數(shù)N的比例，即巨片的相對(duì)大小。1/N實(shí)現(xiàn)不同尺度的網(wǎng)絡(luò)可以進(jìn)行魯棒性的歸一化比較。不論何種算法，在星型網(wǎng)絡(luò)中，R取最小值1/N，在完全圖中R取最大值0.5。由此，我們可以進(jìn)一步定義：

V=0.5-R

(6)

式(6)表示網(wǎng)絡(luò)對(duì)于移除節(jié)點(diǎn)后的脆弱性：V越大說(shuō)明網(wǎng)絡(luò)對(duì)于攻擊越脆弱，即采用的攻擊策略的效果越好。

2 數(shù)據(jù)介紹

實(shí)驗(yàn)所用數(shù)據(jù)集分為兩大類：開放數(shù)據(jù)集(非微博數(shù)據(jù))和作者爬取的新浪微博數(shù)據(jù)集。依據(jù)實(shí)驗(yàn)需要，原始網(wǎng)絡(luò)統(tǒng)一處理為無(wú)向無(wú)權(quán)網(wǎng)絡(luò)。

2.1 開放數(shù)據(jù)集

實(shí)驗(yàn)一共采用5個(gè)不同規(guī)模的開放數(shù)據(jù)集[12]。海豚網(wǎng)絡(luò)和線蟲神經(jīng)網(wǎng)絡(luò)(有向含權(quán)網(wǎng)絡(luò))屬于小型網(wǎng)絡(luò)，科學(xué)家合作網(wǎng)絡(luò)、美國(guó)西部電力網(wǎng)絡(luò)和路由器自治層次網(wǎng)絡(luò)屬于中大型網(wǎng)絡(luò)，具體統(tǒng)計(jì)性質(zhì)見表1所示。其中，N和M分別表示網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和邊數(shù)，為網(wǎng)絡(luò)的平均度，l為平均路徑長(zhǎng)度，GN為巨片包含節(jié)點(diǎn)數(shù)，CN為連通子圖數(shù)目。

表1 開放數(shù)據(jù)集網(wǎng)絡(luò)的拓?fù)湫再|(zhì)

2.2 新浪微博數(shù)據(jù)集

本文采集新浪微博的實(shí)際用戶數(shù)據(jù)，構(gòu)建用戶關(guān)系網(wǎng)絡(luò)。為了增強(qiáng)實(shí)驗(yàn)結(jié)果的可靠性、避免新浪微博API的限制，采用基于HTTP協(xié)議的網(wǎng)絡(luò)爬蟲獲取數(shù)據(jù)集，分別從作者的所有轉(zhuǎn)發(fā)用戶出發(fā)，逐層爬取粉絲和關(guān)注用戶，構(gòu)成原始的數(shù)據(jù)集。然后經(jīng)過(guò)數(shù)據(jù)的預(yù)處理，得到實(shí)驗(yàn)所需的網(wǎng)絡(luò)數(shù)據(jù)集。構(gòu)建的微博數(shù)據(jù)集的網(wǎng)絡(luò)拓?fù)涮卣魅绫?所示(d為網(wǎng)絡(luò)直徑、r為平均聚類系數(shù)，其他符號(hào)同上表)。從表2發(fā)現(xiàn)網(wǎng)絡(luò)平均路徑長(zhǎng)度位于4到6之間，網(wǎng)絡(luò)直徑均為12，說(shuō)明微博數(shù)據(jù)集均具有小世界的特征[13]。文中實(shí)驗(yàn)不區(qū)分邊的有向性。

表2 微博有向傳播網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

圖2是數(shù)據(jù)集的度、入度和出度的累計(jì)概率分布。從圖中可知，度、入度和出度均出現(xiàn)首尾分段冪律分布的現(xiàn)象，其中，度和出度在尾部的分布類似，出度的分布更加平滑。微博數(shù)據(jù)集均符合復(fù)雜網(wǎng)絡(luò)的冪律分布特性[14]，說(shuō)明新浪微博滿足復(fù)雜網(wǎng)絡(luò)的無(wú)標(biāo)度特性，驗(yàn)證了爬取的微博數(shù)據(jù)的有效性。

圖2 微博數(shù)據(jù)集的度、入度和出度的累計(jì)分布圖

3 實(shí)驗(yàn)結(jié)果與分析

本文對(duì)構(gòu)建的網(wǎng)絡(luò)從某一中心性值最高的節(jié)點(diǎn)開始，迭代遞增比例的順序移除節(jié)點(diǎn)。通過(guò)巨片的相對(duì)大小和連通子圖數(shù)目直觀分析網(wǎng)絡(luò)的魯棒性，再依據(jù)V-指標(biāo)量化分析網(wǎng)絡(luò)的魯棒性。

3.1 開放數(shù)據(jù)集網(wǎng)絡(luò)

圖3-圖5為數(shù)據(jù)集在遭到蓄意攻擊時(shí)的不同情況。經(jīng)分析，面對(duì)相同的攻擊不同的網(wǎng)絡(luò)呈現(xiàn)某些共性，比如巨片相對(duì)大小的下降趨勢(shì)呈現(xiàn)先快后慢，連通子圖數(shù)目先遞增至最值，然后遞減。然而，不同網(wǎng)絡(luò)又表現(xiàn)出各自的差異性。

圖3 海豚網(wǎng)絡(luò)

圖4 科學(xué)家合作網(wǎng)絡(luò)、電力網(wǎng)絡(luò)和路由器自治網(wǎng)絡(luò)

圖5 線蟲神經(jīng)網(wǎng)絡(luò)

從圖3可以看出海豚網(wǎng)絡(luò)對(duì)不同的攻擊策略有明顯差異。巨片和連通子圖數(shù)目均表明度和介數(shù)攻擊策略優(yōu)于緊密度和特征向量攻擊策略，其中度攻擊策略產(chǎn)生較多的碎片，介數(shù)攻擊策略生成較小的巨片，兩種策略各有優(yōu)缺點(diǎn)。

從圖4結(jié)果分析，可以看到科學(xué)家合作網(wǎng)絡(luò)、電力網(wǎng)絡(luò)和路由器自治網(wǎng)絡(luò)遭到蓄意攻擊時(shí)，巨片大小呈現(xiàn)較快速的下降趨勢(shì)。其中，科學(xué)家合作網(wǎng)絡(luò)若僅分析巨片，發(fā)現(xiàn)度、介數(shù)和緊密度攻擊策略的效果類似。進(jìn)一步分析連通子圖數(shù)目，在移除節(jié)點(diǎn)的百分比較低時(shí)，介數(shù)攻擊策略產(chǎn)生顯著較多碎片，其攻擊效果優(yōu)于度策略，此外清晰得知緊密度和特征向量攻擊策略較差。電力網(wǎng)絡(luò)和航空網(wǎng)絡(luò)屬于社會(huì)生產(chǎn)生活過(guò)程中演化出的網(wǎng)絡(luò)。電力網(wǎng)絡(luò)從巨片角度出發(fā)，度和介數(shù)攻擊策略效果類似，均好于緊密度和特征向量，結(jié)合連通子圖數(shù)目分析，可以看出度攻擊策略優(yōu)于介數(shù)策略。而且明顯發(fā)現(xiàn)電力網(wǎng)絡(luò)移除少量高中心性值節(jié)點(diǎn)(少于10%節(jié)點(diǎn))可對(duì)網(wǎng)絡(luò)產(chǎn)生嚴(yán)重后果。路由器自治網(wǎng)絡(luò)的攻擊效果明顯分為兩大類，其中度和介數(shù)攻擊策略屬于較好一類，其攻擊效果基本相同，即對(duì)網(wǎng)絡(luò)造成迅速和嚴(yán)重的破壞，極少量節(jié)點(diǎn)(甚至不到5%節(jié)點(diǎn))可導(dǎo)致網(wǎng)絡(luò)的整體破碎，這一現(xiàn)象與路由器網(wǎng)絡(luò)的構(gòu)造緊密相關(guān)，少量的路由器占據(jù)著網(wǎng)絡(luò)的大量重要位置。

從圖5發(fā)現(xiàn)線蟲神經(jīng)網(wǎng)絡(luò)遭到蓄意攻擊時(shí)呈現(xiàn)有趣的不同現(xiàn)象。巨片大小下降緩慢、碎片數(shù)目上升也較慢，這表明該網(wǎng)絡(luò)具有較強(qiáng)的魯棒性：移除小部分節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的完整性產(chǎn)生的影響較小。但移除的節(jié)點(diǎn)數(shù)到達(dá)一定程度，對(duì)網(wǎng)絡(luò)的破壞程度便會(huì)突升。這一現(xiàn)象或許與生物神經(jīng)網(wǎng)絡(luò)的特性相關(guān)，生物神經(jīng)網(wǎng)絡(luò)是長(zhǎng)期進(jìn)化的結(jié)果。

從不同網(wǎng)絡(luò)遭到蓄意攻擊時(shí)的不同現(xiàn)象發(fā)現(xiàn)，采用度和介數(shù)攻擊策略普遍較好。我們也注意到，結(jié)合巨片和連通子圖數(shù)目可以更加清晰、有效地分析攻擊效果。巨片描述網(wǎng)絡(luò)的最大連通子圖內(nèi)部的溝通能力，屬于局部指標(biāo)；連通子圖數(shù)目從網(wǎng)絡(luò)的整體破碎程度出發(fā)，描述破碎網(wǎng)絡(luò)“殘留”的“整體”溝通能力，屬于粗粒度的全局指標(biāo)。

3.2 微博數(shù)據(jù)集

除采用開放數(shù)據(jù)集，本文繼續(xù)對(duì)微博數(shù)據(jù)集進(jìn)行魯棒性研究，實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 新浪微博網(wǎng)絡(luò)

從圖6發(fā)現(xiàn)，微博網(wǎng)絡(luò)對(duì)蓄意攻擊表現(xiàn)出與前文不同的現(xiàn)象。對(duì)于微博網(wǎng)絡(luò)，圖6表明度和緊密度攻擊策略更好，均優(yōu)于介數(shù)(較淺虛線)和特征向量攻擊策略，且緊密度(較深虛線)攻擊策略的攻擊效果不同于度策略的攻擊效果。其中，移除節(jié)點(diǎn)比例較低時(shí)，度策略均優(yōu)于緊密度策略，但在移除節(jié)點(diǎn)比例20%左右時(shí)，度攻擊策略略遜于緊密度攻擊策略。此外，采用緊密度攻擊策略，微博網(wǎng)絡(luò)在移除25%～35%的節(jié)點(diǎn)區(qū)間內(nèi)，巨片大小下降速度迅速減緩，同時(shí)碎片數(shù)目不再增加，反而呈現(xiàn)持續(xù)遞減趨勢(shì)，一段過(guò)程后才回升。

我們定性解釋微博網(wǎng)絡(luò)的現(xiàn)象，圖7是各中心性的分布圖?？梢钥闯觯活愑休^多的高中心性值節(jié)點(diǎn)，另一類有較少的高中心性值節(jié)點(diǎn)。對(duì)于度分布，高中心性值的節(jié)點(diǎn)數(shù)目最少，該現(xiàn)象與文獻(xiàn)[3]中描述一致，即大部分節(jié)點(diǎn)的度相對(duì)較小僅少量節(jié)點(diǎn)的度相對(duì)較大。介數(shù)和特征向量中心性均擁有較多的高中心性節(jié)點(diǎn)，而緊密度的高中心性值節(jié)點(diǎn)較少。同時(shí)也發(fā)現(xiàn)，不同緊密度值均對(duì)應(yīng)一定小數(shù)目的節(jié)點(diǎn)，特別是統(tǒng)計(jì)發(fā)現(xiàn)在0.26～0.28值之間集中了較多節(jié)點(diǎn)，這與圖6中緊密度出現(xiàn)的局部(巨片平滑穩(wěn)定)碎片數(shù)目不升反降密切有關(guān)。

圖7 微博網(wǎng)絡(luò)魯棒性現(xiàn)象探究解釋

3.3 綜合分析

為了定量分析開放數(shù)據(jù)集和爬取的微博數(shù)據(jù)集的魯棒性，本文計(jì)算網(wǎng)絡(luò)脆弱性V-指標(biāo)，結(jié)果如表3所示。

表3 網(wǎng)絡(luò)受到同步蓄意攻擊的V-指標(biāo)

從表3得知，非微博網(wǎng)絡(luò)(開放數(shù)據(jù)集)采用度和介數(shù)攻擊策略對(duì)應(yīng)的V值大于緊密度和特征向量攻擊策略。微博網(wǎng)絡(luò)采用度和緊密度攻擊策略對(duì)應(yīng)的V值大于介數(shù)和特征向量攻擊策略。此外，電力和路由器自治網(wǎng)絡(luò)的V值大于0.4，面對(duì)蓄意攻擊的影響更大，這一結(jié)果和日常生活的直覺一致；線蟲神經(jīng)網(wǎng)絡(luò)的V值最小，面對(duì)蓄意攻擊時(shí)的魯棒性最強(qiáng)；量化的分析結(jié)果與前文分析的結(jié)論一致。

4 結(jié) 語(yǔ)

復(fù)雜網(wǎng)絡(luò)的部分節(jié)點(diǎn)失效后，網(wǎng)絡(luò)能否維持其功能通常與網(wǎng)絡(luò)結(jié)構(gòu)的完整性有關(guān)。本文在常用的巨片指標(biāo)的基礎(chǔ)上，引入連通子圖數(shù)目來(lái)分析網(wǎng)絡(luò)遭到攻擊后的破碎情況。研究發(fā)現(xiàn)，非網(wǎng)絡(luò)微博在面對(duì)度和介數(shù)攻擊策略時(shí)，破壞程度較嚴(yán)重；微博網(wǎng)絡(luò)采用度和緊密度攻擊策略得到的攻擊效果優(yōu)于采用介數(shù)和特征向量攻擊策略。

[1] 鄧宏鐘,吳俊,李勇,等.復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)系統(tǒng)抗毀性影響研究[J].系統(tǒng)工程與電子技術(shù),2009,30(12):2425-2428.

[2] Morohosi H.Measuring the network robustness by Monte Carlo estimation of shortest path length distribution[J].Mathematics and Computers in Simulation,2010,81(3):551-559.

[3] Albert R,Jeong H,Barabási A L.Error and attack tolerance of complex networks[J].Nature,2000,406(6794):378-382.

[4] 柳虹,周根貴,傅培華,等.基于供應(yīng)鏈網(wǎng)絡(luò)的傳遞攻擊策略研究[J].計(jì)算機(jī)科學(xué),2013,40(7):98-101.

[5] 周漩,張鳳鳴,周衛(wèi)平,等.利用節(jié)點(diǎn)效率評(píng)估復(fù)雜網(wǎng)絡(luò)功能魯棒性[J].物理學(xué)報(bào),2012,61(19):190201.

[6] 王凱.基于復(fù)雜網(wǎng)絡(luò)理論的電網(wǎng)結(jié)構(gòu)復(fù)雜性和脆弱性研究[D].華中科技大學(xué),2011.

[7] Schneider C M,Moreira A A,Andrade J S,et al.Mitigation of malicious attacks on networks[J].Proceedings of the National Academy of Sciences,2011,108(10):3838-3841.

[8] Iyer S,Killingback T,Sundaram B,et al.Attack robustness and centrality of complex networks[J].PloS one,2013,8(4):e59613.

[9] 吳敏,李慧,張柯,等.BBS用戶回復(fù)網(wǎng)絡(luò)的抗毀性分析[J].計(jì)算機(jī)科學(xué),2012,39(S6):28-30.

[10] Crucitti P,Latora V,Marchiori M,et al.Error and Attack Tolerance of Complex Networks[J].Physica,2004,340:388-394.

[11] Barrat A,Barthelemy M,Pastor-Satorras R,et al.The architecture of complex weighted networks[J].Proceedings of the National Academy of Sciences of the United States of America,2004,101(11):3747-3752.

[12] Newman M E J.datsets.http://www-personal.umich.edu/～mejn/netdata/.

[13] Watts D J,Strogatz S H.Collective dynamics of ‘small-world’networks[J].Nature,1998,393(6684):440-442.

[14] Newman M E J,Park J.Why social networks are different from other types of networks[J].Physical Review E,2003,68(3):036122.

RESEARCH ON ROBUSTNESS AND CENTRALITY METRICS OF COMPLEX NETWORKS

Lu Jingqiao1Fu Xiufen1Meng Zaiqiao2

1(SchoolofComputer,GuangdongUniversityofTechnology,Guangzhou510006,Guangdong,China)2(SchoolofinformationScienceandTechnology,SunYat-senUniversity,Guangzhou510006,Guangdong,China)

Network’s robustness refers to the capability of network to remain its functionality unchanged when suffering random failures or malicious attacks, it is of important significance to understand the impact of partial structural failure in complex network on the structure and function of networks. Aiming at different open datasets and the Sina microblogging datasets which is derived by crawling, we concentrated on analysing the impact of malicious attacks on the network structure by calculating the indices of giant component and the number of connected subgraph after removing a portion of nodes, and found that the degree attack strategy had a great impact on different network structures, while closeness and betweenness attack strategies had distinct impact on network structure. Experiment showed that in malicious attacking against non-microblogging network, to adopt the degree and betweenness attacking strategies simultaneously has better effect, while for microblogging network the degree and closeness attacking strategies should be used.

Complex networks Centrality metrics Robustness Malicious attack

2014-08-25。廣東省科技計(jì)劃項(xiàng)目(2012B091000173)。陸靖橋，碩士生，主研領(lǐng)域：復(fù)雜網(wǎng)絡(luò)，數(shù)據(jù)挖掘。傅秀芬，教授。蒙在橋，博士生。

TP301

A

10.3969/j.issn.1000-386x.2016.04.070