基于代價的復(fù)雜網(wǎng)絡(luò)邊攻擊策略有效性分析

王爾申, 王玉偉, 曲萍萍, 藍(lán)曉宇, 陳佳美

(1. 沈陽航空航天大學(xué)電子信息工程學(xué)院, 遼寧 沈陽 110136; 2. 北京航空航天大學(xué)電子信息工程學(xué)院, 北京 100191)

0　引　言

現(xiàn)實(shí)生活中存在各種各樣的復(fù)雜網(wǎng)絡(luò),這些網(wǎng)絡(luò)由大量節(jié)點(diǎn)和邊組成且具有很高的復(fù)雜性。其中,節(jié)點(diǎn)代表組成該網(wǎng)絡(luò)中的個體,邊代表節(jié)點(diǎn)之間的相互聯(lián)系[1-3]。許多真實(shí)網(wǎng)絡(luò)都可以用加權(quán)網(wǎng)絡(luò)來描述[4-7],如道路交通網(wǎng)絡(luò)中邊的權(quán)重可以由兩地之間道路的長度或車輛通行所花費(fèi)的時間來表示。近年來,復(fù)雜網(wǎng)絡(luò)已經(jīng)得到了社會學(xué)[8]、數(shù)學(xué)[9]、生物學(xué)[10]、信息學(xué)[11]、軍事學(xué)[12]與經(jīng)濟(jì)學(xué)[13]等領(lǐng)域科研人員的廣泛關(guān)注。

網(wǎng)絡(luò)的魯棒性一直是復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域的重要研究方向[14-17]。在很多實(shí)際網(wǎng)絡(luò)中,一個或少數(shù)幾個節(jié)點(diǎn)(邊)發(fā)生故障后,通過節(jié)點(diǎn)之間的耦合關(guān)系可能導(dǎo)致整個網(wǎng)絡(luò)的崩潰,如2003年,美國俄亥俄州由于3條電線燒斷引發(fā)的北美大規(guī)模停電事故[18]。文獻(xiàn)[19]在復(fù)雜網(wǎng)絡(luò)魯棒性方面研究較早,該研究表明,具有無標(biāo)度特性的網(wǎng)絡(luò)在隨機(jī)攻擊下表現(xiàn)出較強(qiáng)的魯棒性,而在蓄意攻擊下非常脆弱。文獻(xiàn)[20]考慮到網(wǎng)絡(luò)初始狀態(tài)和發(fā)生故障后可以看作動力學(xué)平衡,提出了一個新的級聯(lián)失效模型,仿真結(jié)果表明,對于無標(biāo)度網(wǎng)絡(luò)來說,無論是高度節(jié)點(diǎn)還是部分低度節(jié)點(diǎn)吸收額外負(fù)載高于其自身能力,而小世界網(wǎng)絡(luò)沒有這種現(xiàn)象。文獻(xiàn)[21]對于復(fù)雜網(wǎng)絡(luò)邊襲擊策略進(jìn)行了研究,認(rèn)為襲擊網(wǎng)絡(luò)中負(fù)荷較小的邊更易導(dǎo)致相繼故障,但是,該研究并沒有考慮攻擊代價因素。文獻(xiàn)[22]對航空公司航線網(wǎng)絡(luò)的魯棒性進(jìn)行了研究,認(rèn)為低成本航空公司(low cost carriers,LCC)航線網(wǎng)絡(luò)比提供全方位服務(wù)的航空公司(full service carriers,FSC)航線網(wǎng)絡(luò)更具魯棒性。在文獻(xiàn)[23]中,作者研究了加權(quán)復(fù)雜網(wǎng)絡(luò)的動態(tài)魯棒性,認(rèn)為在異配網(wǎng)絡(luò)中,低度節(jié)點(diǎn)成為關(guān)鍵節(jié)點(diǎn)的現(xiàn)象只會出現(xiàn)在弱加權(quán)網(wǎng)絡(luò)和弱耦合網(wǎng)絡(luò)中,但是該研究只是對節(jié)點(diǎn)進(jìn)行了分析,并沒有對復(fù)雜網(wǎng)絡(luò)的邊進(jìn)行分析。文獻(xiàn)[24]以自然連通度為網(wǎng)絡(luò)抗毀性譜測度指標(biāo),通過混合擇優(yōu)模型構(gòu)造不同度分布的復(fù)雜網(wǎng)絡(luò),研究了度分布對網(wǎng)絡(luò)抗毀性的影響,研究表明在相同條件下,網(wǎng)絡(luò)度分布越不均勻,抗毀性越強(qiáng)。

