張 昕,郭 陽
遼寧大學 信息學院,沈陽110036
隨著信息技術的發展復雜網絡已經深入到人類社會的各個方面,如社交網絡、通信網絡與互聯網、物網絡、交通網絡、經濟與金融網絡等。而網絡時刻遭受著來自不同方面的、不同程度的、蓄意或無意的攻擊,這就需要對網絡進行抗毀性分析[1],合理地衡量整個網絡抵御攻擊的能力,從而得到更有針對性地部署防范策略,有效地減少攻擊損失。所以,復雜網絡中的抗毀性[2]研究具有重要的理論價值和應用價值。現有的相關研究主要從三個方面進行[3]:一是基于圖論的抗毀性研究,如粘連度、完整度、膨脹系數、核度等,考量了整個網絡的抗毀性;二是基于解析的抗毀性研究,是采用渝滲理論將隨機圖中研究的問題滲流變換后進行分析研究;三是基于仿真的抗毀性研究,主要是對隨機網絡模型[4]和無標度網絡模型[5-6]采用不同類型的攻擊策略進行攻擊后,對其拓撲結構的變化進行研究。考慮到在復雜網絡中,核心節點一旦遭到攻擊,有可能產生嚴重后果,甚至摧毀整個網絡,因此本文從基于節點重要性[7]方面進行考量,研究復雜網絡的抗毀性。本文結合多種網絡拓撲結構,重新定義了節點重要性評估指標,提出了基于局部的介-度中心性指標,進而構建出介-度熵測度模型,提出衡量網絡抗毀性的介-度熵算法。仿真實驗結果表明,與傳統的攻擊策略相比較,本文提出的介-度中心性攻擊策略破壞網絡的能力更強,由此可知本文提出的基于局部的介-度中心性指標及介-度熵度量方法可以更好地衡量和評估網絡的抗毀性。
在復雜網絡中,網絡的生產性為隨機性故障發生后其仍可以正常工作的能力;網絡的可靠性為網絡被攻擊后其自身糾錯并正常工作的能力。網絡的隨機性攻擊會影響網絡的生產性,而選擇性攻擊則會影響網絡的可靠性。目前,網絡的抗毀性能研究主要集中在對已知的確定性的網絡進行選擇性攻擊,從而評估網絡的可靠性。但在實際中對于網絡的損害也有可能是其自身因素所造成的。
目前,許多研究人員從不同角度提出了抗毀性測度模型,確定了網絡抗毀性度量,并量化分析了網絡抗毀性。文獻[8]中利用節點度值的大小對隨機網絡的魯棒性和脆弱性進行了評估和分析;文獻[9]在有權網絡中利用邊的數量及權值的大小評估網絡中節點的重要程度,進而構建網絡抗毀模型;文獻[10]中分析了節點的介數中心性對大規模復雜網絡中節點重要程度的影響;文獻[11]提出了刪除網絡中節點后最短路徑變化的評估方法;文獻[12]中提出了針對無標度網絡模型的抗毀性測度分析;文獻[13]分別從節點重要性和網絡拓撲結構的變化方面對網絡的抗毀性的影響進行了研究;文獻[14]研究了拓撲結構確定的加權復雜網路的抗毀性;文獻[15]采用基于平均連通度及粘聚度的抗毀性測度方法評估了賦權網絡的抗毀性。
在基于節點重要性的抗毀性測度研究中,文獻[8]雖然是最簡單直接的方式,但該方式并不全面;文獻[9]局限于有權網絡;文獻[10]需要考慮網絡自身的拓撲結構;文獻[11]在網絡遭受選擇性攻擊后分析了網絡的連通性,但未考慮網絡中最短路徑的改變對節點重要性的影響。在基于鏈路的抗毀性測度研究中,文獻[12]中當隨機對網絡中的鏈路進行刪除時,有可能會破壞無標度網絡的原有特性。文獻[13]中衡量節點重要性主要采用節點的度分布,未結合節點其他重要性指標來進行抗毀性研究;文獻[14]的研究無法適用于拓撲結構不確定的網絡。
目前研究者們對節點的重要性評估主要采用全局中心性度量方法,如度中心性、介數中心性等。基于局部的節點重要性度量方法較少,已有的局部介數中心性[16]度量方法,是將節點的介數中心性的求解范圍從全局轉變為約束在k步內進行求解。在現實網絡中節點的重要性需要從多方面進行考量,節點的度中心性和介數中心性雖然都可以在某種程度上反映出一個節點在網絡中的重要程度,而且介數較高的節點的度值一般也比較高,但節點的度值和介數的關聯程度并不高,所以可以對節點的度值和介數進行綜合考量,得到節點重要性的衡量指標,可以更好地對節點的重要性進行評估。因此,本文對節點的局部介數中心性和度中心性進行了綜合考量,提出介-度中心性指標(Betweenness-Degree Centrality,K-BDC),用以評估網絡中節點的重要程度。同時兼顧聚集系數對節點重要程度的影響,進一步給出節點的抗毀性指標,并構建介-度熵度量,進而提出介-度熵(Betweenness-Degree Entropy,BDE)算法,衡量整個網絡的抗攻擊能力。
在對計算機抗干擾性進行分析時,需要計算所有節點對之間的最短路徑,計算復雜度較高,故而本文在Brandes[17]針對全局介數中心性算法基礎上,引入最長距離約束k,將全局節點對之間的最短路徑求解轉化為k步內最短路徑求解,縮小了求解最短路徑的規模,提升了計算效率。并綜合考慮節點的介數中心性與節點的度中心性,定義了基于局部的介-度中心性指標,用來衡量節點在網絡中的重要性。
復雜網絡可抽象為拓撲圖表示,記為圖G=(V,E),其中V表示為節點的集合,E表示為連邊的集合。
定義1局部度相關系數:圖G中節點v的局部度相關系數是指在圖G所有長度不超過k(k>1)的路徑中,節點v的度在每條路徑中占比值的總和,記為Tk(v),其值由式(1)確定。

