加權無標度網絡級聯抗毀性研究

王甲生，吳曉平，陳永強

（海軍工程大學信息安全系，武漢 430033）

加權無標度網絡級聯抗毀性研究

王甲生，吳曉平，陳永強

（海軍工程大學信息安全系，武漢 430033）

通過引入一種改進的非線性負載容量模型，對加權無標度網絡的級聯抗毀性進行了深入研究。采用標準化崩塌規模為度量指標，在局部加權負載重分配準則下，對權重系數、容量參數以及網絡密度等參量對網絡級聯抗毀性的影響進行了數值仿真模擬。結果表明，網絡的級聯抗毀性隨著權重系數θ的增大而降低，在θ≤0.3時網絡具有較強的抗毀性，這與線性模型中的結論是截然不同的；網絡的級聯抗毀性隨著容量參數的增大而增強，且在權重系數確定的情況下，存在最優參數組合使得網絡具有最強的級聯抗毀性。最后，對成本和性能約束下加權無標度網絡的級聯抗毀性進行了定量分析。

加權無標度網絡；抗毀性；級聯失效；負載容量模型；權重系數

0 引言

復雜網絡作為復雜性科學的一個重要研究領域，近年來受到數學、物理學、生物學、社會學、信息科學以及軍事和經濟等各學科領域研究人員的廣泛關注［1］。隨著復雜網絡研究的興起，其抗毀性研究也備受關注，特別是一些現代社會賴以生存的重要基礎設施網絡，如電力網絡、金融網絡、交通網絡等，其抗毀性研究顯得尤為迫切。復雜網絡的級聯抗毀性是復雜網絡抗毀性研究的一個重要方面，是指當網絡中節點發生故障或被攻擊時，在節點容量有限的情況下，網絡上的負載進行重新分配使得相關節點上的負載超過其容量而失效的動態過程，可能導致部分網絡故障甚至整個網絡的崩潰［2］。在現實世界中很多網絡災難都可以歸結為這類級聯崩潰問題，比如2012年7月發生的印度大停電事故，同樣的問題也存在于通信網、交通網、因特網等網絡系統之中。

復雜網絡上的級聯抗毀性研究近年來得到了很大關注。Motter等［2］首次研究了不同類型網絡中的級聯失效，通過引入一個負載容量線性模型，發現異構網絡中級聯失效對選擇性攻擊具有敏感性。Crucitti等［3］提出了一種節點和邊的混合動態相繼故障模型，并采用級聯失效后網絡的平均加權效率度量級聯失效的后果。Schafer等［4］提出了一種增加網絡級聯失效抗毀性的設計方法，并通過減少網絡總負載來提高網絡抗毀性。Wang W X等［5］研究了加權復雜網絡對級聯失效的魯棒性與權重分布的關系，結果表明存在最優權重分布使網絡具有最強的魯棒性。Mirzasoleiman B［6］等研究了加權網絡對于級聯失效的魯棒性，并在電力網、AS級Internet網絡、鐵路網以及航空網上進行了驗證，結果表明賦權模型為端節點介數乘積的網絡具有最強的魯棒性。LI S D［7］等研究了無標度網絡、WS小世界網絡和ER隨機網絡由最大負載攻擊（HL）和隨機攻擊（RA）引起的網絡的級聯失效問題。Babaei M等［8］研究了模塊化小世界網絡對于級聯失效的魯棒性，研究表明模塊內部連接對于網絡魯棒性具有重要作用，且模塊化程度越高的網絡其魯棒性越差。DOU B L［9］等提出了一種非線性負載容量模型，并在BA無標度網絡、ER隨機網絡、AS級Internet網絡以及電力網上進行了仿真。朱濤等［10］研究了指揮控制級聯失效模型，并就不同條件下指揮控制的級聯失效特征變化情況進行了定量分析。李勇等［11］建立了度均勻隨機分布的網絡模型和負載局部擴展的級聯失效抗毀性模型，并運用多維分支過程方法求解網絡級聯失效的臨界值。任俊亮等［12］建立了一個無尺度網絡的相繼故障模型，該模型采用基于節點剩余容量的負載重分配策略能較充分地利用網絡資源。王威等［13］提出了基于隨機行走介數的級聯失效模型。

