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

董 昂,吳亞麗,任遠光,馮夢琦

(西安理工大學 a.自動化與信息工程學院;b.陜西省復雜系統(tǒng)控制與智能信息處理重點實驗室,西安 710048)

0 引言

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

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

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

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

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

(1)

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

(2)

(3)

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

(4)

(5)

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

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

2 局部熵的相關定義

(6)

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

(7)

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

(8)

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

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

Ei=-pilogpi

(9)

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

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

(10)

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

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

(11)

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

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

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

(12)

(13)

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

(14)

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

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

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

本文在定義節(jié)點的初始負載時,利用信息熵的概念定義了網(wǎng)絡中節(jié)點的1級局部熵,考慮了節(jié)點及其1層鄰居節(jié)點的拓撲信息。定義節(jié)點vi的初始負載為

Li0=LEα(vi,1)

(15)

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

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

Ci= (1 +T)Li0

(16)

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

Lj=Lj+ΔLj

(17)

(18)

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

Lj+ΔLj>Cj

(19)

圖1 級聯(lián)過程節(jié)點負載分配示意圖

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

(20)

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

3.2 模型解析

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

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

Lj+ΔLj≤Cj

(21)

時級聯(lián)故障不會發(fā)生。

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

(22)

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

(23)

整理后可得

(24)

當節(jié)點vj的初始負載Lj0=0時,其容量Cj也為0,那么節(jié)點vj無意義且不參與級聯(lián)過程。因此本文僅考慮節(jié)點初始負載Lj0>0的情況。

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

(25)

整理得

(26)

整理可得

(27)

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

4 仿真分析

本節(jié)通過多個仿真及對比實驗,驗證了本文提出的基于局部熵的初始負載定義的有效性。

4.1 實驗數(shù)據(jù)集

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

表1 實驗網(wǎng)絡及其拓撲性質

4.2 攻擊策略介紹

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

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

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

4.3 仿真結果及分析

本文以Python為編程語言進行仿真。

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

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

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

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

4.3.2 蓄意攻擊節(jié)點數(shù)量對級聯(lián)過程的影響

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

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

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

4.3.3 不同節(jié)點的初始負載定義下級聯(lián)故障模型對比

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

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

圖4 攻擊單個度最大節(jié)點的級聯(lián)故障

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

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

4.3.4 對式(27)的仿真驗證

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

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

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

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

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

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

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

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

5 結論

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