基于局部熵的級(jí)聯(lián)故障模型初始負(fù)載定義方式

董 昂,吳亞麗,任遠(yuǎn)光,馮夢(mèng)琦

(西安理工大學(xué) a.自動(dòng)化與信息工程學(xué)院;b.陜西省復(fù)雜系統(tǒng)控制與智能信息處理重點(diǎn)實(shí)驗(yàn)室,西安 710048)

0 引言

社交網(wǎng)絡(luò),電力網(wǎng)絡(luò),生物網(wǎng)絡(luò)等復(fù)雜網(wǎng)絡(luò)是當(dāng)今社會(huì)的重要組成部分[1],其復(fù)雜性體現(xiàn)在真實(shí)網(wǎng)絡(luò)海量的節(jié)點(diǎn)及節(jié)點(diǎn)之間復(fù)雜的連接關(guān)系。在復(fù)雜網(wǎng)絡(luò)中,節(jié)點(diǎn)和邊承擔(dān)的負(fù)載是不斷演化的,具有一定的動(dòng)力學(xué)特征。當(dāng)節(jié)點(diǎn)或邊的負(fù)載大于自身容量而導(dǎo)致失效后,失效節(jié)點(diǎn)或邊的負(fù)載通過(guò)網(wǎng)絡(luò)的相互連接被重新分配到相關(guān)節(jié)點(diǎn)或邊上,從而引起其他節(jié)點(diǎn)或邊失效,產(chǎn)生級(jí)聯(lián)效應(yīng),嚴(yán)重時(shí)會(huì)導(dǎo)致整個(gè)網(wǎng)絡(luò)的癱瘓,這種由微小事件引發(fā)的連鎖故障稱為級(jí)聯(lián)失效。現(xiàn)實(shí)生活中存在許多級(jí)聯(lián)故障問(wèn)題,例如:運(yùn)輸網(wǎng)絡(luò)級(jí)聯(lián)失效[2]、裝備保障網(wǎng)絡(luò)級(jí)聯(lián)失效[3]、電力網(wǎng)絡(luò)抗毀性分析[4]、局域路由器級(jí)聯(lián)問(wèn)題[5]等。建立普適性的級(jí)聯(lián)故障模型,研究其動(dòng)力學(xué)特性,已經(jīng)成為預(yù)防和控制級(jí)聯(lián)故障的有效手段[6]。

近年來(lái),級(jí)聯(lián)故障模型的研究集中于節(jié)點(diǎn)初始負(fù)載的定義,節(jié)點(diǎn)容量的定義以及故障節(jié)點(diǎn)負(fù)載的分配方式[7]3個(gè)方面。文獻(xiàn)[8]假定網(wǎng)絡(luò)中的信息通過(guò)節(jié)點(diǎn)之間的最短路徑傳遞,因此利用介數(shù)定義節(jié)點(diǎn)的初始負(fù)載,并提出初始負(fù)載和容量呈線性關(guān)系,建立了經(jīng)典的ML模型。該模型能完整體現(xiàn)級(jí)聯(lián)故障過(guò)程,其容量分配方式也得到廣泛使用。文獻(xiàn)[9]定義網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的初始負(fù)載為其介數(shù)的冪函數(shù)。但介數(shù)作為一個(gè)全局量,在網(wǎng)絡(luò)拓?fù)涓叨葟?fù)雜的情況下,計(jì)算需要耗費(fèi)很大的算力。因此基于介數(shù)的初始負(fù)載定義方式不適合用于大規(guī)模復(fù)雜網(wǎng)絡(luò);基于此,文獻(xiàn)[10]假定每個(gè)節(jié)點(diǎn)的初始負(fù)載相互獨(dú)立,并在區(qū)間[Lmin,Lmax]上服從均勻分布。采用這種完全隨機(jī)的初始負(fù)載定義方式雖然簡(jiǎn)便,但是沒(méi)有利用網(wǎng)絡(luò)的結(jié)構(gòu)信息。文獻(xiàn)[11-13]分析了節(jié)點(diǎn)的度和初始負(fù)載的相關(guān)性,并使用節(jié)點(diǎn)的度定義其初始負(fù)載。如何充分利用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息已經(jīng)成為定義初始負(fù)載的有效方式。

