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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 障滲流過(guò)程的理論分析

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

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

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

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

把對(duì)節(jié)點(diǎn)的目的攻擊轉(zhuǎn)化為對(duì)節(jié)點(diǎn)隨機(jī)攻擊問(wèn)題，則有：

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

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

5 仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

6 結(jié)論

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

[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ò)健壯性社團(tuán)挖掘算法[J]. 計(jì)算機(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.