然而,以往的研究大都考慮攻擊節(jié)點(diǎn),未考慮攻擊代價因素或直接假設(shè)攻擊代價相同[25-31]。實(shí)際上,對許多真實(shí)的網(wǎng)絡(luò)系統(tǒng)進(jìn)行攻擊所花的代價存在很大差異。文獻(xiàn)[32]研究了代價下節(jié)點(diǎn)攻擊策略的有效性,提出了介數(shù)緊致系數(shù)和接近度緊致系數(shù)兩個新的度量指標(biāo),仿真結(jié)果表明,針對同一網(wǎng)絡(luò)度攻擊策略最差;相同平均度下,介數(shù)緊致系數(shù)或接近度緊致系數(shù)越小,則與此接近的介數(shù)或接近度攻擊策略越有效,但是沒有研究代價下邊攻擊策略。文獻(xiàn)[33]研究了在復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)之間如何有效地分配有限的防御資源,以使得網(wǎng)絡(luò)在面對各種攻擊策略時所遭到的破壞程度降到最小,發(fā)現(xiàn)從基于代價的攻擊角度看,存在一個最優(yōu)的防御資源分配策略,可以使得網(wǎng)絡(luò)得到最大限度的保護(hù),最優(yōu)防御的配置問題取決于網(wǎng)絡(luò)參數(shù),網(wǎng)絡(luò)連接更稀疏可能更有益于網(wǎng)絡(luò)防御優(yōu)化。文獻(xiàn)[34]對于復(fù)雜網(wǎng)絡(luò)中的攻擊策略提出了一種代價約束模型,認(rèn)為節(jié)點(diǎn)度較低的節(jié)點(diǎn)在約束代價較高時會優(yōu)先被攻擊,而節(jié)點(diǎn)度較高的節(jié)點(diǎn)在約束代價較低時才會優(yōu)先被攻擊;除此之外,還發(fā)現(xiàn)存在代價敏感型參數(shù)閾值,如果攻擊單個節(jié)點(diǎn)的代價小于這個閾值,那么節(jié)點(diǎn)度高的節(jié)點(diǎn)不會被優(yōu)先攻擊。文獻(xiàn)[35]研究了復(fù)雜網(wǎng)絡(luò)在考慮代價情況下,攻擊節(jié)點(diǎn)時網(wǎng)絡(luò)的魯棒性,但并沒有涉及到考慮代價時攻擊邊的情況。

受之前研究內(nèi)容的啟發(fā),文中主要研究復(fù)雜網(wǎng)絡(luò)邊的攻擊,并且考慮邊的攻擊代價因素。假設(shè)攻擊代價與邊的權(quán)重呈正相關(guān)的關(guān)系,提出基于代價的復(fù)雜網(wǎng)絡(luò)邊攻擊模型,采用邊的3種攻擊策略對網(wǎng)絡(luò)進(jìn)行攻擊。研究在考慮攻擊代價時分別使用這3種策略攻擊邊對于普通無標(biāo)度網(wǎng)絡(luò)和指數(shù)可調(diào)無標(biāo)度網(wǎng)絡(luò)魯棒性的影響。

1　基于代價的復(fù)雜網(wǎng)絡(luò)邊攻擊模型

1.1　無標(biāo)度網(wǎng)絡(luò)

20世紀(jì)末,Barabasi-Albert(BA)無標(biāo)度網(wǎng)絡(luò)模型被提出,真實(shí)網(wǎng)絡(luò)的無標(biāo)度特性源于兩種生成機(jī)制:①網(wǎng)絡(luò)通過增加新節(jié)點(diǎn)而持續(xù)擴(kuò)張;②新節(jié)點(diǎn)擇優(yōu)連接到具有大量連接的節(jié)點(diǎn)上。現(xiàn)實(shí)中眾多網(wǎng)絡(luò)具有無標(biāo)度特性,該網(wǎng)絡(luò)模型應(yīng)用非常廣泛。該模型的具體算法在文獻(xiàn)[2]中有詳細(xì)介紹。文獻(xiàn)[1]中生成了基于配置模型的無標(biāo)度網(wǎng)絡(luò),其指數(shù)可調(diào)。

文獻(xiàn)[3]提出一種生成冪指數(shù)可調(diào)的無標(biāo)度網(wǎng)絡(luò)的算法。設(shè)初始網(wǎng)絡(luò)中包含N個孤立節(jié)點(diǎn),并將所有的節(jié)點(diǎn)從1到N依次編號,然后給節(jié)點(diǎn)i賦權(quán)值pi=i-α,其中,α是一個控制參數(shù)。將所有權(quán)值加權(quán)歸一化,即

(1)

從而有

(2)

可以證明,根據(jù)此算法生成的網(wǎng)絡(luò),其度分布滿足冪率特性,即P(k)∝k-γ,并且γ滿足

(3)

通過調(diào)節(jié)控制參數(shù)α在區(qū)間[0,1)內(nèi)變化,可以生成冪率指數(shù)γ在(2,+∞)內(nèi)的無標(biāo)度網(wǎng)絡(luò)。

1.2　邊權(quán)重的定義

現(xiàn)實(shí)中很多網(wǎng)絡(luò)都是有權(quán)網(wǎng)絡(luò),一個具體的網(wǎng)絡(luò)可以由點(diǎn)集V和邊集E組成的圖來表示,N=|V|為節(jié)點(diǎn)數(shù),M=|E|為邊數(shù)。一般使用權(quán)重鄰接矩陣w=(wij)n×n表示加權(quán)網(wǎng)絡(luò)邊權(quán)重。wij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j連接的邊的權(quán)重,當(dāng)網(wǎng)絡(luò)中各條邊的權(quán)值都相同時,加權(quán)網(wǎng)絡(luò)即退化為無權(quán)網(wǎng)絡(luò)。邊的權(quán)重與兩個節(jié)點(diǎn)的度相關(guān),假設(shè)網(wǎng)絡(luò)的某條邊所連兩個節(jié)點(diǎn)i和j的度值分別為ki和kj,那么這條邊的權(quán)重可以定義為

(4)

式中,θ(θ>0)是一個可調(diào)的權(quán)重參數(shù),用于描述所連兩節(jié)點(diǎn)間聯(lián)系的強(qiáng)度。

