目的邊攻擊和防御下的相互依存網絡相繼故障

李穩國，崔憲普，鄧曙光，肖衛初

LI Wen-guo,CUI Xian-pu ,DENG Shu-guang, XIAO Wei-chu

湖南城市學院 通信與電子工程學院，湖南 益陽 413000

Department of Communication and Electronic Engineering, Hunan City University, Yiyang 413000, China

1 引言

過去十年，復雜網絡的大部分研究集中于單一網絡的結構及功能分析；然現實的網絡和系統都不是孤立的，它們通過彼此間相互作用組成大型復雜的相互依存網絡或系統[1]。由于不同網絡節點間相互依存的關系，這些由不同的網絡構成的相互依存復雜網絡存在巨大的脆弱性；一個或幾個網絡的部分節點或網絡間的相互依存邊失效，會導致與之依存的其他網絡節點或邊失效，繼而引發網絡間的故障相繼，最終導致這些相互依存網絡整體失效[2]。

相互依存網絡的相繼故障的相關研究始于《Nature》的文獻[3]，該研究分析基于節點的隨機攻擊導致的網絡間相繼故障，為后來相關研究提供了基本的理論框架。此后，相互依存網絡的故障滲流及魯棒性問題逐漸成為了研究熱點[1-10]。文獻[4]研究了目的攻擊節點造成的相互依存網絡故障滲流；文獻[5]研究了相互依存網絡間節點同度相連情況下，網絡故障滲流問題；及節點攻擊下的相互依存網絡的相變[6]、故障滲流[7-10]。然現實情況中，相互依存網絡的故障起因和發展并不僅局限于節點的隨機攻擊及目的攻擊，節點因地域范圍小易受到保護。網絡間的相互依存邊，因地域范圍跨度廣更易受到攻擊，然這方面的研究甚少。

本文主要研究相互依存網絡在其相互依存邊受到目的攻擊時的相繼故障。提出針對相互依存邊的目的攻擊和防御策略，構建相互依存網絡的故障滲流模型及算法，分析相互依存邊受到目的攻擊和防御時相互依存網絡的相繼故障滲流和魯棒性，并分別以相互依存的隨機（Erdos Renyi ER）網絡和無標度（Scale-Free SF）網絡為實例進行驗證。

2 相互依存邊的目的攻擊和防御策略

參照文獻[3,4]，本文中的相互依存網絡也由兩個單獨網絡(A、B網絡)通過彼此結點連接組成。假設A網絡中節點i與B網絡中節點j存在一相互依存邊，則此相互依存邊的邊權定義如下：

其中Aiv∈，Bjv∈；ki為A網絡節點i的度，kj為B網絡節點j的度；α為攻擊指數(-∞＜α＜+∞)。

假設A、B網絡間共有N條相互依存邊，設每次只攻擊其中的一條相互依存邊，則定義這條相互依存邊被攻擊的概率為：

聯合(1)式有：

假設攻擊 (1-p) (0＜p＜1)比例部分相互依存邊使其失效，首先可按照公式(3)式對每條沒失效的相互依存邊循環遍歷攻擊，直到其中的一條邊失效；接著采用同樣的方法使得第二條、第三條失效，以此類推直到N(1-p)邊失效為止。所以，當α＞0時，權重大的一些相互依存邊易受攻擊，稱為相互依存邊的目的攻擊；當α＜0時，權重大的一些相互依存邊得到保護而受攻擊的概率小，故稱目的防御；當α=0時，表示對相互依存邊的隨機攻擊，因相互依存邊兩端的結點是隨機選擇的，故這種情況與文獻[3, 4]對節點隨機攻擊等效。

3 故障滲流模型及算法描述

本文在文獻[3]基礎上，構建基于相互依存邊目的攻擊下的相互依存網絡相繼故障模型。為簡化而不失一般性，本模型中設定為兩個網絡即A、B網絡，這兩個網絡具有同樣的節點數N，A網絡的度分布為PA(k)，B網絡的度分布為 PB(k)，且一個網絡的節點只通過一條相互依存邊連接另一個網絡的節點，即一一對應。整個相繼故障模型如圖1所示，圖 1.(a)、1.(b)、1.(c)、1.(d)分布代表連鎖故障過程中的不同階段，其相應的算法如下：

（0）初始階段(圖1.(a))：按照公式(3)式，攻擊(1-p)比例部分相互依存邊使其失效（見 2部分），同時其兩端節點也失效。

（1）第一階段(圖 1.(b))：利用廣度優先算法（BSF）搜索A網絡中的最大連通子圖并判斷該最大連通子圖是否屬于極大簇：是，則不屬于最大連通子圖（極大簇）的節點失效，轉第二階段；否，則意味著整個相互依存網絡失效，轉結束。

（2）第二階段(圖1.(c))：由于相互依存的關系，B網絡中與A網絡失效節點相連的節點相繼失效。同理，對B網絡運用第一階段方法。

