考慮節點負載的多社團網絡級聯失效問題研究

任林濤，裴忠民，熊 偉，羅章凱

航天工程大學 復雜電子系統仿真重點實驗室，北京 101416

近些年來，針對復雜網絡級聯失效問題,許多專家學者在各個領域開展了大量研究[1-4]。Motter等人[5]最先提出了一種基于介數定義節點初始負載的線性負載—容量（ML模型），得出網絡介數分布的差異性導致攻擊介數高的節點越容易導致級聯失效現象發生。段東立等人[6]針對的負載重分配規則是介于全局分配與最近鄰分配、均勻分配與極端非均勻分配的特點，提出了一種可調負載重分配范圍與負載重分配異質性的級聯失效模型。唐亮等人[7]考慮節點具有恢復和重復失效等特征，構建了故障節點概率傳播模式下的級聯失效模型。郝羽成等人[8]針對現實網絡中節點對負載的冗余能力，提出一種考慮節點過載狀態的復雜網絡級聯失效模型。Tian等人[9]根據控制節點在內的相依網絡之間節點負載依賴關系，提出了一種在相依網絡上基于節點負荷的級聯故障模型。

以上文獻都是從均勻網絡、無標度網絡結構或相依網絡等方向研究級聯失效問題，沒有考慮社團結構[10]對級聯失效作用的影響，而社團結構作為復雜網絡最普遍和最重要的拓撲結構屬性之一，廣泛存在于現實生活中[11-13]，其結構特征表現為社團內部節點連接緊密，社團間節點連接比較稀疏。研究社團網絡級聯失效問題，能更好地從社團網絡結構特征出發理解產生級聯失效的原因，對尋找提升網絡魯棒性方法有非常重要的意義。

Wu等人[14]采用節點度定義節點初始負荷，研究了具有社團結構的無標度網絡抗毀性，結論表明社團結構越明顯其越具有魯棒性。李浩敏等人[15]研究了多社團結構網絡的級聯失效問題，得出網絡的拓撲結構參數變化會影響網絡的抗毀性，但沒有具體研究不同攻擊策略對級聯失效的影響;陸靖橋等人[16]在經典的線性負載容量模型基礎上，有選擇地對社團邊界節點的容量附加二次容忍值，建立級聯故障抵制模型，但只選取了固定結構的電力社團網絡作為研究對象，沒有推廣到一般性質的社團網絡。

本文設計一種社團規模和社團結構可調的網絡結構模型，以節點度和介數共同定義節點初始負載，根據社團結構特征，對頭節點附加二次容忍負載，采用局部相鄰節點分配策略處理失效節點負載，提出初始負載、容忍負載、臨界負載三個階段節點失效模型。通過仿真分析了節點在遭受隨機攻擊和蓄意攻擊時，節點負載模型參數和多社團網絡結構對網絡魯棒性和級聯失效作用的影響。

1 多社團網絡生成模型

本文在文獻[17]的基礎上，提出一種社團規模和結構可調的多社團網絡模型，生成方法如下：

（1）初始網絡：設初始網絡有M個社團，將社團標記為C1,C2,…,CM。每個初始社團都是由m0(3≤m0)個節點組成的全連接網絡（當m0最小值為1和2時初始網絡無法區分出有效的社團結構）。同時為確保初始社團間的連通性（不產生孤立節點和孤立社團），設任意兩個社團間均有一條社團間連接邊。

（2）節點增長：在每一個時間間隔內新加入一個節點（也可以每一個時間間隔加入多個節點），新增加的節點則以概率ph進入社團Ch，則有當新增加節點確定進入社團Ch后，則需要選擇連接此社團內部m(1 ≤m≤m0)個節點，此時，新增加節點與Ch社團內的節點j相連的概率取決于節點j在Ch社團內度dhj所占本社團所有節點度的比例，即：

同時，新增加的節點以概率β進行社團間的連接（通過設置概率β可以控制社團間連邊的數量，進而調整多社團網絡的網絡結構）。文獻[17]中新增加節點與其他社團節點進行n次連邊操作，每一次連邊操作前都要依概率pt選擇連邊的社團Ct(t≠h)，再依照節點度分布的比例選擇社團Ct內某個節點進行連接；而本文則是先依概率pt選擇連邊的社團Ct，再在社團Ct內挑選n個不同節點進行連邊操作。這n個節點的選擇同樣取決于其占Ct社團所有節點度的比例，比例越大，越容易被選擇。通過上述與文獻[17]社團間連接的建模過程對比可以看出，本文建模的復雜度要相應低一些，而且n越大，復雜度差異就會變得更大。