式中,dv表示節點v的度值,L(s,t|v)表示以節點s與節點t為兩端點并經過節點v的路徑集合,l表示其中一條路徑。
定義2局部介-度中心性指標:令p(v)表示圖G中通過節點v的所有長度不超過k的路徑條數,σ(s,t)表示從節點s到節點t的最短路徑數量,σ(s,t|v)表示從節點s通過節點v后到達節點t的最短路徑數量,則圖G中節點v的局部介-度中心性指標Ck(v)值由式(2)確定。

對比節點的介數中心性度量方法,K-BDC指標對節點的度值和介數進行了綜合考量,從不同的角度綜合評估了節點的重要性。由于節點度值僅能體現鄰接節點數目,對節點重要程度的刻畫不足,因此本文提出局部度相關系數概念,考察節點度在多條路徑中的比重。在此基礎上結合節點介數,進一步提出局部介-度中心性指標,并考慮到度相關系數相比節點介數計算結果相差一個量級,因此引入局部路徑數目,使二者對局部介-度中心性指標的影響更為均衡。
分別采用介數中心性及本文提出的介-度中心性指標對圖1所示網絡中的節點中心性進行求解,所得結果見表1。

圖1 示意網絡圖

表1 不同中心性度量方法求得的節點中心性對比
由表1可以看出,圖1中節點1、2、3的介數中心性的值相同,表明這3個節點在網絡中的重要程度相同,若對該網絡進行蓄意攻擊[18],當節點1、2、3失效后,剩余節點之間不再存在連邊,網絡完全癱瘓。而圖1中節點2、3的介-度中心性的值相同,當這2個節點失效后,即可使整個網絡癱瘓。由該對比操作結果可知,本文定義的介-度中心性指標在網絡抗毀性上對節點重要性的刻畫準確程度高于介數中心性度量方法。同時,也說明本文提出的局部介-度中心性雖然是通過最長距離約束k對介數中心性進行了近似計算,但求得的節點重要性排序結果依然合理有效。由于在求解時有效地約束了路徑長度,使得其在大規模網絡上的運行效率得到了較大的提升。
在復雜網絡中,處于關鍵位置的核心節點通常具有信息傳輸量大、信息交換頻繁等特點。所以核心節點的損壞可能會影響到整個網絡的穩定性。故而本文基于節點重要性相關研究構建網絡抗毀性測度模型。結合已提出的節點介-度中心性指標,提出節點抗毀性指標。進而提出介-度熵(BDE)度量方法,并進一步給出BDE算法及其時間復雜度分析。
在圖論中,聚集系數通常用于刻畫圖中節點聚集成團的程度,即衡量圖中一個節點的鄰居節點之間相互連接的緊密程度,節點在網絡中越靠近核心位置,其鄰居節點之間存在連邊的可能性就越大,節點就越可能具有較高的度值和聚集系數,聚集系數在一定程度上刻畫出節點在網絡中所處的位置,而核心節點一般距離網絡的中心位置較近,其聚集系數也較高,所以采用聚集系數可以更全面地描述節點的重要性。因而可以通過介-度中心性指標和聚集系數對節點的重要性進行綜合考量,以期得到的更符合現實網絡的節點抗毀性指標。
定義3節點抗毀性:是指網絡中節點v的毀壞與整個網絡毀壞的關聯程度,記為S(v),其值越大,則該節點的毀壞越易導致整個網絡的毀壞。計算方法如式(3)所示,其中CLv表示節點v的聚集系數,Ck(v)為節點v的局部介-度中心性指標。