1.3　邊攻擊策略

以往對于復(fù)雜網(wǎng)絡(luò)魯棒性的研究大多是基于節(jié)點(diǎn)的攻擊。邊攻擊策略的定義是基于邊的重要性度量指標(biāo),如邊的權(quán)重,即將邊按照其權(quán)重的大小進(jìn)行排序并移除。邊攻擊策略可以按照邊的重要性度量指標(biāo)攻擊網(wǎng)絡(luò),采用3種攻擊策略,即基于初始圖面向邊權(quán)重的重要性度量指標(biāo)的攻擊。這3種攻擊策略定義分別如下:

(1) 邊的權(quán)重隨機(jī)攻擊策略(random weight removal strategy,RW):將網(wǎng)絡(luò)生成的邊按照其權(quán)重大小隨機(jī)選擇進(jìn)行移除。

(2) 邊的權(quán)重由小到大攻擊策略(low weight removal strategy, LW):將網(wǎng)絡(luò)生成的邊按照其權(quán)重由小到大的順序進(jìn)行排序,按照此排序結(jié)果對邊進(jìn)行移除。

(3) 邊的權(quán)重由大到小攻擊策略(high weight removal strategy, HW):將網(wǎng)絡(luò)生成的邊按照其權(quán)重由大到小的順序進(jìn)行排序,按照此排序結(jié)果對邊進(jìn)行移除。

1.4　網(wǎng)絡(luò)魯棒性測度

復(fù)雜網(wǎng)絡(luò)的魯棒性可以用最大連通子圖[15]、平均路徑長度[19]和自然連通度[26]等多種指標(biāo)進(jìn)行測度。

文中采用最大連通子圖相對值S和平均路徑長度L兩種指標(biāo)共同來衡量網(wǎng)絡(luò)的崩潰程度。特別地,對于網(wǎng)絡(luò)的毀損效應(yīng)不考慮級聯(lián)損失。

(1)S定義為被攻擊后的網(wǎng)絡(luò)最大連通子圖的規(guī)模N′與原始網(wǎng)絡(luò)規(guī)模N的比值,即

S=N′/N

(5)

式中,N′表示相繼故障結(jié)束后網(wǎng)絡(luò)的最大連通子圖所含的節(jié)點(diǎn)個數(shù);N表示初始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。S的值越大,表示網(wǎng)絡(luò)的魯棒性越強(qiáng)。比較網(wǎng)絡(luò)遭到攻擊前后的最大連通子圖的相對大小S,可以直觀地反映網(wǎng)絡(luò)遭到攻擊與破壞的程度。

(2) 網(wǎng)絡(luò)的平均路徑長度L定義為任意兩個節(jié)點(diǎn)之間的距離的平均值,即

(6)

式中,N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù);dij為網(wǎng)絡(luò)中任意兩個節(jié)點(diǎn)i和j之間的最短距離。一般來說,平均路徑長度越短,網(wǎng)絡(luò)的連通性越好。

1.5　邊攻擊代價

關(guān)于復(fù)雜網(wǎng)絡(luò)攻擊性研究大多基于無代價條件或基于代價時節(jié)點(diǎn)的攻擊。但是,不同網(wǎng)絡(luò)節(jié)點(diǎn)和邊的性質(zhì)不同,攻擊代價是不同的。文中采用邊的權(quán)重近似衡量攻擊代價,即costi=wi。總的攻擊代價定義為

(7)

式中,we是邊e的權(quán)重;M是生成的總邊數(shù);Z是移除邊的數(shù)量總和。

1.6　基于代價的復(fù)雜網(wǎng)絡(luò)邊攻擊模型算法

根據(jù)第1.1節(jié)～第1.5節(jié)的相關(guān)定義,該模型具體算法步驟設(shè)計如下:

步驟1按照第1.1節(jié)中的算法生成一定規(guī)模的BA無標(biāo)度網(wǎng)絡(luò)和指數(shù)可調(diào)的無標(biāo)度網(wǎng)絡(luò)。

步驟2按照邊的權(quán)重式(4)分別求出兩種網(wǎng)絡(luò)中節(jié)點(diǎn)之間所連邊的權(quán)重。

步驟3設(shè)定代價初始值,將邊按照第1.3節(jié)中的3種策略分別進(jìn)行攻擊,將被攻擊的邊的權(quán)重按照式(7)計算ρ值,如果ρ的值比所給代價值小,那么這條邊被移除,重復(fù)此步驟直到ρ的值達(dá)到所給的代價值。

步驟4按照式(5)和式(6)分別計算每種網(wǎng)絡(luò)遭攻擊后的最大連通子圖的大小S與平均路徑長度L。

步驟5輸出結(jié)果。

2　實(shí)驗(yàn)仿真結(jié)果及分析

為了更好地研究考慮代價時邊攻擊策略的有效性,文中選取BA無標(biāo)度網(wǎng)絡(luò)和指數(shù)可調(diào)的無標(biāo)度網(wǎng)絡(luò)分別進(jìn)行實(shí)驗(yàn)。由于模型中權(quán)重參數(shù)的影響,實(shí)驗(yàn)分別基于邊權(quán)參數(shù)θ=1,2,3的不同情況。文中仿真均在復(fù)雜網(wǎng)絡(luò)邊攻擊后的毀損效應(yīng)不包含級聯(lián)損失的情況下進(jìn)行。每組實(shí)驗(yàn)均進(jìn)行15次,取平均值作為最終仿真結(jié)果。