以上多社團網絡的建模過程可以通過調節新節點加入社團的概率ph(h=1,2,…,M)來控制每個社團的規模。當ph=1/M時，即新節點進入每個社團的概率都相等，這樣最終生成的多社團網絡中每個社團的節點數量幾乎相等，此時生成的網絡就是均勻的，反之網絡就是非均勻的。另外，新節點進行社團間連接時，挑選連接社團時也是以概率ph(h=1,2,…,M)進行選擇的，也就是說某個社團節點數越多，越能吸引新節點加入。同時，與文獻[17]相比，本文在一個社團內挑選n個不同節點進行連邊，這樣更容易使節點數多的社團產生更多的社團間連接，而且規模越大且社團間連邊數越多的社團節點，越容易吸引其他社團節點與其進行連接。這樣的情形在真實網絡中較為常見，比如實力強的團隊越能吸引新人加入，同時還能加強與其他實力較強團隊的合作，實現強強聯合，這也說明了本文生成的多社團網絡更具一般性，與實際網絡更吻合。

設M=3,m=2,m0=3,p1=1/6,p2=1/3,p3=1/2,β=0.1,n=1,N=200。生成的多社團網絡拓撲圖和多社團網絡鄰接矩陣圖如圖1和圖2所示。

圖1 多社團網絡拓撲結構圖Fig.1 Multi-community network topology diagram

圖2 多社團網絡鄰接矩陣圖Fig.2 Multi-community network adjacency matrix

根據上述參數設置，取100次仿真結果平均值，得出多社團網絡拓撲結構參數如表1所示。

從表1得出，生成的多社團網絡平均路徑長度和網絡直徑與真實多社團網絡相比較小，具有“小世界效應”[18]，模塊度為0.56，說明網絡的社團化特征明顯[19]。同時，生成網絡頭節點個數占節點總數的比例為17.9%，產生的社團間連接數比社團內部連接數小得多。

表1 多社團網絡拓撲結構參數Table 1 Multi-community network topology parameters

2 節點負載評估模型

2.1 節點負載相關定義

Motter等人提出的ML模型中，定義節點i的容量C(i)與初始負載l(i)存在線性關系，即C(i)=(1+α)l(i)，α表示為容量調節參數。這種定義由于簡單通用性強而被大多數學者所采用。但是隨著研究的不斷深入，Kim等人[20]通過研究電力網、航空網、交通網等現實中的網絡，發現網絡中具有較小負載的節點反而擁有較大的空閑容量，即在大多數網絡中，節點的容量與負載并非呈簡單的線性關系。為體現這種非線性關系，陸靖橋、丁超等人[21]以及其他許多學者在其研究中都相應地給初始負載l(i)中添加了指數調節參數，來控制初始負載的強度。

在描述節點屬性的參數中，節點度、介數[10]是其中最重要的兩個。由前文生成的多社團網絡的靜態參數可知，網絡中只有少部分節點度具有較高的值，大部分節點度值都比較小，因此只選用度作為節點負載區分度不高。從全局刻畫節點重要性的另一個重要指標是介數，但本文經過仿真后發現有個別節點的介數為0，這是因為這些節點都是處于整個網絡的邊緣，其他節點之間的最短路徑都不經過這些節點，因此本文選擇用度和介數共同來定義節點的初始負載參數，本文將節點的初始負載定義為：

d(i)為第i個節點的度，B(i)為第i個節點的介數，a、b分別為節點度和介數的倍數參數。由于節點度在數值上遠小于節點的介數，為了使度和介數能夠調整到同一數量級，使得能用度和介數共同反映節點初始負載，本文用θ作為節點介數的指數調節參數。

頭節點作為多社團網絡節點之間交互的樞紐，是保持網絡結構完整性最重要的節點，因此在社團內節點的負載保持不變的情況下，可以通過對頭節點附加二次容忍負載值，來研究頭節點對網絡結構的影響。

Γm為節點i與其他社團頭節點連接的集合。表示與節點i連接的其他社團頭節點初始負載之和。p為附加的二次負載調節參數，且0≤p≤1。節點若該節點不是頭節點時，p=0,W(i)退化為ML模型。

對于復雜網絡中的節點而言，本身就具有正常運行時能夠承受的負載，假定在節點承受負載范圍內運行就不會失效，本文將這個不會發生失效的負載上限定義為容忍負載R。