（3）第三階段(圖1.(d))：不斷重復第一、二階段，直到A、B網絡不再有新的碎片簇出現，整個網絡穩定轉結束。

圖1 相互依存網絡相繼故障模型

按照上述模型與算法，相互依存網絡故障滲流最終出現兩個中之一的結果：相互依存網絡整體失效，或整個相互依存網絡不再發生故障滲流而穩定。相互依存網絡的魯棒性可以用pc和p∞兩個參數來衡量[3]：滲流閾值pc是指相互依存網絡整體失效和不失效臨界狀態時p的臨界值；p∞是指整個相互依存相繼故障不再發生穩定時，剩余有效的相互依存邊p的最終值（剩余相互依存網絡的相互依存邊占總相互依存邊的比例，也可指A或B剩余網絡中節點數占總節點的比例）。pc越小（（1-pc）越大）表示需攻擊大比例的相互依存邊才能破壞整個網絡系統，即意味整個相互依存網絡的魯棒性越強。在攻擊相同比例的相互依存邊p條件下，p∞越大表示整個相互依存網絡不再發生故障滲流而穩定時剩下的相互依存網絡規模越大，意味著相互依存網絡魯棒性越強。

4 障滲流過程的理論分析

近年來，度分布的生成函數與滲流理論，成為相互依存網絡連鎖故障的一種很有效的方法與工具[3-11]，下面運用生成函數和滲流理論分析相互依存網絡的相繼故障及魯棒性，基本思路是：先把對相互依存邊的目的攻擊問題轉化為對網絡節點的隨機攻擊問題，然后運用文獻[3]的理論求解。

設A網絡中節點i與B網絡中節點j之間存在相互依存邊L1，L1依據公式(3)的概率受到目的攻擊等價于 A網絡中節點 i 依據公式(3)的概率受到目的攻擊。本模型的等價的節點目的攻擊與文獻[4]對節點的目的攻擊不同之處在于；文獻[4]對節點的目的攻擊只包含一個網絡的局部信息，而本模型的等價的節點目的攻擊包含的全局信息。對于整個網絡而言，算法初始階段按照等式(3)移去(1-p)部分的相互依存邊等價于在 A網絡中按等式(3)移去(1-p)部分節點。保留被移去節點的所有邊時，A網絡中剩余的p部分節點的度分布為[12-14]：

其中Ap(k) 為度為k的的節點數，當N→∞時，對等式(4)求導，

Pp(k)這個度分布的生成函數為：

把對節點的目的攻擊轉化為對節點隨機攻擊問題，則有：

對等式(10)進行微分，可以得到最終整個網絡系統失效的臨界條件為：

與文獻[3,4,5]一樣，等式(11)對于 pc和 xc不能得到精確的數學表達式，只可數值求解，因此以下部分的理論解均指其數值解。

5 仿真實驗

依據相互依存網絡相繼故障模型，以實際最常見的ER和SF分別構成的兩個相互依存網絡作為實例作進一步分析，理論分析中的ER和SF網絡[15]，其初始的度分布及相應的生成函數的表達式見文獻[3,4,11,12]；仿真實驗中，ER、SF網絡的節點個數均為N=104，SF網絡均有冪律指數r=3。以下非特別說明，標志點均為仿真值，在圖2和圖3中，SF網絡和ER網絡均有平均度＜k＞=4。。

首先分析攻擊指數α對相互依存網絡相繼故障的影響。圖2為不同攻擊指數下，p∞與p之間關系，從圖2可以得知，無論是相互依存的SF網絡還是ER網絡，攻擊指數越大網絡表現出的魯棒性越差。同等條件下，相互依存的SF網絡和ER網絡比較，SF網絡的在攻擊指數 α＞0時更脆弱，而攻擊指數α＜0時魯棒性更好。為對比分析基于相互依存邊的目的攻擊和基于節點的目的攻擊[4]，本文設計了關于攻擊指數的第二個實驗，（見圖 3），無論是相互依存的SF網絡還是ER網絡，基于相互依存邊的目的攻擊(α＞0)效果好于節點的目的攻擊（相應的 pc稍大），且相互依存邊的目的防御(α＜0)效果也較好（相應的 pc稍小）。故從攻擊指數分析可得：在攻防兩端，基于相互依存邊的目的攻防效果均好于基于節點的攻防效果。

圖2 不同攻擊指數下， p∞與p之間關系，其中(a) SF網絡，(b)ER網絡，實線為相應的理論值。

圖3 目的相互依存邊的攻擊與目的節點的攻擊，不同攻擊指數下的臨界值pc比較。