2.1　邊攻擊代價對BA無標(biāo)度網(wǎng)絡(luò)魯棒性的影響

首先,以BA無標(biāo)度網(wǎng)絡(luò)為例,實(shí)驗(yàn)中網(wǎng)絡(luò)參數(shù)設(shè)置為N=1 000,m=m0=2，其中，N為網(wǎng)絡(luò)生成的節(jié)點(diǎn)總數(shù)；m0為初始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)；m為新節(jié)點(diǎn)所連接的已存在的節(jié)點(diǎn)數(shù)。不同邊權(quán)參數(shù)下BA無標(biāo)度網(wǎng)絡(luò)魯棒性隨邊攻擊策略的變化曲線如圖1所示。同一攻擊策略下邊權(quán)參數(shù)對BA無標(biāo)度網(wǎng)絡(luò)魯棒性的影響如圖2所示。

圖1　不同邊攻擊策略對BA無標(biāo)度網(wǎng)絡(luò)魯棒性的影響

圖2　邊權(quán)參數(shù)對BA無標(biāo)度網(wǎng)絡(luò)魯棒性的影響

圖1為BA無標(biāo)度網(wǎng)絡(luò)的魯棒性隨不同邊攻擊策略的變化曲線圖。圖1(a)和圖1(d)中邊權(quán)參數(shù)θ=1。由圖1(a)可以看出,當(dāng)0<ρ<0.25時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:LW策略,RW策略,HW策略;當(dāng)0.25<ρ<1時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:RW策略,LW策略,HW策略。由圖1(d)可以看出,LW策略下,L呈現(xiàn)下降的趨勢;而RW策略和HW策略下,L都是先變大,若干次攻擊后L才開始下降。當(dāng)0<ρ<0.25時,LW策略下,網(wǎng)絡(luò)開始產(chǎn)生孤立的節(jié)點(diǎn),L值開始減小;而采用RW策略或HW策略時,L呈現(xiàn)上升態(tài)勢,說明這時網(wǎng)絡(luò)還沒有產(chǎn)生孤立節(jié)點(diǎn),但網(wǎng)絡(luò)的連通性已下降,RW策略對應(yīng)的網(wǎng)絡(luò)連通性比HW策略的差,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:LW策略,RW策略,HW策略。當(dāng)0.25<ρ<1時,RW策略對應(yīng)的曲線比LW策略的下降趨勢更快,而HW策略下,L值還是先增大后減小,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:RW策略,LW策略,HW策略。圖1(b)和圖1(e)中邊權(quán)參數(shù)θ=2。由圖1(b)看出,當(dāng)0<ρ<0.35時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:LW策略,RW策略,HW策略;當(dāng)0.35<ρ<1時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:RW策略,LW策略,HW策略。由圖1(e)得知,LW策略下,L呈現(xiàn)下降的趨勢;而RW策略和HW策略下,L都是先變大,若干次攻擊后L才開始下降。當(dāng)0<ρ<0.35時,LW策略下,網(wǎng)絡(luò)開始產(chǎn)生孤立的節(jié)點(diǎn),L值開始減小;而采用RW策略或HW策略時,L呈現(xiàn)上升態(tài)勢,說明這時網(wǎng)絡(luò)還沒有產(chǎn)生孤立節(jié)點(diǎn),但網(wǎng)絡(luò)的連通性已下降,RW策略對應(yīng)的網(wǎng)絡(luò)連通性比HW策略的差,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:LW策略,RW策略,HW策略。當(dāng)0.35<ρ<1時,RW策略對應(yīng)的曲線比LW策略的下降趨勢更快,而HW策略下,L值還是先增大后減小,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:RW策略,LW策略,HW策略。圖1(c)和圖1(f)中邊權(quán)參數(shù)θ=3。由圖1(c)可以看出,當(dāng)0<ρ<0.33時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:LW策略,RW策略,HW策略;當(dāng)0.33<ρ<1時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:RW策略,LW策略,HW策略。由圖1(f)可以看出,LW策略下,L呈現(xiàn)下降的趨勢;而RW策略和HW策略下,L都是先變大,若干次攻擊后L才開始下降。當(dāng)0<ρ<0.33時,LW策略下,網(wǎng)絡(luò)開始產(chǎn)生孤立的節(jié)點(diǎn),L值開始減小;而采用RW策略或HW策略時,L呈現(xiàn)上升態(tài)勢,說明這時網(wǎng)絡(luò)還沒有產(chǎn)生孤立節(jié)點(diǎn),但網(wǎng)絡(luò)的連通性已下降,RW策略對應(yīng)的網(wǎng)絡(luò)連通性比HW策略的差,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:LW策略,RW策略,HW策略。當(dāng)0.33<ρ<1時,RW策略對應(yīng)的曲線比LW策略的下降趨勢更快,而HW策略下,L值還是先增大后減小,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:RW策略,LW策略,HW策略。