λ為節點容忍負載系數，λ≥0。

在諸多實際網絡中，節點超過容忍負載運行時，一般都不會立即失效，反而能在此狀態下維持一段時間，此時人們會采取多種措施確保整個網絡能夠正常運轉，若是采取措施不及時或者節點一直在容忍負載高位運行，就有可能導致節點失效，本文把節點失效的閾值稱為臨界負載L。

式中，k表示臨界負載系數，k≥0。

2.2 失效節點負載重分配策略和流程

失效節點負載重分配策略可以分為兩類[22]：一種是基于全局搜索的分配策略，這種策略計算復雜度高，需要大量時間進行遍歷；另一種是基于局部搜索的策略，這種分配策略是將失效節點的負荷按照一定的規則分配給與失效節點相連的節點，該方法計算復雜度低。作為社團網絡，節點在社團內部連接緊密，在社團間節點連接稀疏，失效節點負載大概率分配給同社團的其他節點，因此本文采用負載局部重分配策略。

當一個社團網失效節點數量超過一定比例時，失效節點的負載才開始向其他社團的節點進行分配，本文將這個比例稱作轉移比z。通過設置轉移比z能夠約束和調控失效節點負載在社團內和社團間的分配過程，這樣更有利于研究級聯失效作用對多社團網絡魯棒性的影響。

圖3 節點失效后社團內負載重分配圖Fig.3 Load redistribution diagram within and between communities after node failure

通過上述具體分配過程，總結出任意節點失效后負載重分配流程如下：

對集合ΓNid內所有節點的負載進行判斷，若有節點負載大于臨界負載，則該節點失效。

（4）對新的失效節點重復上述（1）～（3）中的分配過程，直到整個多社團網絡再無失效節點為止。

2.3 節點失效判定標準

根據初始負載、容忍負載和臨界負載的定義以及負載重分配策略，可以推導出任意一個節點在三個階段內運行時失效的概率分布pt(i)為：

現有的大多數ML改進模型中，判定節點失效標準相對簡單化，即當節點i實際負載小于其容量C(i)時，節點正常運行，反之節點失效。而本文添加了容忍負載和臨界負載兩個判斷閾值，當節點i在容忍負載以下運行時，節點就不會失效。節點超過容忍負載運行時，自身負載越靠近臨界負載，失效的概率就越高。當節點自身負載超過臨界負載時，節點就立即失效。而節點負載處于這兩個閾值之間時，相當于實際網絡中節點可以過載運行一樣。顯然本文的設定更加貼合實際網絡中節點在運行時可能出現的情況。

當網絡在遭受攻擊時節點被摧毀，網絡內其他節點由于級聯效應部分可能處于容忍負載狀態或直接失效，失效的節點越少，網絡的魯棒性越好。本文定義失效節點數量與節點總數的比值稱為失效比E，用失效比作為評估網絡魯棒性的標準。

其中，e表示失效節點的數量，N為節點總數量。

3 仿真分析

本文分別從節點負載模型參數和多社團網絡結構兩方面研究網絡的級聯失效問題。攻擊策略為蓄意攻擊初始負載最大的節點，隨機攻擊任意一個節點。為不失一般性，令a,b=1。

3.1 節點負載模型參數對級聯失效作用的影響

設置網絡生成參數為M=3,m=3,m0=3,p1=1/6,p2=1/3,p3=1/2,β=0.1,n=1,N=200，為避免偶然性，每次生成網絡100個，每個網絡仿真100次，仿真結果取平均值。

（1）介數調節參數θ

本文采用控制變量法，首先研究介數調節參數θ對級聯失效作用的影響。設二次容忍負載參數p=0.5,轉移比z=0.5,容忍負載參數λ=0.2,θ=[0.1,0.3,0.5,0.7]，k=[0,2]。經過仿真，失效比E隨臨界負載參數k的變化趨勢如圖5和圖6所示。

圖5 蓄意攻擊不同θ值時的E～k曲線Fig.5 Deliberately attacking E～k curve with differentθvalues

圖6 隨機攻擊不同θ值時的E～k曲線Fig.6 Random attacking E～k curve with differentθvalues