熵的概念是由德國(guó)物理學(xué)家克勞修斯于1865年提出,最初是用來(lái)描述“能量退化”的物質(zhì)狀態(tài)參數(shù)之一,在熱力學(xué)中有廣泛的應(yīng)用。隨著統(tǒng)計(jì)物理、信息論等一系列科學(xué)理論的發(fā)展,當(dāng)人們認(rèn)識(shí)到熵的本質(zhì)是一個(gè)系統(tǒng)“內(nèi)在的混亂程度”時(shí),它在控制論、概率論、數(shù)論、天體物理、生命科學(xué)等領(lǐng)域都有了重要的應(yīng)用。文獻(xiàn)[14-15]最早將熵引入圖論中,提出了圖熵的概念,并認(rèn)為它能夠反映網(wǎng)絡(luò)的拓?fù)湫畔?文獻(xiàn)[16]采用圖中的一些不變量,如頂點(diǎn)個(gè)數(shù)、節(jié)點(diǎn)的度等信息來(lái)計(jì)算圖熵,并用信息函數(shù)來(lái)表示概率分布。文獻(xiàn)[17]采用節(jié)點(diǎn)的度作為非負(fù)整數(shù)元組來(lái)計(jì)算p,進(jìn)而計(jì)算圖熵。文獻(xiàn)[18]中提到了多種圖熵的定義方式,不同的圖熵在不同的場(chǎng)合下均作為一種度量,依據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)來(lái)衡量節(jié)點(diǎn)包含信息量的多少。基于此,本文針對(duì)級(jí)聯(lián)故障問(wèn)題的特點(diǎn),綜合考慮節(jié)點(diǎn)及其鄰居的信息,提出了一種基于局部熵的初始負(fù)載定義方式,在減少計(jì)算量的同時(shí),可以更好地模擬網(wǎng)絡(luò)中的級(jí)聯(lián)過(guò)程。通過(guò)比較在不同網(wǎng)絡(luò)中采用介數(shù)、度、局部熵定義初始負(fù)載的3種級(jí)聯(lián)故障模型面對(duì)不同類型攻擊時(shí)的魯棒性,驗(yàn)證本文提出局部熵概念的通用性及有效性。

1 基于度和介數(shù)的級(jí)聯(lián)故障初始負(fù)載定義

一個(gè)網(wǎng)絡(luò)通常由G=(V,E)建模,其中V為網(wǎng)絡(luò)G的節(jié)點(diǎn)集合,E為網(wǎng)絡(luò)G的邊集合。對(duì)于一個(gè)無(wú)向無(wú)權(quán)網(wǎng)絡(luò),可以由一個(gè)鄰接矩陣A表示。其中,A中的元素Aij的含義為

(1)

節(jié)點(diǎn)的度是與它直接相連的邊的數(shù)目。將節(jié)點(diǎn)vi的度表示為di,可以用鄰接矩陣的方式表示為

(2)

(3)

目前,級(jí)聯(lián)故障模型中節(jié)點(diǎn)初始負(fù)載多用節(jié)點(diǎn)的介數(shù)和度進(jìn)行定義。文獻(xiàn)[9]和文獻(xiàn)[11]分別采用了兩種定義方式。

(4)

(5)

其中,α為負(fù)荷系數(shù)。

節(jié)點(diǎn)的度是節(jié)點(diǎn)的特征之一,直接用節(jié)點(diǎn)的度定義其初始負(fù)載,簡(jiǎn)單方便但沒(méi)有考慮其鄰居節(jié)點(diǎn)信息。介數(shù)是一個(gè)全局量,它體現(xiàn)了節(jié)點(diǎn)在信息流通中的重要性,但在復(fù)雜網(wǎng)絡(luò)中計(jì)算介數(shù)需要耗費(fèi)巨大的算力。因此本文引入局部熵的概念,同時(shí)考慮節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)的信息來(lái)定義節(jié)點(diǎn)的初始負(fù)載,與介數(shù)定義相比大大降低了計(jì)算量。

2 局部熵的相關(guān)定義

(6)

在圖熵中,對(duì)于一個(gè)網(wǎng)絡(luò)G=(V,E),pi可以被定義為信息函數(shù)f的比值[16]:

(7)

p1+p2+…+p|V|=1

(8)

其中,f(vi)為節(jié)點(diǎn)vi的信息函數(shù)。

