復雜網絡的魯棒性與中心性指標的研究

陸靖橋 傅秀芬 蒙在橋

復雜網絡的魯棒性與中心性指標的研究

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

1(廣東工業(yè)大學計算機學院 廣東 廣州 510006)

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

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

復雜網絡 中心性指標 魯棒性 蓄意攻擊

0 引 言

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

復雜系統(tǒng)強調從結構角度分析系統(tǒng)的功能，事實上復雜系統(tǒng)的拓撲結構是系統(tǒng)所具有的內在、本質的特性，系統(tǒng)的功能與其拓撲密切相關。復雜系統(tǒng)可能會受到各種事件的攻擊，影響系統(tǒng)正常的結構和功能。如2003年8月，美國俄亥俄州克利夫蘭市的超高壓輸電線路相繼過載燒斷使得上千萬人陷入黑暗長達15小時，經濟損失高達數(shù)百億美元。再如，2008年1月的大雪造成中國南方的高速道路、各個城市的街道陷入癱瘓，造成行人和物資無法流通，給社會和經濟帶來了極大的損失。因此，研究復雜網絡的魯棒性具有重要的理論和現(xiàn)實意義。

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

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

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

1 相關定義

1.1 中心性指標

度刻畫網絡的局部特征，屬于無標度網絡拓撲結構的最基本參數(shù)，用于描述靜態(tài)網絡節(jié)點的直接影響力。節(jié)點v的度kv定義為與其直接相連的節(jié)點數(shù)目，節(jié)點的kv越大說明該節(jié)點越重要。在擁有n個節(jié)點的有向網絡中，節(jié)點最大的可能度為n-1，則節(jié)點v的度中心性歸一化值為:

(1)

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

(2)

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

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

(3)

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

(4)

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

1.2 連通子圖

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

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

圖1 相同攻擊策略對同一網絡造成的兩種破碎狀態(tài)

1.3 網絡魯棒性R-指標

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

(5)

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

V=0.5-R

(6)

式(6)表示網絡對于移除節(jié)點后的脆弱性：V越大說明網絡對于攻擊越脆弱，即采用的攻擊策略的效果越好。

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

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

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

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

表1 開放數(shù)據(jù)集網絡的拓撲性質

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

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

表2 微博有向傳播網絡的拓撲結構

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

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

3 實驗結果與分析

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

3.1 開放數(shù)據(jù)集網絡

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

圖3 海豚網絡

圖4 科學家合作網絡、電力網絡和路由器自治網絡

圖5 線蟲神經網絡

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

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

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

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

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

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

圖6 新浪微博網絡

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

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

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

3.3 綜合分析

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

表3 網絡受到同步蓄意攻擊的V-指標

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

4 結 語

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

[1] 鄧宏鐘,吳俊,李勇,等.復雜網絡拓撲結構對系統(tǒng)抗毀性影響研究[J].系統(tǒng)工程與電子技術,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] 柳虹,周根貴,傅培華,等.基于供應鏈網絡的傳遞攻擊策略研究[J].計算機科學,2013,40(7):98-101.

[5] 周漩,張鳳鳴,周衛(wèi)平,等.利用節(jié)點效率評估復雜網絡功能魯棒性[J].物理學報,2012,61(19):190201.

[6] 王凱.基于復雜網絡理論的電網結構復雜性和脆弱性研究[D].華中科技大學,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用戶回復網絡的抗毀性分析[J].計算機科學,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。廣東省科技計劃項目(2012B091000173)。陸靖橋，碩士生，主研領域：復雜網絡，數(shù)據(jù)挖掘。傅秀芬，教授。蒙在橋，博士生。

TP301

A

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