從圖5可以看出，失效比E隨臨界負載參數k的增加而減小。蓄意攻擊時，在同一k值下θ值越小，失效比E越小，說明網絡越具有魯棒性，這是因為θ值越小，調整后的介數就越小，導致整個網絡所有節點初始節點負載就越小，而且使節點初始負載相互之間的差值越接近，即初始負載分布越均勻，因此面對蓄意攻擊更具有魯棒性，這與文獻[23]結論類似。另外，對于不同的θ值都有相應的臨界閾值k1和k2（圖4中，所有θ值的E～k曲線在k=2處均已平穩且趨向為0，故臨界閾值k2必存在于k＞2的某處）。當k＜k1時E≈1，級聯效應導致所有節點都失效。當k＞k2時E≈0，一個失效節點無法引起級聯失效，這同樣與文獻[23]的結論相似。

圖4 節點失效后社團間負載重分配圖（轉移比z=0.5）Fig.4 Load redistribution diagram between communities after node failure（Transfer ratio z=0.5）

圖6中，在隨機攻擊時，在參數k相同的情況下，不同θ值對應的失效比E幾乎都相同，這是因為雖然θ值變化會引起節點初始負載的變化，但每一次隨機選擇到負載最大的節點概率只有0.5%。同時可以看出，在同一k值下，隨機攻擊比蓄意攻擊失效比要小很多，說明網絡在蓄意攻擊時比在隨意攻擊時脆弱很多。

（2）二次容忍負載參數p

設置p=[0,0.25,0.5,0.75]，k=[0,2]，θ=0.5，z=0.5，λ=0.2。失效比E隨臨界負載參數k的變化趨勢如圖7和圖8所示。

圖7 蓄意攻擊不同p值時的E～k曲線Fig.7 Deliberately attacking E～k curve with different p values

圖8 隨機蓄意攻擊不同p值時的E～k曲線Fig.8 Random attacking E～k curve with different p values

從圖7可以看出，蓄意攻擊時，在0.1＜k＜1.5范圍內，沒有設置二次容忍負載的網絡要比設置了二次負載的網絡更加魯棒，這是因為設置了二次負載的頭節點的初始負載增大了許多，當這些頭節點遭受攻擊失效或者級聯失效，過大的負載值分配給鄰居節點，更容易引起鄰居節點的失效，造成更加嚴重的級聯失效問題。從圖8可以看出，在隨機攻擊時，設置二次負載的網絡在0＜k＜0.5的范圍內要比未設置的網絡的魯棒性稍好一些，但幅度有限。因此得出為頭節點設置二次容忍負載值的網絡，面對攻擊的總體魯棒性要低于未設置的網絡，這也從側面說明了頭節點在多社團網絡中所處的位置很重要。

（3）轉移比z

設置z=[0,0.25,0.5,0.75]，k=[0,2]，θ=0.5，p=0.5，λ=0.2。仿真結果如圖9和圖10所示。

圖9中，蓄意攻擊時沒有設置轉移比z的網絡在k=[0,2]的范圍內，失效節點數量都低于設置了轉移比z的網絡，說明后者魯棒性要遠高于前者，當z＞0時，在k=[0,0.8]范圍內，由于級聯失效導致整個網絡節點全部失效。這是因為節點失效時，初期將級聯失效規模控制在本社團，而后將這些失效節點的負載向社團間轉移，這些失效節點的級聯失效作用會“引爆”整個網絡。從圖10看出，設置和未設置轉移比的網絡，在面對隨機攻擊時，失效比曲線在k=[0,2]范圍內幾乎相同，僅在k＜0.2的初始范圍內，設置轉移比的網絡能減少失效節點在整個網絡引起的級聯失效作用。因此，將級聯失效控制在社團內部，不利于網絡的魯棒性。

圖9 蓄意攻擊不同z值時的E～k曲線Fig.9 Deliberately attacking E～k curve with different z values

圖10 隨機蓄意攻擊不同z值時的E～k曲線Fig.10 Random attacking E～k curve with different z values

（4）容忍負載λ

設置λ=[0,0.1,0.2,0.3]，k=[0,2]，θ=0.5，p=0.5，z=0.5。仿真結果如圖11和圖12所示。

圖11 蓄意攻擊不同λ值時的E～k曲線Fig.11 Deliberately attacking E～k curve with differentλvalues

從圖11和圖12可以看出，蓄意攻擊和隨意攻擊在參數λ=0和k=0時，即容忍負載和臨界負載都等于0時，節點無法判斷是否失效。同時在同一個k值下，λ值越大，網絡就越魯棒，λ值越小，網絡就越脆弱。這是因為容忍負載升高，節點超容忍負載運行的概率就會相應降低，即節點肯定不會失效的概率升高。當節點i超過容忍負載運行時，根據公式（8）可以推導出此時失效的概率pt為：