節點的抗毀性指標的準確性與最長距離約束k的取值直接相關,為了準確地刻畫出節點v在局部范圍內的介數中心性,最大距離約束k隨著網絡的規模增加而增大。而現實網絡具有小世界性質,通過實驗分析和理論依據,在網絡規模較大時,取k=6是一個可以取得較準確計算結果的值。隨著k值的取值增大,由最大距離約束k所確定的局部范圍也會隨之增加,直到k增大到某一閾值時,節點v的局部介數中心性計算會退化為對全局介數中心性的計算。以v為局部中心點的局部最短路徑求解范圍也會轉化為對網絡全局最短路徑的計算。節點抗毀性指標體現出網絡中的單個節點抵御攻擊能力的強弱,在此基礎上可以定義網絡抗毀性度量,衡量整個網絡的抗打擊能力。
定義4介-度熵度量:通過對節點抗毀性分布的差異性進行評估,衡量整個網絡的抗打擊能力,記作BDE。介-度熵度量結果與網絡的抗毀性能成正比,與節點間抗毀性分布成反比。即節點間抗毀性分布差異越小,網絡抵御選擇性攻擊的能力越強,介-度熵度量值越大。反之亦然。計算方法如式(4)所示:

該度量表明節點抗毀性分布情況對網絡抵御選擇性攻擊能力強弱的影響。綜合考察了節點的度、局部介數中心性、聚集系數對網絡抗毀性能的影響,得到較全面的網絡的抗毀性度量結果。
本節給出計算節點抗毀性指標與介-度熵度量的BDE算法,該算法有2個輸入參數,分別為網絡G和最長距離約束k。通常來說,最長距離約束k與網絡G的規模具有一定相關性,可根據具體輸入網絡酌情定值。在算法形式化描述中,Node[s-t]為從節點s出發到節點t,所經過的節點集合;Degree[s-t]為從節點s出發到節點t,所經過節點的度值總和。
算法形式化描述如下:
步驟1 START
1.FileOpen(G.edges)
2. FileRead(&u,&v);
3. Matrix[u][v]=Matrix[v][u]=1;
4. Degree[u]++;
5. Degree[v]++;
6.For(i<G.nodes)
7.If(Degree[i]>1)
8. 計算各節點的聚集系數CL[s]
步驟1 FINISH
步驟1讀入圖G的數據文件,將其存入鄰接矩陣中,并計算每個節點的度值,同時得到度值大于1的節點的聚集系數。其中Matrix[N][N]為鄰接矩陣,用來保存圖G的節點信息,Degree[N]用來保存節點的度信息,CL[s]用來保存節點的聚集系數。
步驟2 STRAT
9. BFS(s) s∈V
10. Node[s]←s;
11.If dist[t]<=k
12. Node[s]←t,Q←t
13. If(!Pred Map.containsKey(Node[s-t]))
14. Pred Map.key=Node[s-t]
15. Pred Map.value=Degree[s-t];
16. σ[s]++;
17. t[s]+=Degree[s]/Degree[s-t];
步驟2 FINISH
步驟2求解度相關系數。采用Map結構存儲節點的路徑及路徑上節點的度值總和。其中key為節點的路徑Node[s-t],value為路徑上的節點度值總和Degree[s-t]。dist[t]表示從節點s到節點t之間的最短路徑;Q為滿足最長距離約束k的隊列;σ[s]表示記錄從節點s開始遍歷的滿足最長距離約束k的路徑條數;t[s]表示節點s在整條路徑中節點度所占比值。
步驟3 START
18. While(!Q.Empty())
19. 出隊列w←Q;入棧S←w;
20. GOTO步驟2
21. If Node[w-v]∈Node[s]&&s∈Node[w-v]
22. σ[s]++;
23. t[s]+=Degree[s]/Degree[w-v];
24. If dist[w]=∞∩Exist(dist[w-v])
25. dist[w]←dist[v]+1;
26. If dist[w]<k&&(!Q.contains(w))
27. 入隊列Q←w;
28. If dist[w]=dist[v]+1
29. σ[w]←σ[w]+ω(s,w)?σ[v];
30. Pred[w]←v;
31.For v∈V
32. δ[v]←0;
33.While(!S.Empty())
34. 出棧w←S;
35. For v∈Pred[w]
36. δ[v]←σ[v]/σ[w]?((1+δ[w]);
37. If w≠s Then
38. C(w)+=δ[w];
39. Ck(s)=t[s]/σ[s]?C(s);
40. Ck+=Ck(s);
步驟3 FINISH
步驟3利用網絡中前置節點的點對依賴求解節點的介-度中心性。其中ω(s,w)表示從節點s到節點w之間的路徑的條數。其中序號18~20為初始化Q中節點信息;序號21~23為計算節點s在整條路徑中節點度所占比值;序號24~30為求得s和w的中繼節點v及從s經過v再到w的最短路徑條數;序號31~40依據最短路徑個數計算點對依賴,進而獲得局部介-度中心性的值。
步驟4 START
41. BFS(s) s∈V
42. S(s)=CL[s]*Ck(s)/Ck;
43. E+=(-S(s)ln S(s));
44. return S,E;
步驟4 FINISH
步驟4計算整個網絡的介-度熵值。由求解得到的節點的聚集系數及介-度中心性,推導出節點的抗毀度,進而求得整個網絡的介-度熵值。
在BDE算法中,計算節點的度相關系數由于引入最長距離約束k,使得其計算的時間復雜度近似接近于O(n2),局部介-度中心性指標的時間復雜度由于將全局介數中心性計算轉化為局部介數中心性計算,節點數量遠遠小于整個網絡的節點數量,可以快速計算出局部的介數中心性。所以,局部介-度中心性指標的時間復雜度近似接近于O(n2)。從而可以得出BDE算法的時間復雜度根據最長距離約束k的選擇會有一定的差異,當k選擇為常量時,BDE算法的時間復雜度不超過O(n2)。
采用具有無標度網絡和小世界網絡特性的生成網絡進行仿真實驗,網絡節點數量分別為200和5 000,通過對節點攻擊(在網絡中去除節點)后網絡連通程度的變化情況進行研究,得到網絡在不同攻擊策略下的抗毀性能。實驗中采用隨機攻擊和蓄意攻擊方式去除仿真網絡中的節點,其中蓄意攻擊方式采取基于度中心性優先攻擊、基于介數中心性優先攻擊以及基于介-度中心性優先攻擊三種攻擊策略。分別對比不同的網絡規模及攻擊策略下仿真網絡所表現出的抗毀性差異。一般來說,對于規模較小的網絡選擇以去除的節點個數為研究對象,可采用最大連通子圖;對于規模較大的網絡選擇以去除節點的比例為研究對象,可采用平均反測地線距離。因此,本文采用上述兩種指標作為評估不同規模網絡連通程度的度量。
然后生成節點數量分別為30和5 000,且連接概率不同的模擬網絡進行抗毀性評估,通過對比不同網絡的介-度熵度量與網絡的實際抗毀性,論證該度量的合理性。
在網絡中,連通子圖表示其內部任意兩個節點之間都存在相連路徑的圖;非連通子圖則表示其內部存在兩個或以上節點之間無相連路徑的圖。在圖中具有最多節點的連通子圖稱為最大連通子圖。在一個連通的網絡中,網絡的結構隨著節點的變化而不斷改變,連通子圖有可能分裂為多個子圖或者合并成一個子圖。采用最大連通子圖對網絡連通程度的進行度量,可以有效說明網絡受損的程度。
分別生成節點數量為200的2個具有不同網絡特性仿真網絡。具有小世界網絡特性的生成網絡的節點度值分布相對比較均勻,而具有無標度特性的生成網絡的節點度值隨機性較大,且網絡中小部分節點具有較高的度值。在無標度網絡中度值為1的節點比重較大,而在小世界網絡中度值為4的節點比重較大。實驗中計算局部介-度中心性指標時,考慮實驗網絡規模,令局部性約束k=5。圖2展現了基于隨機性攻擊、度中心性優先攻擊、介數中心性優先攻擊以及介-度中心性優先攻擊4種攻擊策略時網絡受損情況對比,并以網絡最大連通子圖的規模為衡量標準。
從圖2(a)中可以看出,在隨機攻擊模式下,無標度網絡中的最大連通子圖中節點的數量隨著節點的不斷移除以線性的方式逐漸遞減,直到移除節點的個數接近節點總數時才降為0;在蓄意攻擊模式下,基于度中心性的攻擊策略在移除大約50個節點時,最大連通子圖中節點的數量接近于0,此時網絡中只存在孤立節點;基于介數中心性的攻擊策略與基于本文介-度中心性的攻擊策略在移除大約40個節點時,最大連通子圖中節點的數量即趨向于0。但從兩個攻擊策略的對比曲線可以看出,基于本文介-度中心性的攻擊策略下降得略快。圖2(b)所示對比情況與圖2(a)類似,隨機攻擊的效果較差,而在蓄意攻擊模式下基于介-度中心性的策略效果最佳。由此可以得到結論,基于本文介-度中心性的攻擊策略要優于基于度中心性和基于介數中心性的攻擊策略,對網絡的破壞性更強。
節點之間的最短路徑為從起始節點到目標節點經過連邊最少的一條路徑,也稱為測地線。網絡中所有節點之間最短距離的均值表明了節點的分散情況,稱為平均測地線距離,記作L,其計算方法如式(5)所示,其中dij表示節點之間的最短距離。

當網絡不斷遭受選擇性攻擊時,整個網絡被逐步拆分為多個子網絡,導致平均路徑長度不斷擴大。這時可以使用反測地線距離L-1描述網絡的平均最短路徑,當L-1變為0時,則表明節點對之間不再存在相連路徑,此時網絡中的節點全部成為孤立節點,其計算方法如式(6)所示,其中若節點i和節點j之間不存在通路時1/dij=0。


圖2 最大連通度指標下4種攻擊策略對比圖
分別生成節點數量均為5 000的無標度網絡和小世界網絡,圖3展現了基于度中心性優先攻擊、基于介數中心性優先攻擊以及基于介-度中心性優先攻擊三種攻擊策略時網絡受損情況對比,并以網絡平均反測地線距離為衡量標準。由于實驗網絡規模較大,隨機攻擊效果極差,不必與其進行對比,并令局部性約束k=6。
由圖3(a)中可知,平均反測地線距離的變化速率隨著節點的失效逐漸放緩,在基于度中心性的攻擊策略中,網絡的平均反測地線距離在移除大約整個網絡中25%的節點時變為0;在基于介數中心性的攻擊策略和基于本文介-度中心性的攻擊策略中,網絡的平均反測地線距離在移除整個網絡中20%的節點時開始趨向于0,但采用本文介-度中心性策略進行攻擊的曲線比采用介數中心性策略進行攻擊的曲線下降得略快,即網絡中節點全部成為孤立節點的速度略快于采用基于介數中心性的攻擊策略。由此可知,在無標度網絡中,基于介-度中心性的攻擊策略對網絡的破壞能力高于基于度中心性及基于介數中心性的攻擊策略。
由圖3(b)可知,小世界網絡中的平均反測地線距離變化速率雖然也隨著節點的失效逐漸放緩,但其放緩速率要比在無標度網絡中慢得多。采用基于度中心性的攻擊策略時,平均反測地線距離在移除整個網絡中大約60%的節點時變為0;采用基于介-度中心性的策略攻擊時,平均反測地線距離在移除整個網絡中大約50%的節點時就開始趨近0;而采用基于介數中心性攻擊策略進行攻擊的曲線圖形介于基于度中心性攻擊策略和基于介-度中心性攻擊策略之間,靠近于基于本文提出的介-度中心性策略進行攻擊的曲線。總體看來,對網絡進行蓄意攻擊時,與采用基于度中心性和采用基于介數中心性的攻擊策略相比,采用本文提出的基于介-度中心性的攻擊策略在去除更少的節點時就使得網絡的平均反測地線距離趨向于0或成為0,表明其更容易對網絡造成損害,攻擊效果更明顯。
構造不同規模以及不同連接概率的模擬網絡對節點抗毀性測度及網絡介-度熵度量進行分析,根據構造時選取的隨機重連概率p不同,構造出的網絡模型也將發生相應的變化。當p為0時,構造出的網絡為規則網絡;隨著p值的不斷增大,網絡向小世界網絡演化,當p增大至1時,構造出的網絡即為隨機網絡。
將網絡中節點總數分別設為30與5 000,節點平均度為6,對p分別取值為0.1、0.5和0.9,構造出的3種仿真網絡中的節點的度分布情況如圖4所示。
分別針對節點個數為30(局部性約束k=4)和節點個數為5 000(局部性約束k=6)2種情況,計算對3類網絡進行選擇性攻擊時網絡中的節點抗毀性和介-度熵,計算結果如表2所示。

圖3 平均反測地線距離指標下3種攻擊策略對比圖

圖4 仿真網絡節點度分布圖

表2 仿真網絡節點抗毀性及介-度熵計算結果
由圖4(a)和圖4(b)可以看出,生成網絡的節點度值的隨機性與生成網絡的隨機重連概率p正相關,p值越大,節點度分布的差異性就越大。由于規則網絡中節點度分布最均勻,因此對其進行選擇性攻擊時單個節點的毀壞對網絡的影響最小,抵抗破壞能力最強。而隨機網絡中節點度分布最不均勻,重要性較為突出個別核心節點一旦被毀壞將對網絡造成較大的影響,因此隨機網絡對選擇性攻擊的抵抗能力最弱。
由表2的對比結果可以看出,對3種網絡進行選擇性攻擊時,其節點平均抗毀性關系:規則網絡>小世界網絡>隨機網絡,體現了網絡面對選擇性打擊時抗毀性能的強弱排序,而介-度熵度量得到了相同的對比結果。該對比排序結果符合圖4(a)和圖4(b)的對比分析,因此說明介-度熵度量是完全合理的。
首先對仿真生成網絡進行仿真攻擊實驗。通過分別對比3種不同攻擊策略下的實驗結果,可以看出在對網絡進行選擇性攻擊時,基于本文介-度中心性的攻擊策略大幅優于基于度中心性的攻擊策略,且相對于基于介數中心性的攻擊策略也具有一定優勢。對大規模復雜網絡求取介數中心性時通常效率較低,而介-度中心性可以通過限制最長距離約束來進行近似計算,提高了計算效率,更適合大規模網絡中的抗毀性分析。然后對規則網絡、小世界網絡以及隨機網絡進行抗毀性評估計算,結果表明本文提出的介-度熵度量能夠準確評估大規模復雜網絡的網絡抗毀性。
本文結合節點度值與節點介數,并通過限制最長距離約束考察其局部作用,提出了用于度量網絡中節點重要程度的局部介-度中心性指標。在此基礎上提出了度量網絡中單個節點對整體抗毀性影響能力大小的節點抗毀性指標。進而提出介-度熵度量,評估網絡抗毀性能的強弱,并給出了該度量的計算方法。仿真實驗結果表明,與傳統的攻擊策略相比較,本文提出的介-度中心性的攻擊策略具有明顯優勢,對網絡造成的破壞性更強,說明介-度中心性指標在衡量節點重要性方面具有明顯優勢。對規則網絡、小世界網絡以及隨機網絡進行抗毀性評估計算的結果表明,介-度熵度量是評估大規模復雜網絡抗毀性的合理度量。
本文主要基于無權網絡進行抗毀性研究,而在現實網絡中,連邊通常存在多種權重,需要綜合考慮權重因素,以便獲得更準確的網絡抗毀性度量結果。在未來的工作中需要依據實際應用環境,綜合考慮各方面因素改進介-度中心性指標與介-度熵度量,使其具有更好的評估效果。