網絡的平均度是網絡中所有節點的連接邊數的平均，反映一個網絡的連接密度，接下來分析相互依存網絡的平均度對相繼故障的影響。圖4為基于相互依存邊目的的攻擊與基于目的節點的攻擊，在不同平均度參數下的臨界閾值pc的比較，其中B、D、F、H代表基于節點目的攻擊的臨界閾值pc，C、E、G、I代表基于相互依存邊目的攻擊的臨界閾值pc。圖5為相互依存邊目的攻擊下不同平均度時，p∞與p之間關系，其中(a) SF網絡，(b) ER網絡。從圖4可知：相互依存的SF網絡和ER網絡，基于相互依存邊的目的攻防效果均好于基于節點的目的攻防效果（α＜0時，相應的pc稍大；α＜0相應的pc稍小）。從圖 5可得：平均度越大，相互依存網絡的魯棒性越強。

圖4 目的相互依存邊的攻擊與目的節點的攻擊，不同平均度下的臨界值pc比較，其中實線ER網絡隨機攻擊的理論值。

圖5 不同平均度下，p∞與p之間關系，其中(a) SF網絡，(b) ER網絡，實線為相應的理論值。

接下來對上述結論作進一步的討論。相互依存邊的目的攻擊(α＞0)和目的防御(α＜0)效果均好于節點的目的攻擊和防御[4]是因為本文采用了全局最優策略（見（3）式）；而節點的目的攻擊和防御針對的是相互依存網絡中某一個網絡的節點，采用的是局部最優策略（見文獻[4]）。都是基于相互依存邊的攻防且相同條件下的相互依存的SF和ER網絡對比， SF網絡的攻防效果好于ER網絡；SF網絡在演化過程中的擇優原則導致出現的少數的核心節點（較小的節點集中了網絡大部分的邊），是出現這一結果的原因。

6 結論

本文提出了針對相互依存邊的目的攻擊和防御的全局最優的策略，并以相互依存的 SF網絡和相互依存的ER網絡為例，分析了在此策略下的相互依存網絡的相繼故障。理論分析和仿真結果表明，相比于節點的目的攻擊和防御，相互依存邊的目的攻擊和防御下的相互依存網絡的攻擊和防御效果均較優，并對這些結論進行了合理的分析和解釋。這一結論將為設計魯棒性強的相互依存網絡提供理論基礎，相互依存網絡的拓撲結構對相互依存網絡的魯棒性影響，將是下一步工作的重點。

[1]Yanqing H, Baruch K, Reuven C,et al. Percolation in interdependent and interconnected networks: Abrupt change from second- to first-order transitions[J]. Phys. Rev. E.2011(6) 84: 066116-1-6.

[2]Parshani R, Buldyrev S V, Havlin S. Interdependent networks: reducing the coupling strength leads to change from a first to second order percalation transition[J]. Phys. Rev.Lett. 2010, 4(105) : 048701-1-4.

[3]Buldyrev S V, Parshani R, Paul G, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature(London), 2010, 464 (7291): 1025-1028.

[4]Huang X, Gao J, Buldyrev S V, et al. Robustness of interdependent networks under targeted attack[J]. Phys. Rev. E,2011,6(83): 065101-1-4.

[5]Buldyrev S V, Nathaniel S, Gabriel A C. Interdependent networks with identical degrees of mutually dependent nodes[J]. Phys. Rev. E, 2011, 1(83): 016112-1-8.

[6]Parshani R, Buldyrev S V, Havlin S. Interdependent networks: reducing the coupling strength leads to change from a first to second order percolation transition[J]. Phys. Rev.Lett, 2010, 4(105): 048701-1-4.

[7]Dong G, Gao J, Tian L. Percolation of partially interdependent networks under targeted attack[J]. Phys. Rev. E,2012,1(85): 016112-1-7.

[8]Baxter G J, Dorogovtsev S N, Goltsev A V, et al. Avalanche collapse of interdependent networks[J]. Phys. Rev. Lett,2012, 24(109): 248701-1-5

[9]Morris R G, Barthelemy M. Transport on coupled spatial networks[J]. Phys. Rev. Lett., 2012, 12(109: 128703-1-4.

[10]Li W, Bashan A, Buldyrev S V , et al. Cascading failures in interdependent lattice networks: the critical role of the length of dependency links[J]. Phys. Rev. Lett. 2012,22(108): 228702-1-5

[11]Newman M E J. Spread of epidemic disease on networks[J]. Phys. Rev. E, 2002, 1(66): 016128-1-11

[12]Shao J, Buldyrev S V , Cohen B,et al. Fractal boundaries of complex networks[J]. Europhys. Lett. 2008,4(84):04-06.

[13]Shao J, Buldyrev S V, Braunstein L A, Havlin S, et al.Structure of shells in complex networks[J]. Phys. Rev. E,2009, 3(80): 0369105-1-13.

[14]王艷, 李應興, 勒二輝. 復雜網絡健壯性社團挖掘算法[J]. 計算機工程與應用, 2012, 48(31): 36-39.

[15]Dorogovtsev S N, Mends J F F, Samukhin A N. Structure of growth networks with preferential linking [J]. Phy. Rev.Lett. 2000, 5(85), 4633-1-4.