圖2為同一邊攻擊策略下,可調(diào)邊權(quán)參數(shù)對BA無標(biāo)度網(wǎng)絡(luò)魯棒性影響的曲線圖。圖2(a)和圖2(d)中采用LW策略。由圖2(a)得知,同一邊攻擊代價下,θ=3對應(yīng)的網(wǎng)絡(luò)曲線下降趨勢最快,θ=2對應(yīng)的曲線次之,θ=1對應(yīng)的曲線下降趨勢最慢。從而,權(quán)重參數(shù)θ不同取值情況下對網(wǎng)絡(luò)的破壞順序:θ=3時對網(wǎng)絡(luò)攻擊效果最好,θ=2次之,θ=1時攻擊效果最差。由圖2(d)得知,LW策略下,3種θ值對應(yīng)的L值都呈現(xiàn)減小趨勢,說明LW策略下網(wǎng)絡(luò)較容易產(chǎn)生孤立節(jié)點(diǎn)。同一邊攻擊代價下,θ=3對應(yīng)的網(wǎng)絡(luò)L值減小趨勢最快,θ=2對應(yīng)的曲線次之,θ=1對應(yīng)的L值減小趨勢最慢。由此得出,權(quán)重參數(shù)θ不同取值情況下對網(wǎng)絡(luò)的破壞順序:θ=3時對網(wǎng)絡(luò)攻擊效果最好,θ=2次之,θ=1時攻擊效果最差。圖2(b)和圖2(e)中采用RW策略。由圖2(b)得知,邊權(quán)參數(shù)不同取值下網(wǎng)絡(luò)曲線幾乎重合,表明設(shè)定不同邊權(quán)參數(shù)值對網(wǎng)絡(luò)破壞效果幾乎相同。由圖2(e)得知,L值在不同邊權(quán)參數(shù)取值下都呈現(xiàn)先增大后減小的趨勢,但趨勢幾乎一致,表明RW策略下設(shè)定不同邊權(quán)參數(shù)對網(wǎng)絡(luò)毀傷效果幾乎相同。圖2(c)和圖2(f)采用HW策略。由圖2(c)得知,同一邊攻擊代價下,θ=1對應(yīng)的網(wǎng)絡(luò)曲線下降趨勢最快,θ=2對應(yīng)的曲線次之,θ=3對應(yīng)的曲線下降趨勢最慢。從而,權(quán)重參數(shù)θ不同取值情況下對網(wǎng)絡(luò)的破壞順序:θ=1時對網(wǎng)絡(luò)攻擊效果最好,θ=2時次之,θ=3時攻擊效果最差。由圖2(f)得知,HW策略下,3種θ值對應(yīng)的L值都呈現(xiàn)先增后減的趨勢。當(dāng)0<ρ<0.9時,3種θ值下的L都呈增大趨勢,網(wǎng)絡(luò)連通性由弱到強(qiáng)依次是:θ=1,θ=2,θ=3。當(dāng)0.9<ρ<1時,θ=1對應(yīng)的L值開始減小,θ=2與θ=3對應(yīng)的L值先增后減,θ=2比θ=3的曲線變化明顯。

對于BA無標(biāo)度網(wǎng)絡(luò),綜合圖1和圖2的仿真結(jié)果可以得知:

(1) 可調(diào)邊權(quán)參數(shù)下,HW策略攻擊效果都不是最好的;當(dāng)攻擊代價較小時,LW策略的攻擊效果最好。

(2) 當(dāng)采用LW策略時,設(shè)置邊權(quán)參數(shù)θ=3時對網(wǎng)絡(luò)攻擊效果最好;當(dāng)采用HW策略時,設(shè)置邊權(quán)參數(shù)θ=1時對網(wǎng)絡(luò)攻擊效果最好。

2.2　邊攻擊代價對指數(shù)可調(diào)無標(biāo)度網(wǎng)絡(luò)魯棒性的影響

BA無標(biāo)度網(wǎng)絡(luò)度分布的冪率指數(shù)γ恒定為3,而大多數(shù)具有無標(biāo)度特性的真實(shí)復(fù)雜網(wǎng)絡(luò)的冪率指數(shù)在2～3。γ越小,網(wǎng)絡(luò)在度分布上的非均勻性越強(qiáng);反之,度分布均勻性越強(qiáng)。選取指數(shù)可調(diào)的無標(biāo)度網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn),網(wǎng)絡(luò)參數(shù)設(shè)置為N=1 000,m=2,γ=2.4。圖3為不同邊攻擊策略對指數(shù)可調(diào)無標(biāo)度網(wǎng)絡(luò)魯棒性的影響。 圖4為邊權(quán)參數(shù)對指數(shù)可調(diào)無標(biāo)度網(wǎng)絡(luò)魯棒性的影響。

圖3　不同邊攻擊策略對指數(shù)可調(diào)的無標(biāo)度網(wǎng)絡(luò)魯棒性的影響

圖4　邊權(quán)參數(shù)對指數(shù)可調(diào)無標(biāo)度網(wǎng)絡(luò)魯棒性的影響