文獻(xiàn)[16]提出:信息函數(shù)f的定義并不唯一,其本質(zhì)要能夠反映拓?fù)浣Y(jié)構(gòu)的信息。在網(wǎng)絡(luò)中,節(jié)點(diǎn)vi的度di描述了節(jié)點(diǎn)vi與其鄰居節(jié)點(diǎn)的連接關(guān)系,因此本文使用節(jié)點(diǎn)的度定義信息函數(shù)。節(jié)點(diǎn)vi包含全局信息的熵Ei可以通過(guò)式(9)計(jì)算:

Ei=-pilogpi

(9)

對(duì)于一個(gè)網(wǎng)絡(luò)G=(V,E),定義節(jié)點(diǎn)vi的第k層鄰居節(jié)點(diǎn)集合為Sk(vi,G)。

Sk(vi,G)={v∈V|l(vi,v) =k}

(10)

其中,l(vi,v)為節(jié)點(diǎn)vi與節(jié)點(diǎn)v之間的最短路徑長(zhǎng)度,1≤k≤diamG(diamG是網(wǎng)絡(luò)直徑)。

整個(gè)網(wǎng)絡(luò)G可以看作由節(jié)點(diǎn)vi及其diamG層鄰居節(jié)點(diǎn)構(gòu)成,每層鄰居對(duì)節(jié)點(diǎn)vi的貢獻(xiàn)不同,應(yīng)對(duì)節(jié)點(diǎn)vi的各層鄰居提供的信息賦予不同權(quán)值。因此更新后的節(jié)點(diǎn)vi包含全局信息的熵定義為

(11)

其中,c1,c2,…cdiamG是呈指數(shù)遞減的正實(shí)數(shù)序列。

節(jié)點(diǎn)vi及其第k層鄰居節(jié)點(diǎn)的熵LE(vi,k)為

LE(vi,k)=-p(vi,k)logp(vi,k)

(12)

(13)

因此,節(jié)點(diǎn)vi的k級(jí)局部熵可以定義為

(14)

文獻(xiàn)[17]認(rèn)為節(jié)點(diǎn)vi對(duì)越接近它的節(jié)點(diǎn)影響越大,并對(duì)其第三層及以后的鄰居節(jié)點(diǎn)的影響可以忽略不計(jì),即對(duì)vi包含信息量影響最大的是其前兩層的鄰居節(jié)點(diǎn)。為了減少計(jì)算量,并使節(jié)點(diǎn)vi包含更多的信息,本文在建立級(jí)聯(lián)故障模型時(shí)充分考慮節(jié)點(diǎn)及其單層鄰居節(jié)點(diǎn)的信息。

3 基于局部熵的級(jí)聯(lián)故障初始負(fù)載定義

3.1 基于局部熵的級(jí)聯(lián)故障模型概念

本文在定義節(jié)點(diǎn)的初始負(fù)載時(shí),利用信息熵的概念定義了網(wǎng)絡(luò)中節(jié)點(diǎn)的1級(jí)局部熵,考慮了節(jié)點(diǎn)及其1層鄰居節(jié)點(diǎn)的拓?fù)湫畔ⅰ６x節(jié)點(diǎn)vi的初始負(fù)載為

Li0=LEα(vi,1)

(15)

其中,α為負(fù)荷系數(shù)。

節(jié)點(diǎn)容量的定義采用與ML模型相同的方式,即節(jié)點(diǎn)容量與節(jié)點(diǎn)初始負(fù)載呈線性關(guān)系,具體如式(16)所示:

Ci= (1 +T)Li0

(16)

其中,T為容忍系數(shù),且T≥0。T值越大時(shí),節(jié)點(diǎn)的容量越大,因此網(wǎng)絡(luò)抵抗攻擊能力越強(qiáng),魯棒性越強(qiáng)。但T又是與成本有關(guān)的量,當(dāng)T值越大時(shí),消耗的成本也會(huì)越大。

Lj=Lj+ΔLj

(17)

(18)

由定義可知,若節(jié)點(diǎn)vj更新后的負(fù)載值Lj大于節(jié)點(diǎn)vj的容量值Cj,則節(jié)點(diǎn)vj故障,并開始級(jí)聯(lián)過(guò)程。

Lj+ΔLj>Cj

(19)

圖1 級(jí)聯(lián)過(guò)程節(jié)點(diǎn)負(fù)載分配示意圖