在實際網絡的級聯抗毀性研究中，一個關鍵的問題是合理設定節點和邊的容量，使之盡可能符合實際。另一方面，由于實際網絡的構建也是需要考慮成本的，因此也需要設計合理的負載容量模型以抵御級聯失效。文獻［14］研究了大規模基礎設施網絡的負載與容量之間的關系，發現負載與容量之間呈現出非線性關系，這一結論與以往研究中［2，5-8，10，12-13］假設的負載容量模型是截然不同的。因此，本文通過引入一種改進的非線性負載容量模型，在局部加權負載重分配準則下，采用數值仿真的方法研究了加權標度網絡權重系數、容量參數以及網絡密度等對網絡級聯抗毀性的影響，定量分析了成本和性能約束下的加權無標度網絡級聯抗毀性。

1 加權復雜網絡級聯失效分析

1.1 加權復雜網絡

加權復雜網絡已經成為復雜網絡的一個重要的研究方向，可以用圖G=（V，E）來表示，假設G是一個無向連通圖，有n個節點和m 條帶有權重的邊，節點集V= （v1，v2，…，vn），邊集E= （e1，e2，…，em）。一般用權重鄰接矩陣W= （wij）n×n表示加權網絡權重，wij表示節點vi與vj連接的邊的權重，當網絡中各條邊的權值都相同時，加權網絡即退化為無權網絡。

把一個實際系統抽象為加權網絡的過程并不是平庸的，以往的權重模型主要有YJBT模型、AK模型以及BBV模型等。本文考慮了一種將無權網絡的性質轉化為邊權的賦權模型，邊權與其兩個端節點的度相關［6，15］。邊權的賦予方式為：假設網絡中邊eij連接的兩個節點vi與vj的度值分別為ki和kj，那么該邊的權重為wij=wji= （kikj）θ，其中θ（θ＞0）為一個可調的權重系數，用于描述邊權與節點度之間的相互關系。這種邊權的賦予方式是有實證數據作支撐的，在目前加權網絡的研究中得到了廣泛的應用。權重系數θ決定了加權復雜網絡邊的非同質性，當θ=0時，對應的邊權w=1，表明邊權與節點度之間沒有關聯，加權網絡退化為無權網絡；當θ＞0時，加權網絡的特性由權重來刻畫，且θ越大則各邊之間的差異越大。

1.2 級聯失效

假設加權復雜網絡的級聯失效是由一個微小的初始攻擊觸發的，比如切除網絡中的任意一條邊。那么，在局部加權的負載重分配準則［5-6］下，這條斷邊上的負載將分配給其端節點相連的鄰邊，且鄰邊接收到的負載正比于邊的權重。與以往的模型一樣，加權網絡中每條邊所能處理的最大負載稱為該邊的容量，一般來說邊的容量是有限的。

負載的重分配和有限容量使得一個節點的失效足以導致整個網絡的崩潰。在初始狀態下，加權網絡處于一個穩定的狀態，每條邊上的負載均小于其容量。任意一條邊的移除將改變之前的平衡狀態，由此引發的負載重分配可能導致其它相連邊的失效，這些邊的失效又可能導致相連邊的失效，直到網絡中每條邊的負載都不超過其容量為止。

P.Holme等［16］的研究指出，復雜網絡中邊的介數與該邊的端節點的度的乘積形式是正相關的。因此，可以合理地設定在邊eij移除之前，如果其沒有接收到額外的負載Δwij，那么該邊上的負載就等于該邊的權重wij。

2 改進的負載容量非線性模型

在實際網絡中，邊的容量是受成本和可用資源約束的。因此，在以往的研究工作中，復雜網絡中邊的容量被設定為正比于其權重，比如C=Tw，其中常數T（T＞1）為臨界系數，w為邊的權重；或者C= （1+a）L，其中常數a為容忍系數，L為邊的初始負載。然而，D H Kim等通過對航空運輸網絡、公路交通網絡、電力網絡及路由器網絡的實證研究發現，實際網絡中容量較小的節點（邊）反而有較大的未使用容量，即負載與容量之間呈現出非線性關系，表明以上假設的負載容量線性模型與現實是不相符的。