圖3為指數(shù)可調(diào)的無標(biāo)度網(wǎng)絡(luò)的魯棒性隨不同邊攻擊策略的變化曲線圖。圖3(a)和圖3(d)中設(shè)置邊權(quán)參數(shù)θ=1。由圖3(a)可以看出,當(dāng)0<ρ<0.3時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:LW策略,RW策略,HW策略;當(dāng)0.3<ρ<1時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:RW策略,LW策略,HW策略。由圖3(d)可以看出,LW策略下,L呈現(xiàn)下降的趨勢;而RW策略和HW策略下,L都是先增大,若干次攻擊后L才開始下降。當(dāng)0<ρ<0.3時,LW策略下,L值開始減小,網(wǎng)絡(luò)開始產(chǎn)生孤立的節(jié)點(diǎn);而采用RW策略或HW策略時,L呈現(xiàn)上升態(tài)勢,說明這時網(wǎng)絡(luò)還沒有產(chǎn)生孤立節(jié)點(diǎn),但網(wǎng)絡(luò)的連通性已下降,RW策略對應(yīng)的網(wǎng)絡(luò)連通性比HW策略的差,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:LW策略,RW策略,HW策略。當(dāng)0.3<ρ<1時,RW策略對應(yīng)的曲線比LW策略的下降趨勢更快,而HW策略下,L值還是先增大后減小,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:RW策略,LW策略,HW策略。圖3(b)和圖3(e)中設(shè)置邊權(quán)參數(shù)θ=2。由圖3(b)看出,當(dāng)0<ρ<0.35時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:LW策略,RW策略,HW策略;當(dāng)0.35<ρ<1時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:RW策略,LW策略,HW策略。由圖3(e)得知,LW策略下,L呈現(xiàn)減小趨勢;而RW策略或HW策略下,L都是先變大,若干次攻擊后L才開始下降。當(dāng)0<ρ<0.35時,LW策略下,L值開始減小,網(wǎng)絡(luò)開始產(chǎn)生孤立的節(jié)點(diǎn);而采用RW策略或HW策略時,L呈現(xiàn)上升態(tài)勢,說明這時網(wǎng)絡(luò)還沒有產(chǎn)生孤立節(jié)點(diǎn),但網(wǎng)絡(luò)的連通性已下降,RW策略對應(yīng)的網(wǎng)絡(luò)連通性比HW策略的差,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:LW策略,RW策略,HW策略。當(dāng)0.35<ρ<1時,RW策略對應(yīng)的曲線比LW策略的下降趨勢更快,而HW策略下,L值還是先增大后減小,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:RW策略,LW策略,HW策略。圖3(c)和圖3(f)中邊權(quán)參數(shù)θ=3。由圖3(c)可以看出,當(dāng)0<ρ<0.33時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:LW策略,RW策略,HW策略;當(dāng)0.33<ρ<1時,對于同一攻擊代價,3種不同邊攻擊策略有效性由強(qiáng)到弱依次是:RW策略,LW策略,HW策略。由圖3(f)可以看出,LW策略下,L呈現(xiàn)下降的趨勢;而RW策略和HW策略下,L都是先變大,若干次攻擊后L才開始下降。當(dāng)0<ρ<0.33時,LW策略下,網(wǎng)絡(luò)開始產(chǎn)生孤立的節(jié)點(diǎn),L值開始減小;而采用RW策略或HW策略時,L呈現(xiàn)上升趨勢,說明這時網(wǎng)絡(luò)還沒有產(chǎn)生孤立節(jié)點(diǎn),但網(wǎng)絡(luò)的連通性已下降,RW策略對應(yīng)的網(wǎng)絡(luò)連通性比HW策略的差,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:LW策略,RW策略,HW策略。當(dāng)0.33<ρ<1時,RW策略對應(yīng)的曲線比LW策略的下降趨勢更快,而HW策略下,L值還是先增大后減小,此時3種策略對網(wǎng)絡(luò)的攻擊效率由快到慢依次是:RW策略,LW策略,HW策略。

圖4為同一邊攻擊策略下,邊權(quán)參數(shù)對指數(shù)可調(diào)無標(biāo)度網(wǎng)絡(luò)魯棒性影響的變化曲線圖。圖4(a)和圖4(d)中采用LW策略。由圖4(a)得知,同一邊攻擊代價下,θ=3對應(yīng)的網(wǎng)絡(luò)曲線下降趨勢最快,θ=2對應(yīng)的曲線次之,θ=1對應(yīng)的曲線下降趨勢最慢。從而,權(quán)重參數(shù)θ不同取值情況下對網(wǎng)絡(luò)的破壞順序:θ=3時對網(wǎng)絡(luò)攻擊效果最好,θ=2次之,θ=1時攻擊效果最差。由圖4(d)得知,LW策略下,3種θ值對應(yīng)的L值都呈現(xiàn)減小趨勢,說明LW策略下網(wǎng)絡(luò)較容易產(chǎn)生孤立節(jié)點(diǎn)。同一邊攻擊代價下,θ=3對應(yīng)的網(wǎng)絡(luò)L值減小趨勢最快,θ=2對應(yīng)的曲線次之,θ=1對應(yīng)的L值減小趨勢最慢。由此得出,權(quán)重參數(shù)θ不同取值情況下對網(wǎng)絡(luò)的破壞順序:θ=3時對網(wǎng)絡(luò)攻擊效果最好,θ=2次之,θ=1時攻擊效果最差。圖4(b)和圖4(e)采用RW策略。由圖4(b)得知,邊權(quán)參數(shù)不同取值下網(wǎng)絡(luò)曲線幾乎重合,表明設(shè)定不同邊權(quán)參數(shù)值對網(wǎng)絡(luò)破壞效果幾乎相同。由圖4(e)得知,L值在不同邊權(quán)參數(shù)取值下都呈現(xiàn)先增大后減小的趨勢,但趨勢幾乎一致,表明RW策略下設(shè)定不同邊權(quán)參數(shù)對網(wǎng)絡(luò)毀傷效果幾乎相同。圖4(c)和圖4(f)采用HW策略。由圖4(c)得知,同一邊攻擊代價下,θ=1對應(yīng)的網(wǎng)絡(luò)曲線下降趨勢最快,θ=2對應(yīng)的曲線次之,θ=3對應(yīng)的曲線下降趨勢最慢。從而,權(quán)重參數(shù)θ不同取值情況下對網(wǎng)絡(luò)的破壞順序:θ=1時對網(wǎng)絡(luò)攻擊效果最好,θ=2時次之,θ=3時攻擊效果最差。由圖4(f)得知,采用HW策略時,不同θ值對應(yīng)的L值都呈現(xiàn)先增后減的趨勢。當(dāng)0<ρ<0.9時,3種情況下的L值都呈增大趨勢,網(wǎng)絡(luò)連通性由弱到強(qiáng)依次是:θ=1,θ=2,θ=3。當(dāng)0.9<ρ<1時,θ=1對應(yīng)的L值開始減小,而θ=2與θ=3對應(yīng)的L值先增后減,但θ=2比θ=3的曲線變化趨勢明顯。

