目的邊攻擊和防御下的相互依存網(wǎng)絡(luò)相繼故障

李穩(wěn)國，崔憲普，鄧曙光，肖衛(wèi)初

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

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

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

1 引言

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

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

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

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

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

其中Aiv∈，Bjv∈；ki為A網(wǎng)絡(luò)節(jié)點i的度，kj為B網(wǎng)絡(luò)節(jié)點j的度；α為攻擊指數(shù)(-∞＜α＜+∞)。

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

聯(lián)合(1)式有：

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

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

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

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

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

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

（3）第三階段(圖1.(d))：不斷重復(fù)第一、二階段，直到A、B網(wǎng)絡(luò)不再有新的碎片簇出現(xiàn)，整個網(wǎng)絡(luò)穩(wěn)定轉(zhuǎn)結(jié)束。

圖1 相互依存網(wǎng)絡(luò)相繼故障模型

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

4 障滲流過程的理論分析

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

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

其中Ap(k) 為度為k的的節(jié)點數(shù)，當(dāng)N→∞時，對等式(4)求導(dǎo)，

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

把對節(jié)點的目的攻擊轉(zhuǎn)化為對節(jié)點隨機攻擊問題，則有：

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

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

5 仿真實驗

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

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

圖2 不同攻擊指數(shù)下， p∞與p之間關(guān)系，其中(a) SF網(wǎng)絡(luò)，(b)ER網(wǎng)絡(luò)，實線為相應(yīng)的理論值。

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

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

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

圖5 不同平均度下，p∞與p之間關(guān)系，其中(a) SF網(wǎng)絡(luò)，(b) ER網(wǎng)絡(luò)，實線為相應(yīng)的理論值。

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

6 結(jié)論

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

[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]王艷, 李應(yīng)興, 勒二輝. 復(fù)雜網(wǎng)絡(luò)健壯性社團挖掘算法[J]. 計算機工程與應(yīng)用, 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.