據此，本文給出了一個改進的負載容量非線性模型，將加權網絡中邊的容量表示為C=L+βLα，其中α（α＞0）和β（β＞0）為容量參數。該模型包含兩個可變參數，靈活性更高，且當α=1時模型即退化為線性模型。圖1給出了改進負載容量模型與線性模型C= （1+a）L在對數坐標系中的比較，圖中灰色實線表示改進的負載容量模型，虛線表示線性模型，黑色實線為容量等于負載的參考線。

由圖1可以看出，以往的線性模型中容量是正比于負載的，改進的負載容量模型在負載較小時空閑容量較大，負載較大時空閑容量反而較小，與文獻［14］中對實際網絡的研究結論一致。

另外，在級聯失效發生后，本文采用崩塌規模Sij來表示切斷邊eij觸發的級聯失效對網絡造成的破壞程度，崩塌規模Sij即網絡中失效邊的數量。為了衡量整個網絡的級聯抗毀性，對崩潰規模進行標準化，采用標準化崩塌規模SN來表示依次切斷每條邊后對網絡造成的平均破壞程度。S=∑ijSij/N，其中N為網絡中邊的數量。標準化崩潰規模SN可以看作是復雜網絡面對隨機失效的級聯抗毀性的平均度量。

圖1 線性與非線性負載容量模型Fig.1 The linear and nonlinear load-capacity model

3 加權無標度網絡級聯抗毀性仿真分析

現實生活中的許多網絡如因特網、航空運輸網、電力網等都具有明顯的無標度特性。為了更好地理解實際網絡特征參數與級聯抗毀性之間的關系，本文研究了加權無標度網絡的抗毀性。首先，構建加權無標度網絡，其初始節點數n0=5，m=4，節點總數N=5 000，網絡的構建依賴于擇優吸附機制。然后，依據1.1節中的賦權方式對BA網絡進行賦權，其中權重系數θ在［0，2］之間取值。當θ=0.5時，加權無標度網絡的負載分布如圖2所示，呈現出冪律分布的特性。

加權無標度網絡的級聯抗毀性與權重系數θ、容量參數α和β等是密切相關的，其級聯抗毀性分析較為復雜。本節分別研究加權無標度網絡級聯抗毀性與權重系數、容量參數以及網絡密度等網絡參數的關系，并定量分析了成本和性能約束下的級聯抗毀性。

3.1 容量參數固定的抗毀性仿真

加權無標度網絡中邊的容量由α和β兩個參數共同決定的，在對實際網絡進行研究的基礎上，獲得容量參數的近似值。設定α=0.45，β=0.20，加權無標度網絡級聯抗毀性與權重系數θ的關系如圖2所示，仿真結果為10次計算的平均值。

由圖3可知，在容量參數固定的情況下，標準化崩塌規模SN隨著權重系數θ的增大不斷增大，即網絡的抗毀性隨θ增大而不斷降低。當θ＜0.4時，SN接近于0，網絡表現出最強的抗毀性。然而當θ≥0.4時，SN迅速增大，且當θ＞0.8時，網絡幾乎全盤崩潰。這一結果與對文獻［5］的進一步的研究結論完全不同。Wang W X等采用線性負載容量模型，其研究工作側重于控制級聯失效的開始及傳播，對于控制任意結構加權無標度網絡級聯失效的發生及失效范圍具有重要指導意義。然而，進一步的研究表明，隨著級聯失效范圍的擴大，標準化崩塌規模SN與閾值T的關系是單調的。在線性負載容量模型中，網絡抗毀性與閾值T的關系如圖4所示，仿真結果為10次計算的平均值。

圖2 加權無標度網絡的負載分布曲線Fig.2 Load distribution of weighted scale-free networks

圖3 網絡抗毀性與權重系數的關系曲線Fig.3 Invulnerability as a function of weight coefficient

圖4 線性模型中抗毀性與閾值T的關系曲線Fig.4 Relationship between invulnerability and the threshold T