據(jù)此,可以得到歸一化衡量故障指標(biāo):設(shè)網(wǎng)絡(luò)中初始故障節(jié)點(diǎn)集合為Sf,級(jí)聯(lián)過(guò)程結(jié)束后的故障節(jié)點(diǎn)集合為φf(shuō),歸一化衡量故障規(guī)模的指標(biāo)計(jì)算公式為

(20)

CF越小,網(wǎng)絡(luò)的故障規(guī)模越小,即網(wǎng)絡(luò)抵抗攻擊的能力越好。

3.2 模型解析

為了更清楚地描述模型含義及模型與參數(shù)之間的關(guān)系,本文通過(guò)理論分析對(duì)模型進(jìn)行解析。

由式(19)知,如果節(jié)點(diǎn)vi故障,其鄰居節(jié)點(diǎn)vj從節(jié)點(diǎn)vi得到故障負(fù)載,與節(jié)點(diǎn)vj當(dāng)前負(fù)載之和大于節(jié)點(diǎn)vj的容量時(shí),節(jié)點(diǎn)vj故障即發(fā)生級(jí)聯(lián)故障。因此,當(dāng)滿足式(21):

Lj+ΔLj≤Cj

(21)

時(shí)級(jí)聯(lián)故障不會(huì)發(fā)生。

將式(18)代入(21)可得

(22)

由于節(jié)點(diǎn)的容量是由節(jié)點(diǎn)的初始負(fù)載線性表示,因此將式(16)代入式(22),可得

(23)

整理后可得

(24)

當(dāng)節(jié)點(diǎn)vj的初始負(fù)載Lj0=0時(shí),其容量Cj也為0,那么節(jié)點(diǎn)vj無(wú)意義且不參與級(jí)聯(lián)過(guò)程。因此本文僅考慮節(jié)點(diǎn)初始負(fù)載Lj0>0的情況。

由于Lj0>0,因此,式(24)兩邊同時(shí)除以Lj0,可得

(25)

整理得

(26)

整理可得

(27)

式(27)反映了兩個(gè)影響級(jí)聯(lián)過(guò)程的因素(容忍系數(shù)T和節(jié)點(diǎn)vi鄰居節(jié)點(diǎn)的初始負(fù)載)之間滿足的關(guān)系。隨著T增大,級(jí)聯(lián)現(xiàn)象減弱或消失;節(jié)點(diǎn)的初始負(fù)載的定義一定程度上也會(huì)影響級(jí)聯(lián)過(guò)程。

4 仿真分析

本節(jié)通過(guò)多個(gè)仿真及對(duì)比實(shí)驗(yàn),驗(yàn)證了本文提出的基于局部熵的初始負(fù)載定義的有效性。

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本文數(shù)據(jù)集的4個(gè)網(wǎng)絡(luò)均是無(wú)向無(wú)權(quán)的真實(shí)網(wǎng)絡(luò),具體信息來(lái)自網(wǎng)站http://konect.cc/和斯坦福數(shù)據(jù)庫(kù)。網(wǎng)絡(luò)結(jié)構(gòu)的詳細(xì)數(shù)據(jù)如表1所示。其中Jazz網(wǎng)絡(luò)是一個(gè)音樂(lè)家合作網(wǎng)絡(luò),每個(gè)節(jié)點(diǎn)代表一個(gè)音樂(lè)家,連邊表示兩個(gè)音樂(lè)家之間存在合作關(guān)系;Email網(wǎng)絡(luò)是一個(gè)郵件網(wǎng)絡(luò),每個(gè)節(jié)點(diǎn)代表一個(gè)人,連邊表示兩個(gè)人之間的通信關(guān)系;Hamsterster網(wǎng)絡(luò)是社交網(wǎng)站Hamsterster中用戶之間的關(guān)系網(wǎng)絡(luò);US.Power網(wǎng)絡(luò)是美國(guó)西部電力網(wǎng)絡(luò)。表中Nodes、Edges、AveDeg、MaxDeg、AveCluCo分別為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)連邊數(shù)、網(wǎng)絡(luò)平均度、網(wǎng)絡(luò)最大度、網(wǎng)絡(luò)平均集聚系數(shù)。

表1 實(shí)驗(yàn)網(wǎng)絡(luò)及其拓?fù)湫再|(zhì)

4.2 攻擊策略介紹

本文采用兩種類型的攻擊策略。