對于指數(shù)可調(diào)的無標(biāo)度網(wǎng)絡(luò),綜合圖3和圖4的仿真結(jié)果可以得知:

(1) 不同邊權(quán)參數(shù)下,HW策略攻擊效果較差;當(dāng)攻擊代價較小時,LW策略是最好的攻擊策略。

(2) 當(dāng)采用LW策略時,取邊權(quán)參數(shù)θ=3時對網(wǎng)絡(luò)攻擊效果最好;當(dāng)采用HW策略時,取邊權(quán)參數(shù)θ=1時對網(wǎng)絡(luò)攻擊效果最好。

3　結(jié)　論

文中提出一種基于代價的復(fù)雜網(wǎng)絡(luò)邊攻擊模型,對考慮代價時BA無標(biāo)度網(wǎng)絡(luò)和指數(shù)可調(diào)的無標(biāo)度網(wǎng)絡(luò)的邊攻擊策略有效性進(jìn)行了深入研究。研究結(jié)果表明:

(1) 邊權(quán)參數(shù)θ取不同值時,采用HW策略攻擊效果都不是最好的。現(xiàn)實(shí)中在攻擊代價較小時,選擇相對薄弱的邊進(jìn)行攻擊達(dá)到的攻擊效果較好。

(2) 通過調(diào)節(jié)權(quán)重參數(shù)θ,相應(yīng)的復(fù)雜網(wǎng)絡(luò)邊攻擊策略攻擊效果可以得到優(yōu)化。

復(fù)雜網(wǎng)絡(luò)邊攻擊后的網(wǎng)絡(luò)毀損效應(yīng)可能包含級聯(lián)損失,這將是下一步研究的重點(diǎn)。

參考文獻(xiàn)：

[1] MOLLOY M R, REED B. A critical point for random graphs with a given degree sequence[J]. Random Structures and Algorithms, 1995, 6(2/3): 161-179.

[2] BARABASI A L, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439):509-512.

[3] GOH K I, KAHNG B, KIM D. Universal behavior of load distribution in scale free networks[J]. Physical Review Letters, 2001, 87(27): 278701.

