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

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

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

0 引言

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

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

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

1 基于度和介數的級聯故障初始負載定義

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

(1)

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

(2)

(3)

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

(4)

(5)

其中,α為負荷系數。

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

2 局部熵的相關定義

(6)

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

(7)

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

(8)

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

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

Ei=-pilogpi

(9)

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

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

(10)

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

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

(11)

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

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

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

(12)

(13)

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

(14)

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

3 基于局部熵的級聯故障初始負載定義

3.1 基于局部熵的級聯故障模型概念

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

Li0=LEα(vi,1)

(15)

其中,α為負荷系數。

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

Ci= (1 +T)Li0

(16)

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

Lj=Lj+ΔLj

(17)

(18)

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

Lj+ΔLj>Cj

(19)

圖1 級聯過程節點負載分配示意圖

據此,可以得到歸一化衡量故障指標:設網絡中初始故障節點集合為Sf,級聯過程結束后的故障節點集合為φf,歸一化衡量故障規模的指標計算公式為

(20)

CF越小,網絡的故障規模越小,即網絡抵抗攻擊的能力越好。

3.2 模型解析

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

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

Lj+ΔLj≤Cj

(21)

時級聯故障不會發生。

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

(22)

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

(23)

整理后可得

(24)

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

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

(25)

整理得

(26)

整理可得

(27)

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

4 仿真分析

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

4.1 實驗數據集

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

表1 實驗網絡及其拓撲性質

4.2 攻擊策略介紹

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

1)攻擊單個度最大的節點,即選取網絡中度最大的節點作為初始故障節點并開始級聯過程。

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

4.3 仿真結果及分析

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

4.3.1 負荷系數α對網絡故障規模的影響

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

圖2 負荷系數α對級聯故障規模的影響

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

4.3.2 蓄意攻擊節點數量對級聯過程的影響

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

圖3 不同數量蓄意攻擊節點的級聯故障

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

4.3.3 不同節點的初始負載定義下級聯故障模型對比

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

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

圖4 攻擊單個度最大節點的級聯故障

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

圖5 時序蓄意攻擊下的級聯故障

4.3.4 對式(27)的仿真驗證

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

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

4.3.5 與傳統WK模型的比較和改進

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

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

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

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

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

5 結論

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