1)攻擊單個(gè)度最大的節(jié)點(diǎn),即選取網(wǎng)絡(luò)中度最大的節(jié)點(diǎn)作為初始故障節(jié)點(diǎn)并開始級(jí)聯(lián)過(guò)程。

2)時(shí)序攻擊是指從選擇的初始故障節(jié)點(diǎn)集合中,逐個(gè)攻擊。本文在時(shí)序攻擊的前提下,從度由大到小排序后的節(jié)點(diǎn)集合中選取10%數(shù)量的節(jié)點(diǎn)進(jìn)行攻擊。4.3節(jié)仿真結(jié)果表示,選擇網(wǎng)絡(luò)5～10%數(shù)量的節(jié)點(diǎn)進(jìn)行攻擊,能夠更加清楚地體現(xiàn)級(jí)聯(lián)過(guò)程。

4.3 仿真結(jié)果及分析

本文以Python為編程語(yǔ)言進(jìn)行仿真。

4.3.1 負(fù)荷系數(shù)α對(duì)網(wǎng)絡(luò)故障規(guī)模的影響

由于真實(shí)網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜多變,其度分布可能不服從冪率分布,因此本文利用Python軟件中的Networkx庫(kù),生成參數(shù)N=1 000,m=2的BA無(wú)標(biāo)度網(wǎng)絡(luò)進(jìn)行驗(yàn)證。進(jìn)行20次獨(dú)立仿真實(shí)驗(yàn),結(jié)果取平均值,仿真結(jié)果如圖2所示。

圖2 負(fù)荷系數(shù)α對(duì)級(jí)聯(lián)故障規(guī)模的影響

圖2中,在容忍系數(shù)T從0增大的過(guò)程中,隨著負(fù)荷系數(shù)α增大,網(wǎng)絡(luò)的故障規(guī)模逐漸增大,網(wǎng)絡(luò)抵抗蓄意攻擊的能力變差。文獻(xiàn)[20]認(rèn)為負(fù)荷系數(shù)α控制著網(wǎng)絡(luò)初始負(fù)荷的分布,α越大,初始負(fù)荷分布越不均勻,仿真結(jié)果也驗(yàn)證了這個(gè)結(jié)論。為了方便研究,本文在比較3個(gè)模型時(shí),取負(fù)荷系數(shù)α=1。

4.3.2 蓄意攻擊節(jié)點(diǎn)數(shù)量對(duì)級(jí)聯(lián)過(guò)程的影響

選擇蓄意攻擊節(jié)點(diǎn)的數(shù)量的多少對(duì)級(jí)聯(lián)過(guò)程有著不同的影響。以Jazz網(wǎng)絡(luò)為例,本文分別選擇該網(wǎng)絡(luò)中5%、10%、15%、30%數(shù)量的節(jié)點(diǎn)進(jìn)行攻擊,仿真結(jié)果如圖3。

圖3 不同數(shù)量蓄意攻擊節(jié)點(diǎn)的級(jí)聯(lián)故障

仿真結(jié)果表明:當(dāng)選擇蓄意攻擊的節(jié)點(diǎn)數(shù)目過(guò)多時(shí),3種級(jí)聯(lián)故障模型的區(qū)別將不再明顯。因此選擇網(wǎng)絡(luò)5%～10%數(shù)量的節(jié)點(diǎn)進(jìn)行攻擊,能更加清楚地對(duì)比3種模型的級(jí)聯(lián)故障規(guī)模。本文在對(duì)比實(shí)驗(yàn)中選擇網(wǎng)絡(luò)數(shù)量10%的蓄意攻擊節(jié)點(diǎn)。

4.3.3 不同節(jié)點(diǎn)的初始負(fù)載定義下級(jí)聯(lián)故障模型對(duì)比

本節(jié)分析3種不同節(jié)點(diǎn)初始負(fù)載定義的級(jí)聯(lián)故障模型在不同攻擊下的對(duì)比效果。