[4] FENG J, LI X M, MAO B H, et al. Weighted complex network analysis of the Beijing subway system: train and passenger flows[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 474: 213-223.

[5] CHEN Y, WANG X L, XIANG X, et al. Overlapping community detection in weighted networks via a bayesian approach[J]. Physica A: Statistical Mechanics and Its Applications, 2017, 468: 790-801.

[6] WEI D J, CHEN X W, DENG Y. Multifractality of weighted complex networks[J].Chinese Journal of Physics,2016,54(3): 416-423.

[7] WU S Y, SHAO F J, ZHANG Q, et al. Topology association analysis in weighted protein interaction network for gene prioritization[J].Physica A:Statistical Mechanics and Its Applications, 2016, 461: 262-269.

[8] 孫睿,羅萬伯.具有非一致傳播率的無標(biāo)度網(wǎng)絡(luò)謠言傳播模型[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2014,11(3):6-11.

SUN R, LUO W B. Scale free rumor propagation model with non-uniform transmission[J]. Complex Systems and Complex Science, 2014, 11(3):6-11.

[9] 張?zhí)m華. 復(fù)雜網(wǎng)絡(luò)建模的仿真與應(yīng)用研究[D]. 大連: 大連理工大學(xué), 2013.

ZHANG L H. Simulation and application of complex network modeling[D]. Dalian: Dalian University of Technology, 2013.

[10] BA Q, LI J, HUANG C, et al. Topological, functional, and dynamic properties of the protein interaction networks rewired by benzo(a)pyrene[J]. Toxicology and Applied Pharmacology, 2015, 283(2): 83-91.

[11] ZHANG C M, HUANG H T. Optimal control strategy for a novel computer virus propagation model on scale-free networks[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 451: 251-265.

[12] 徐雪飛, 李建華, 沈迪, 等. 地空多元復(fù)雜網(wǎng)絡(luò)用頻優(yōu)選模型研究[J]. 系統(tǒng)工程與電子技術(shù), 2016, 38(1): 77-83.

XU X F, LI J H, SHEN D, et al. Research of air-ground multi-element frequency optimization model in complex network[J]. Systems Engineering and Electronics, 2016, 38(1): 77-83.

[13] 王楠. 期貨時間序列復(fù)雜網(wǎng)絡(luò)特征與投資組合策略研究[D]. 北京: 中國地質(zhì)大學(xué), 2016.

WANG N. Research on complex network characteristics and portfolio strategy of futures time series[D]. Beijing: China University of Geosciences, 2016.

[14] 張超,張鳳鳴,王瑛,等.基于復(fù)雜網(wǎng)絡(luò)視角的航空通信網(wǎng)絡(luò)魯棒性分析[J].系統(tǒng)工程與電子技術(shù),2015,31(1):180-184.

ZHANG C, ZHANG F M, WANG Y, et al. Robustness analysis of aeronautical communication networks based on complex network[J]. Systems Engineering and Electronics, 2015, 31(1):180-184.

[15] MOTTER A E, LAI Y C. Cascade-based attacks on complex networks[J]. Physical Review E: Statistical Nonlinear & Soft Matter Physics, 2002, 66(2): 065102.

[16] HONG C, HE N, LORDAN O, et al. Efficient calculation of the robustness measure R for complex networks[J]. Physica A:Statistical Mechanics and Its Applications, 2017,478:63-68.

[17] 陸余良, 楊斌. 域間路由系統(tǒng)級聯(lián)失效分析與建模[J]. 系統(tǒng)工程與電子技術(shù), 2016, 38(1): 172-178.

LU Y L, YANG B. Analysis and modeling of inter domain routing system cascading failure[J]. Systems Engineering and Electronics, 2016, 38(1):172-178.

[18] 郭東超. 復(fù)雜網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的魯棒性與動力學(xué)過程研究[D]. 北京: 北京交通大學(xué), 2014.

GUO D C. Research on robustness and dynamic process of complex network topology[D]. Beijing: Beijing Jiaotong University, 2014.

[19] ALBERT R, JEONG H, BARABASI A L. Error and attack tolerance of complex networks[J]. Nature, 2000, 406(6794): 378-382.

[20] LIU Y Y. Attack vulnerability of complex networks with different initial failure[C]∥Proc.of the 35th Chinese Control Conference, 2016: 1292-1295.

[21] 王建偉,榮莉莉.面向相繼故障的復(fù)雜網(wǎng)絡(luò)上邊襲擊策略研究[J].系統(tǒng)工程學(xué)報,2011,26(1): 1-8.

WANG J W, RONG L L. Research on the attack strategy of the complex network with cascading failures[J]. Journal of Systems Engineering, 2011, 26(1):1-8.

[22] LORDAN O, SALLAN J M, ESCORIHUELA N E, et al. Robustness of airline route networks[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 445: 18-26.

[23] HE Z W, LIU S, ZHAN M. Dynamical robustness analysis of weighted complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2013, 392(18): 4181-4191.

[24] 吳俊, 譚索怡, 譚躍進(jìn), 等. 基于自然連通度的復(fù)雜網(wǎng)絡(luò)抗毀性分析[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2014, 11(1): 77-86.

WU J, TAN S Y, TAN Y J, et al. Analysis of invulnerability in complex networks based on natural connectivity[J]. Complex Systems and Complex Science, 2014, 11(1):77-86.

[25] WU J, BARAHONA M, TAN Y J, et al. Robustness of random graphs based on graph spectra[J]. Chaos, Solitons & Fractals, 2012, 22(4): 043101.

[26] ESTRADA E, HATANO N, BENZI M. The physics of communicability in complex networks[J]. Physics Reports, 2011, 514(3): 89-119.

[27] 崔文巖, 孟相如, 康巧燕, 等. 基于復(fù)合邊權(quán)重的加權(quán)復(fù)雜網(wǎng)絡(luò)級聯(lián)抗毀性優(yōu)化[J]. 系統(tǒng)工程與電子技術(shù), 2017, 39(2):355-361.

CUI W Y, MENG X R, KANG Q Y, et al. Optimization of cascading invulnerability on weighted complex networks based on composite edge weight model[J]. Systems Engineering and Electronics, 2017, 39(2): 355-361.

[28] HAO Y H, HAN J H, LIN Y, et al. Vulnerability of complex networks under three-level-tree attacks[J]. Physica A: Statistical Mechanics and Its Applications, 2016, 462: 674-683.

[29] NIE T Y, GUO Z, ZHAO K, et al. New attack strategies for complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2015, 424: 248-253.

[30] HONG C, ZHANG J, CAO X B, et al. Structural properties of the Chinese air transportation multilayer network[J]. Chaos, Solitons & Fractals, 2016, 86: 28-34.

[31] WANG J W, JIANG C, QIAN J F. Robustness of internet under targeted attack: a cascading failure perspective[J]. Journal of Network and Computer Applications, 2014, 40(7): 97-104.

[32] 覃俊, 吳泓潤, 易云飛, 等. 代價下復(fù)雜網(wǎng)絡(luò)攻擊策略有效性研究[J]. 北京理工大學(xué)學(xué)報, 2013, 33(1): 67-72.

QIN J, WU H R, YI Y F, et al. Effectiveness of attack strategies of complex networks with cost[J]. Transaction of Beijing Institute of Technology, 2013, 33(1): 67-72.

[33] WANG X G, GUAN S G, LAI C H. Protecting infrastructure networks from cost-based attacks[J]. New Journal of Physics, 2009, 11(3): 1-9.

[34] DENG Y, WU J. Optimal attack strategy based on limited cost model on complex network[C]∥Proc.of the IEEE International Conference on Systems,Man,and Cybernetics,2015:105-108.

[35] HONG C, CAO X B, DU W B, et al. The effect of attack cost on network robustness[J]. Physica Scripta,2013,87(5):458-465.