圖12 隨機蓄意攻擊不同λ值時的E～k曲線Fig.12 Random attacking E～k curve with differentλvalues

其中，W′(i)表示節點i實際負載，W(i)表示節點初始負載。從公式（10）可以看出，若初始負載W(i)和W′(i)固定，節點失效概率pt與λ和k呈負相關，即λ和k值越大，節點失效概率就越小，E值也就越小，這與圖11和圖12仿真結果相吻合。

從圖12中可以看出，不同值曲線的區分度要比其他參數的曲線（圖6、8、10）高很多，這是因為參數作為判斷節點是否失效的一個標準，同等大小間隔的敏感度要比其他參數高很多，同時值變化也會引起處在容忍負載和臨界負載之間的節點失效的概率，影響失效節點數同樣比其他參數高很多。

3.2 多社團網絡結構對級聯失效作用的影響

從本文生成多社團網絡的參數可以看出，影響網絡結構的參數主要是m和β（本文默認n=1）。設置節點負載模型參數為θ=0.5,p=0.5,z=0.5,λ=0.2,k=[0,2],仿真結果同樣取100次仿真平均值。

（1）社團內部連接數m

同樣采用控制變量法，設置網絡生成參數為M=3,m0=3,p1=1/6,p2=1/3,p3=1/2,β=0.1,n=1,N=200,m=[1,2,3],k=[0,2]。仿真結果如圖13和圖14所示。

從圖13和圖14可以看出，蓄意攻擊和隨機攻擊時，社團內部節點連接數m越大，網絡越脆弱。這是因為雖然社團內部節點連接數增加了，但度大的節點連接更多的新節點，會使初始負載變得更大，而負載小的節點幾乎無變化，形成“馬太效應”，使得社團內部結構無標度化，因此整個網絡在面對攻擊時越脆弱[1]。另外，當m=1時，隨機攻擊后網絡節本無失效節點，這是因為此時網絡的平均聚類系數為0.013 3，社團內節點之間連接程度非常低，網絡無法引起級聯失效反應。

圖13 蓄意攻擊不同m值時的E～k曲線Fig.13 Deliberately attacking E～k curve with different m values

圖14 隨機蓄意攻擊不同m值時的E～k曲線Fig.14 Random attacking E～k curve with different m values

（2）社團間連接概率β

設置網絡生成參數為M=3,m=2,m0=3,p1=1/6,p2=1/3,p3=1/2,n=1,N=200,β=[0.1,0.5,0.9],k=[0,2]。仿真結果如圖15和圖16所示。

圖15 蓄意攻擊不同β值時的E～k曲線Fig.15 Deliberately attacking E～k curve with differentβvalues

圖16 隨機蓄意攻擊不同β值時的E～k曲線Fig.16 Random attacking E～k curve with differentβvalues

從圖15和16可以看出，增加社團間連接概率，在蓄意攻擊和隨機攻擊時，網絡會越脆弱。β值越高，產生的社團間連接數越多，雖然會使社團間的耦合強度增大，但也會使網絡中頭節點的數目增加，經過仿真計算，β=0.1時，平均頭節點個數為35個，β=0.5時為121個，β=0.9時為185個。頭節點數量增加導致整個網絡的平均路徑長度變短，平均度增加，平均介數也相應增加，導致節點初始負載增大，在臨界負載相對較小時，網絡容易引發嚴重的級聯失效反應，因此不利于網絡的魯棒性。

4 結束語

本文提出一種社團規模和社團結構可調的網絡結構模型，以節點度和介數共同定義節點初始負載，根據社團結構特征，對頭節點附加二次容忍負載，采用局部相鄰節點分配策略處理失效節點負載，同時提出初始負載、容忍負載、臨界負載三個階段節點失效模型。通過對多社團網絡級聯失效問題進行了研究，得出結論為：（1）相同參數設置下，隨機攻擊時多社團網絡魯棒，蓄意攻擊時多社團網絡脆弱。（2）在蓄意攻擊時，初始節點負載越高，網絡越脆弱，越容易引起網絡級聯失效。（3）給頭節點添加二次負載，蓄意攻擊時會成為“爆發點”，引起嚴重的級聯失效反應。（4）將失效節點負載分配控制在一個社團，越容易引發級聯失效反應。（5）設置容忍負載和臨界負載兩階段節點負載上限能有效提升網絡魯棒性。（6）社團內節點連接越均勻，網絡越魯棒。（7）社團間連接應選擇初始負載較低的節點進行連接，以提高魯棒性。