圖4是選擇單個(gè)度最大節(jié)點(diǎn)的攻擊策略時(shí)的對(duì)比結(jié)果。可以看出:在4個(gè)不同的網(wǎng)絡(luò)中,3種模型的網(wǎng)絡(luò)故障指標(biāo)CF,在隨著容忍系數(shù)T由0增大過(guò)程中,從最大值突變?yōu)樽钚≈?即級(jí)聯(lián)過(guò)程結(jié)束后,網(wǎng)絡(luò)中由全部節(jié)點(diǎn)失效轉(zhuǎn)變?yōu)闆](méi)有故障節(jié)點(diǎn)產(chǎn)生。仿真結(jié)果也體現(xiàn)了容忍系數(shù)的含義,當(dāng)容忍系數(shù)T越大,網(wǎng)絡(luò)中所有節(jié)點(diǎn)的容量越大。因此T在從0增大的過(guò)程中,有一臨界值Tc,當(dāng)T>Tc時(shí),面對(duì)初始攻擊,網(wǎng)絡(luò)中將不會(huì)出現(xiàn)級(jí)聯(lián)故障。同時(shí)從圖4中可以看出,基于節(jié)點(diǎn)局部熵定義初始負(fù)載的級(jí)聯(lián)故障模型,在容忍系數(shù)T更小時(shí),網(wǎng)絡(luò)中沒(méi)有故障節(jié)點(diǎn)出現(xiàn),即臨界值Tc最小。這說(shuō)明本文所提出的初始負(fù)載定義方式能夠以更小的代價(jià)提高網(wǎng)絡(luò)抵抗蓄意攻擊的能力。

圖4 攻擊單個(gè)度最大節(jié)點(diǎn)的級(jí)聯(lián)故障

圖5是時(shí)序的蓄意攻擊下的仿真結(jié)果。與圖4不同,圖5選擇了網(wǎng)絡(luò)中10%數(shù)量的初始失效節(jié)點(diǎn)數(shù)目,因此網(wǎng)絡(luò)故障指標(biāo)CF的值,在隨著容忍系數(shù)T由0增大的過(guò)程中,呈現(xiàn)遞減趨勢(shì)。比較3種模型,從圖5中可以看出,基于節(jié)點(diǎn)局部熵定義初始負(fù)載的級(jí)聯(lián)故障模型,網(wǎng)絡(luò)故障指標(biāo)CF的值在隨著容忍系數(shù)T增大的過(guò)程中,下降最快,并且在相同容忍系數(shù)T下,網(wǎng)絡(luò)級(jí)聯(lián)過(guò)程結(jié)束后的故障規(guī)模更小,同樣驗(yàn)證了本文提出的基于局部熵的初始負(fù)載定義的優(yōu)勢(shì)。

圖5 時(shí)序蓄意攻擊下的級(jí)聯(lián)故障

4.3.4 對(duì)式(27)的仿真驗(yàn)證

3.2節(jié)通過(guò)對(duì)模型的解析,我們得到級(jí)聯(lián)過(guò)程同攻擊節(jié)點(diǎn)的初始負(fù)載與其鄰居節(jié)點(diǎn)初始負(fù)載比值有關(guān),比值越小,級(jí)聯(lián)故障越不容易發(fā)生。本節(jié)計(jì)算了3種初始負(fù)載分配方式下攻擊網(wǎng)絡(luò)中度最大的節(jié)點(diǎn)的比值(見表2)。從表2中可以看出基于局部熵的級(jí)聯(lián)故障模型在4個(gè)網(wǎng)絡(luò)中的比值都最小,進(jìn)一步驗(yàn)證了本文提出的局部熵概念的有效性。

表2 度最大節(jié)點(diǎn)的初始負(fù)載與其鄰居初始負(fù)載之和的比值

4.3.5 與傳統(tǒng)WK模型的比較和改進(jìn)

文獻(xiàn)[21]在ML模型的基礎(chǔ)上提出了WK模型。兩種模型主要區(qū)別在于節(jié)點(diǎn)容量的分配方式。ML模型給每個(gè)節(jié)點(diǎn)相同的容忍系數(shù)T,使得每個(gè)節(jié)點(diǎn)容量大于其初始負(fù)載,這樣整個(gè)網(wǎng)絡(luò)的魯棒性能夠得到提高。然而現(xiàn)實(shí)生活中,節(jié)點(diǎn)容量的分配有一定的限制要求即成本是有限的。WK模型定義容量Ci=(1+T·θ(Li0/Lmax-β))·Li0,其中θ(x)是一個(gè)二值函數(shù)θ(x)=0(1),x<0(x>0)。在相同容忍系數(shù)T的情況下,影響節(jié)點(diǎn)容量大小的主要因素有兩點(diǎn):1)節(jié)點(diǎn)初始負(fù)載的大小;2)參數(shù)β的取值。節(jié)點(diǎn)初始負(fù)載值越大,β取值越小,則節(jié)點(diǎn)就會(huì)被分配額外的容量,當(dāng)β=0時(shí)WK模型退化為ML模型。因此,在容量成本有限制的情況下,WK模型更傾向于保護(hù)初始負(fù)載值更大的節(jié)點(diǎn),為此可能犧牲一部分網(wǎng)絡(luò)的魯棒性。