由圖4可以看出，在線性負載容量模型中，隨著級聯失效規模的擴大，對于確定的閾值T0，權重系數θ越大，標準化崩塌規模SN就越小，加權無標度網絡的級聯抗毀性越強。這與本文上述得出的結論是截然不同的，這種差異正是由于負載容量之間的非線性關系造成的。

3.2 不同容量參數的抗毀性仿真

D H Kim等對實際網絡的實證研究也發現，不同復雜網絡中負載容量的關系曲線是不同的。為此，本文研究了不同容量參數下加權無標度網絡的級聯抗毀性。圖5和圖6分別為加權無標度網絡級聯抗毀性與容量參數α和β的關系曲線，仿真結果為10次計算的平均值。

圖5 網絡抗毀性隨容量參數α的變化曲線Fig.5 Invulnerability as a function of parameterα

圖6 網絡抗毀性隨容量參數β的變化曲線Fig.6 Invulnerability as a function of parameterβ

在圖5中，參數β=0.20。由圖5a可知，對于給定的α值，隨著θ的不斷增大，SN不斷增大，網絡的級聯抗毀性不斷降低。對于給定的θ值，隨著α的不斷增大，網絡的級聯抗毀性不斷增強，θ=0.5時的情況如圖5b所示。在圖6中，參數α=0.45。參數β對網絡級聯抗毀性的影響與α類似。對于給定β值，隨著θ的不斷增大，網絡的級聯抗毀性不斷降低。對于給定的θ值，隨著β的不斷增大，網絡的級聯抗毀性不斷增強，如圖6b所示。隨著參數α和β的不斷增大，網絡的級聯抗毀性不斷增強，這與直觀上的認識是一致的。

從圖5和圖6也可以看出，不同容量參數的網絡在θ較小（θ≤0.3）時，表現出較強的抗毀性，隨著θ的進一步增大，網絡抗毀性急劇降低。另外，隨著α和β的增大，網絡抵抗級聯失效的空閑容量ΔC=βLα也不斷增大，網絡成本也進一步增加。因此，從控制成本的角度考慮，可以減小網絡的權重系數，隨后根據實際需要對容量參數進行調節，使網絡的級聯抗毀性最強。

3.3 不同網絡密度對抗毀性的影響

網絡密度對加權網絡的級聯抗毀性也存在一定影響。網絡密度表現為平均度〈k〉，網絡密度與網絡級聯抗毀性的關系曲線如圖7所示，仿真結果為10次計算的平均值。

在圖7中，容量參數α=0.45，β=0.20。由圖7a可知，給定〈k〉的情況下，隨著權重系數θ的不斷增大，網絡的級聯抗毀性先降低，隨后又略有增強。對于給定的θ值，網絡的級聯抗毀性與〈k〉的關系如圖7b所示。由圖7b可知，在θ=0.5的情況下，網絡的級聯抗毀性在〈k〉=2時最強，在〈k〉=4時最差，隨著〈k〉的繼續增大有所增強。另外，由圖7a可以看出，不同密度的加權無標度網絡在θ＜0.3時級聯失效規模較小，而當θ≥0.3時級聯失效傳播的速度迅速加快。從控制級聯失效傳播范圍的角度考慮，可以采取的方法是首先減小權重系數，進而根據需要對網絡密度進行一定調整。

3.4 考慮成本與性能的抗毀性優化分析

在實際網絡的抗毀性研究中，通常人們比較關心的是如何在保持成本一定的情況下，設計抗毀性最優的網絡［17］。前面給出了加權無標度網絡級聯抗毀性與各參數的定性關系，下面從定量的角度給出加權無標度網絡抗毀性的優化分析模型。

加權無標度網絡的級聯抗毀性可以表示為網絡魯棒性與網絡成本的函數。

其中，F為加權無標度網絡級聯抗毀性目標函數。R為網絡魯棒性，用最大連通子圖的相對大小來表示，R=G′/G，G′和G分別表示級聯失效發生前后的最大連通子圖大小。S為成本，與網絡密度〈k〉和邊容量C相關，表示為S（〈k〉）和S（C）。S（〈k〉）=m/n0，m 為平均連接數，n0為無標度網絡的初始節點數。S（C）=∑ijΔC/ΣijL，L為初始負載，S（C）為網絡的相對增加成本。γ為加權系數，表示網絡邊容量決定的網絡成本的重要性，通過調節γ，可以均衡容量成本和密度成本對網絡抗毀性的影響。本文重點考慮容量成本對網絡級聯抗毀性的影響，取γ=1。成本和性能約束下，加權無標度網絡的級聯抗毀性與各參數的關系曲線如圖8所示。