本文提出的局部熵模型在ML模型的基礎(chǔ)上對(duì)節(jié)點(diǎn)的初始負(fù)載進(jìn)行了新定義,而WK模型中節(jié)點(diǎn)初始負(fù)載為節(jié)點(diǎn)的介數(shù)。對(duì)于節(jié)點(diǎn)容量分配方式,本文采用與ML模型相同的分配方式。

受WK模型的啟發(fā),考慮到節(jié)點(diǎn)可分配的容量有限,在本文模型的基礎(chǔ)上采用WK模型中的節(jié)點(diǎn)容量分配方式,與原模型進(jìn)行對(duì)比仿真驗(yàn)證。以Email網(wǎng)絡(luò)和US.Power網(wǎng)絡(luò)為例,攻擊策略采用蓄意攻擊網(wǎng)絡(luò)中10%數(shù)量的節(jié)點(diǎn),仿真結(jié)果如圖6。

圖6 采用WK模型容量分配方式模型后的級(jí)聯(lián)故障對(duì)比

從圖6可以看出采用原模型的網(wǎng)絡(luò),抵抗蓄意攻擊的能力最強(qiáng)。采用WK模型的節(jié)點(diǎn)容量分配方式后,對(duì)于Email網(wǎng)絡(luò),當(dāng)β=0.28時(shí),網(wǎng)絡(luò)故障規(guī)模和原模型近似,此時(shí)網(wǎng)絡(luò)中有28個(gè)節(jié)點(diǎn)未被賦予額外的容量,即減少了成本,但犧牲了部分網(wǎng)絡(luò)的魯棒性。隨著β增大故障規(guī)模變大,網(wǎng)絡(luò)抵抗蓄意攻擊的能力變差。對(duì)于US.Power網(wǎng)絡(luò),當(dāng)β=0.55時(shí),與原模型得到的結(jié)果近似,此時(shí)網(wǎng)絡(luò)中44個(gè)節(jié)點(diǎn)未被賦予額外的容量。仿真結(jié)果表明,隨著網(wǎng)絡(luò)規(guī)模的增大,可以對(duì)更多的節(jié)點(diǎn)不賦予額外的容量,以減少更多的成本。在容量有限制的情況下,改進(jìn)后的局部熵級(jí)聯(lián)故障模型能夠以犧牲部分網(wǎng)絡(luò)魯棒性為代價(jià),從而減少成本,給予決策者更多的選擇。

5 結(jié)論

復(fù)雜網(wǎng)絡(luò)作為多學(xué)科交叉的新興學(xué)科,在網(wǎng)絡(luò)化、信息化、數(shù)據(jù)化的時(shí)代,備受研究者的關(guān)注。級(jí)聯(lián)故障作為復(fù)雜網(wǎng)絡(luò)的熱點(diǎn)研究領(lǐng)域,對(duì)我們的日常生活、電力安全等方面有著重要的意義。本文將圖熵的概念引入到級(jí)聯(lián)故障模型的節(jié)點(diǎn)初始負(fù)載的定義中,綜合考慮節(jié)點(diǎn)及其鄰居節(jié)點(diǎn)的信息,根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)的局部熵定義節(jié)點(diǎn)的初始負(fù)載。在面對(duì)兩種不同的蓄意攻擊時(shí),通過(guò)在多個(gè)真實(shí)網(wǎng)絡(luò)上對(duì)級(jí)聯(lián)故障模型進(jìn)行仿真分析,結(jié)果表明本文所提的基于局部熵的級(jí)聯(lián)故障模型的魯棒性更好,能夠以較小的成本抵抗蓄意攻擊。從圖熵的角度考慮,保護(hù)局部熵較大的節(jié)點(diǎn),也是一種較好的預(yù)防級(jí)聯(lián)故障的方式。