圖7 不同網絡密度與級聯抗毀性的關系曲線Fig.7 Invulnerability as a function of parameter〈k〉

圖8 成本和性能約束下級聯抗毀性與α，β和θ的關系曲線Fig.8 Invulnerability as functions ofα，βandθconsidering cost and network performance

由圖8a可知，在確定容量參數α和β的情況下，網絡在θ∈［0.1 0.3］時具有較強的級聯抗毀性，且在θ=0.3時抗毀性最強，隨后又迅速降低，到θ≥0.7時網絡全盤崩潰。在圖8b和c可知，網絡的級聯抗毀性隨著α和β的逐漸增大呈現出先增強后減弱的趨勢，也就是說在確定權重系數θ的情況下，網絡存在最優級聯抗毀性，以θ=0.5為例，網絡在α=0.60，β=0.20時抗毀性最強。

由圖3～圖8的仿真結果可以得出如下結論，在非線性負載容量模型條件下：

1）加權無標度網絡的級聯抗毀性隨著權重系數θ的增大而降低，當θ≤0.3時網絡具有較強的抗毀性，當θ＞0.3時級聯抗毀性迅速降低，而當θ＞0.8時網絡接近全盤崩潰，這與文獻［5］中關于線性模型的結論是完全相反的。

2）加權無標度網絡的級聯抗毀性隨著容量參數α和β的增大而增強，這與直觀上的認識是一致的。然而，容量參數的增大也在一定程度上增加了網絡成本。從控制成本的角度考慮，首要是減小網絡的權重系數，隨后根據需要對容量參數進行調節，使得網絡的級聯抗毀性最強。

3）在成本和抗毀性約束下，加權無標度網絡的抗毀性在權重系數θ≤0.3時較強，且在權重系數θ確定的情況下，通過調節容量參數α和β，加權無標度網絡存在最優的級聯抗毀性。

由此可以看出，本文的研究成果能夠從整體上把握加權負載網絡的級聯抗毀性狀況，且能靈活調節參數以獲取最大的級聯抗毀性。

4 結論

本文通過引入改進的非線性負載容量線性模型，對加權無標度網絡的級聯抗毀性進行了深入研究。結果表明，加權無標度網絡的級聯抗毀性隨著權重系數的增大而降低，隨容量參數的增大而增強，且在權重參數固定的情況下存在最優參數組合使得網絡具有最強抗毀性。研究成果能夠為實際網絡的抗毀性優化設計提供一定的參考和借鑒。另外，本文的研究可以看作是加權無標度網絡面對隨機失效的級聯抗毀性，實際上網絡面臨的攻擊更多的是蓄意攻擊，因此加權無標度網絡面對基于高負載節點或蓄意攻擊的級聯抗毀性問題將是下一步研究重點。

［1］陳關榮，陳增強，呂金虎.復雜網絡科學與工程的研究進展［J］.系統工程學報，2010，25（6）：723-724.

Chen Guanrong，Chen Zengqiang，LüJinhu.Advances on complex networks science and engineering［J］.Journal of Systems Engineering，2010，25（6）：723-724.

［2］Motter A E，Lai Y C.Cascade-based attacks on complex networks［J］.Phys Rev E，2002，66（6）：065102.

［3］Crucitti P，Latora V，Marchiori M.Model for cascading failures in complex networks［J］.Phys Rev E，2004，69（4）：045104.

［4］Schafer M，Scholz J，Greiner M.Proactive robustness control of heterogeneously loaded networks［J］.Phys Rev Lett，2006，96（10）：108701.

［5］Wang W X，Chen G R.Universal robustness characteristic of weighted networks against cascading failure［J］.Phys Rev E，2008，77（2），026101.

［6］Mirzasoleiman B，Babaei M，Jalili M，et al.Cascaded failures in weighted networks［J］.Phys Rev E，2011，84（4）：046114.

［7］Li S D，Li L X，Yang Y X，et al.Revealing the process of edge-based-attack cascading failures［J］.Nonlinear Dyn.，2012，69（3）：837-845.

［8］Babaei M，Ghassemieh H，Jalili M.Cascading failure tolerance of modular small-world networks［J］.IEEE Transactions on Circuits and Systems-II：Express Briefs，2011，58（8）：527-531.

［9］Dou B L，Wang X G，Zhang S Y.Robustness of networks against cascading failures［J］.Physica A，2010，389（11）：2310-2317.

［10］朱濤，常國岑，張水平，等.基于復雜網絡的指揮控制級聯失效模型研究［J］.系統仿真學報，2010，22（8）：1817-1820.

Zhu Tao，Chang Guocen，Zhang Shuiping，et al.Reseatch on model of cascading failure in command and control based on complex networks［J］.Journal of System Simulation，2010，22（8）：1817-1820.

［11］李勇，吳俊，譚躍進.物流保障網絡級聯失效臨界抗毀性［J］.系統仿真學報，2012，24（5）：1030-1034.

Li Yong，Wu Jun，Tan Yuejin.Critical invulnerabiity study for cascading failure of tactical logistics networks［J］.Journal of System Simulation，2012，24（5）：1030-1034.

［12］任俊亮，申卯興，仝蕊，等.無尺度網絡中降低相繼故障規模的策略研究［J］.計算機工程與應用，2011，47（33）：82-84.

Ren Junliang，Shen Maoxing，Tong Rui，et al.Study of reducing size of cascading failures in scale-free network［J］.Computer Engineering and Applications，2011，47（33）：82-84.

［13］王威，狄鵬，胡斌.基于隨機行走介數的級聯失效模型［J］.系統工程與電子技術，2012，34（9）：1914-1917.

Wang Wei，Di Peng，Hu Bin.Cascading failure model based on random-walk betweenness［J］.Systems Engineering and Electronics，2012，34（9）：1914-1917.

［14］Kim D H，Motter A E.Resource allocation pattern in infrastructure networks［J］.J Phys A：Math Theor，2008，41（22）：224019.

［15］Zhang Y C，Zhou S，Zhang Z Z，et al.Traffic fluctuation on weighted networks［J］.IEEE Circuits and Systems，2012，12（1）：33-44.

［16］Holme P，Kim B J，Yoon C N，et al.Attack vulnerability of complex networks［J］.Phys Rev E，2002，65（5）：056109.

［17］Li P，Wang B H，Sun H，et al.A limited resource model of fault-tolerant capability against cascading failure of complex network［J］.Eur Phys J B，2008，62（1）：101-104.

Invulnerability of Weighted Scale-Free Networks Against Cascading Failure

WANG Jia-sheng，WU Xiao-ping，CHEN Yong-qiang
（Department of Information Security，Naval University of Engineering，Wuhan 430033，China）

To solve the problem of invulnerability analysis of weighted scale-free networks against cascading failure，an improved nonlinear load-capacity model is introduced.The normalized avalanche size is adopted as the measurement of invulnerability，and under the rule of local weighted load redistribution，the influence of weight coefficient，capacity parameters and density of the network on invulnerability of weighted scale-free networks against cascading failure is investigated by numerical simulation.The results demonstrate that the smaller of the weight coefficientθ，the better of the invulnerability，especially whenθ≤0.3，which contrasts with the conclusion drawn from the linear model.In addition，the larger of the capacity parameters，the better of the invulnerability.And moreover，when the weight coefficient is fixed，there exists an optimal combination of the capacity parameters which ensures that the weighted networks reach the strongest invulnerability level.Finally，the qualitative analysis of invulnerability of weighted scale-free networks against cascading failure under the restrictions of cost and performance is presented.

weighted scale-free networks；invulnerability；cascading failure；load-capacity model；weight coefficient

N949

A

1672-3813（2013）02-0013-07

2012-08-24

國家自然科學基金（71171198，61100042）；湖北省自然科學基金（2011CDB052）

王甲生（1984-），男，陜西渭南人，博士研究生，主要研究方向為復雜系統分析建模與仿真。

（責任編輯 李進）