基于最大連通子圖相對效能的相依網絡魯棒性分析

趙 娜，柴焰明，尹春林，楊 政，王 劍，蘇 適

(1. 云南大學軟件學院 昆明 650091；2. 云南大學軟件學院軟件工程重點實驗室 昆明 650091；3. 云南電網有限責任公司電力科學研究院 昆明 650217；4. 昆明理工大學信息工程與自動化學院 昆明 650504)

隨著社會和科技的發展，現實中各事物的聯系越來越多，這些聯系都可以用網絡系統來描述。隨著這些關系變得錯綜復雜，逐漸產生了兩個甚至多個系統之間的聯系，形成相互依存網絡。為衡量相互依存網絡在級聯失效過程中的魯棒性，需要一個能準確衡量魯棒性的測度指標。目前大部分網絡魯棒性研究都直接采用攻擊后最大連通子圖比例作為魯棒性指標，該指標雖能較合理反映網絡魯棒性，但在實際應用時也因適用性和準確性的問題而常被詬病。此外，目前大多數魯棒性指標都是針對單一網絡，專門針對相互依存網絡魯棒性評價指標的探討卻較少。因此，有必要對常用魯棒性指標進行準確性和適用性的探討，并對相互依存網絡的特點進行分析，提出新的相互依存網絡魯棒性指標。

本文對幾個常用的具有代表性的魯棒性指標進行分析，針對一般相依網絡級聯失效過程，提出了最大連通子圖相對效能比的魯棒性度量指標。通過相互依存網絡級聯失效模型的攻擊實驗表明，相比于現有常用指標，該指標能更準確地衡量相依網絡在級聯失效過程中的魯棒性變化，在大規模的網絡中具有明顯優勢，可適用于相依網絡中基于仿真的魯棒性分析。

1 研究現狀

復雜網絡的魯棒性研究最初起源于2000年。文獻[1]最先提出以最大連通子圖和平均最短距離作為魯棒性指標對復雜網絡的魯棒性進行研究，在國內外引起了廣泛關注。目前大部分的文獻都采用最大連通子圖及其變形來度量網絡的魯棒性(如網絡攻擊前后最大連通子圖規模比例、連通子圖個數等)，并且以網絡的攻擊實驗作為研究魯棒性的主要方式。文獻[2]從網絡構建的角度，提出用自然連通度作為魯棒性指標來分析使用不同方式給網絡增邊后對魯棒性的影響。文獻[3]將自然連通度指標放入網絡攻擊實驗中進行了驗證。文獻[4]對自然連通度做了優化，提出基于禁忌搜索以及網絡效率權衡優化模型的方法優化網絡魯棒性。文獻[5]提出了一種提高復雜網絡結構魯棒性方法，使用連通度、失效節點比例、網絡效率等多個魯棒性度量指標，并在車載自組織網絡中進行應用分析。文獻[6]基于MapReduce框架的網絡，給出了連通率和效率比兩個魯棒性指標觀測不同攻擊策略下網絡的魯棒性。文獻[7]從點韌性度的角度設計了一個基于粒子群的網絡魯棒性計算的改進算法。文獻[8]從攻擊方式的角度提出了介度熵魯棒性度量方法，驗證了介度中心性的攻擊方式優于傳統攻擊方式。文獻[9]則以圖熵的角度構建介度熵指標，依據馮諾依曼熵提出了子圖信息熵和H信息熵的魯棒性指標。文獻[10]就譜圖論，采用Kirchhoff指數衡量網絡魯棒性以尋找并獲取網絡中較為穩定的邊界。

相依網絡魯棒性研究最早開始于2010年。文獻[11]基于滲流理論構建了級聯故障滲流模型，并對相依網絡魯棒性進行了研究。文獻[12]使用小世界網絡、隨機網絡和無標度網絡，研究了由不同類型網絡構成的相依網絡在目標攻擊和隨機攻擊下的魯棒性。文獻[13]指出相依網絡中網絡間的相依方式有同配相依(度數相近)、異配相依(度數相差較大)、隨機相依3種，并使用BA-BA相依網絡模型研究不同相依方式下耦合強度對網絡魯棒性能的影響。文獻[14]就相依網絡中出現的級聯失效現象，構建了基于負載重分配的級聯失效模型，以相依邊的負載作為耦合強度來探究耦合強度對網絡魯棒性的影響，發現魯棒性與耦合強度并非單調性關系。文獻[15]改進了傳統負載級聯失效模型，重新定義了節點失效條件，并使用介數作為網絡相依方式的界定因素，進而發現魯棒性與網絡間相依方式、耦合強度和重要節點密切相關，且影響程度不同。文獻[16]綜合了以上研究結果，在基于負載的相依網絡魯棒性研究中，將相依方式整理為7種，其中包括從度相關和介數相關來構建同配異配相依方式，甚至是度和介數混合相依，同時將節點初始負載定義為在度相關和介數相關之間可線性變換的方式。文獻[17]針對異質弱相依的相依網絡進行魯棒性研究，其中考慮到節點失效后其相依節點的所有連接邊不會全部失效，而是以一個概率失效，且每個邊失效的概率也不同，研究得出網絡魯棒性與網絡異質程度正相關。文獻[18]研究了多重非對稱相依網絡的魯棒性，發現在該網絡模型中，具有多重相依關系的層會存在混合相變，而沒有多重相依關系的另一層只出現一階相變。

縱觀以上研究可以發現，以上研究所采用的魯棒性指標幾乎都是最大連通子圖比例及其變形，且已有的對魯棒性指標的討論也都是針對單一網絡，而針對相依網絡魯棒性指標的討論很少。此外，在相依網絡研究中，大部分都過于依賴單一網絡的思想，導致魯棒性指標也采用單一網絡的指標而沒有考慮其在相依網絡中的適用性。因此，本文針對一般相依網絡級聯失效過程，提出了新的魯棒性度量指標，目的在于使魯棒性指標更好地適用于相依網絡且具有較高準確性。

2 相依網絡的級聯失效模型

2.1 相依網絡的構建

為了使研究更具代表性，同時降低研究的復雜性，本文只考慮由兩個網絡構成的相依網絡，且根據一對一相依關系來構建相依網絡模型。

根據復雜網絡理論，相依網絡一般用基于圖論的數學模型來表示[16]。單個網絡用圖G(V,E)來表示，其中V是圖中所有節點的集合，E是圖中所有邊的集合。對于兩層相依網絡，其子網絡分為網絡A和網絡B，分別記為GA(VA,EA)和GB(VB,EB)。為了描述相依網絡中網絡間的相依關系，需額外構建矩陣來表示網絡間節點相依邊的鄰接矩陣。則相依網絡可以表示為GAB(GA,GB,EAB,EBA)，其中EAB、EBA是網絡A與網絡B之間相依關系的鄰接矩陣，設兩個網絡的節點數分別為NA=m,NB=n，則以EAB為 例可表示為規模m×n的矩陣：

式中，ei,j表示網絡A中節點i與網絡B中節點j的相依關系，若存在相依關系，ei,j=1，否則ei,j=0。

2.2 級聯失效模型的構建

級聯失效是復雜網絡中的一種典型的故障傳播模式。網絡中，在一個或部分節點因故障失效后，會通過相依關系使相依節點發生失效，進而引發其他節點接連失效，產生級聯效應，最終導致網絡大面積崩潰甚至完全崩潰。本文采用一般相依網絡級聯故障模型，根據此模型可以得出節點失效的情況如下：1) 節點受到隨機或蓄意的直接攻擊影響而失效；2) 一個節點的失效導致與其相依的節點失去了相依關系而失效；3) 隨著節點的失效導致網絡中一些節點脫離了最大連通子圖，失去了與網絡大部分節點的聯系，導致這些節點即使沒有被直接攻擊也會失效。

相依網絡級聯失效過程如下：

1) 攻擊相依網絡中的一個或一定比例的節點，由于網絡的相依性，與該節點相依的節點也會失效(之后任何節點失效時都伴隨其相依節點失效)。

2) 檢查剩余網絡，如果有節點脫離了最大連通子圖，該節點也視為失效。

3) 如果在步驟2)中有節點失效，則重復步驟2)，否則級聯失效結束。

上述過程如圖1所示，其中，相依網絡由網絡A和網絡B構成。假設對節點A5進行攻擊，使A5失效，從網絡A中移除與A5相連的邊，則與其相依的節點B5因失去了相依關系而失效，從網絡B中移除與B5相連的連接邊，此時網絡達到階段1的狀態。隨后，隨著A5的失效，節點A6脫離了網絡A的最大連通分量成為孤立節點，導致其與其他節點失去聯系而失效，對應地其相依節點B6失效。同理節點B4成為孤立節點而失效，其相依節點A4失效。經過以上級聯失效后最終形成階段2的穩定狀態。

圖1 相依網絡級聯失效過程

3 相互依存網絡魯棒性指標構建

在基于仿真的魯棒性分析中，網絡在受到攻擊后，主要關注的是其拓撲結構和連通性的變化。當前研究中最常用的最大連通子圖比例和網絡效能比指標也是基于這一思想。本文針對相依網絡，在最大連通子圖比例和網絡效能比的基礎上，考慮相依網絡每個子網絡在攻擊前后相對于整個網絡的連通性，提出了新的基于最大連通子圖相對效能比的相互依存網絡魯棒性指標，來衡量相依網絡級聯失效過程中網絡魯棒性變化狀況。

3.1 常用魯棒性指標定義

定義1 攻擊后網絡最大連通子圖比例F

攻擊后網絡最大連通子圖比例是目前復雜網絡魯棒性研究中最常用的指標，指攻擊后網絡中最大連通子圖的節點數量與整個網絡中全部節點數量的比值：

式中，N′表示網絡受攻擊后最大連通子圖中的剩余節點數量；N表示整個網絡中全部節點的數量。該指標反映了網絡遭受攻擊后的拓撲結構的變化。

定義2 網絡效能比EM

網絡效能是一個量化節點間連通性和通信效率的魯棒性指標，為網絡中任意兩個節點間最短路徑距離的倒數的平均值。由于節點間最短路徑又稱為測地線，因此網絡效能也可以稱為反測地線距離[7]。對網絡效能E的定義如下：

式中，Ei和Ec分別為攻擊前和攻擊后的網絡效率。按照性質可知，網絡效能比EM越大，則網絡魯棒性越好。

3.2 最大連通子圖相對效能比

級聯失效過程中，網絡中任意節點在失效時，并非將該節點從網絡中完全移除，而是使其失去所有連接邊，以孤立節點的形式存在于網絡中。根據這一點可知，設N表示整個網絡中全部節點的數量，N′表示網絡受攻擊后最大連通子圖中的節點數量，則網絡在攻擊前后N是不變的，而N′逐漸減少，若攻擊后網絡完全崩潰，則網絡中所有節點均為孤立節點，不存在最大連通子圖，即N′=0。根據級聯失效模型和滲流理論可知，只有當節點在最大連通子圖中時，才能夠保持正常運作，而節點脫離了最大連通子圖時，會因失去與網絡大部分節點的聯系而失去正常工作的能力導致失效[16]。而網絡效能始終以整個網絡的角度來衡量網絡的連通性，這會將已經失效的孤立節點也一并納入衡量，無法準確得知最大連通子圖在級聯失效過程中的變化情況。因此，本文結合級聯失效過程中網絡全局和最大連通子圖的變化情況，給出最大連通子圖相對效能LRE (largest-component relative efficiency)的定義，并進一步提出最大連通子圖相對效能比LREM(largest-component relative efficiency measurementratio)。

對于一個網絡n中的最大連通子圖，其網絡效能E′表示為：

和網絡效能同理，為了對比攻擊前后的效果，對LRE進行歸一化處理，形成最大連通子圖相對效能比LREM指標，按以下公式計算：

式中， LREi和 LREc分別為攻擊前和攻擊后的LRE值。與EM同理，LREM越大，表示網絡魯棒性就越強。

4 仿真分析

本文在相依網絡上進行級聯失效模型仿真，通過觀察在不同的相依網絡上各魯棒性指標的表現，來驗證這些指標在相依網絡中的魯棒性度量是否合理且準確。

4.1 仿真實驗設定

為了使實驗更具代表性和直觀性，本文參照現實中常用的復雜網絡結構，設定仿真實驗構建的相依網絡模型由BA無標度網絡模型和WS小世界網絡模型兩兩相互連接構建而成，構成BA-BA、BAWS、WS-WS相依網絡模型，其中BA無標度網絡模型是參照文獻[19]提出的無標度網絡演化算法構建的網絡模型，WS小世界網絡模型則是遵循文獻[20]提出的小世界網絡演化算法來構建的模型。設定每個子網絡規模N=1000，BA網絡遵循BA(N,m=2)， WS網 絡 遵 循 WS(N,K=4,p=0.5)，則顯然對于相依網絡，平均度 〈k〉=4。兩個網絡間的相依方式為按照度數差的大小添加相依邊，分為同配相依(AL)、隨機相依(RL)和異配相依(DL)3種相依方式。相應地，攻擊方式采用全網高度數蓄意攻擊方式，從整個網絡中攻擊度數最高的數量比例為p的節點，并規定一個完全崩潰閾值pc為使網絡恰好完全崩潰時的p值。攻擊全過程遵循2.2節中所述級聯失效模型。所有實驗結果均為實驗20次后取平均值，進行對比的魯棒性指標分別為網絡最大連通子圖比例F、網絡效能比EM和最大連通子圖相對效能比LREM。

4.2 仿真結果分析

圖2為BA-BA相依網絡模型下攻擊比例為p的節點各魯棒性指標的變化情況。可以看出，在高度數蓄意攻擊下，整個網絡會顯得非常脆弱。最壞的情況為在相依方式為異配相依，攻擊比例p=0.3左右時網絡就完全崩潰(F=0)，即pc≈0.3。而同配相依的pc≈0.46時網絡才會完全崩潰，隨機相依則介于同配相依與異配相依之間。結合F指標可得出，BA-BA相依網絡在全網蓄意攻擊下，同配相依時魯棒性最好，異配相依時魯棒性最差。根據BA無標度網絡的網絡特性，每個節點更傾向于與度數大的節點相連接，則網絡中度數大的節點會凝聚在一起。另外，魯棒性指標EM和LREM的表現與F相似，隨著p的增加，EM和LREM都在逐漸減小，最終網絡完全崩潰時，EM=LREM=0。網絡破壞程度較小時，相比F，LREM減小最快，EM其次，且它們的值明顯比F小，即LREM＜EM＜F，這說明網絡中從LREM體現的魯棒性比F和EM更弱；而在網絡接近崩潰時，EM和LREM基本接近于0，此時減小幅度放緩，但存在一個pm值 (pm＜pc)，使得當p∈(pm,pc)時LREM會略微大于EM。這是因為EM是面向相依網絡整體進行計算，而LREM是對相依網絡中每個子網絡的最大連通子圖進行計算并取平均值，則在網絡節點數較少時，相依網絡整體的效能要低于每個子網絡的平均效能。因此可以看出，相比F和EM，LREM對網絡的魯棒性的變化更加敏感，并在規模較大的網絡中對魯棒性的衡量具有較大優勢。

圖2 BA-BA相依網絡蓄意攻擊下的魯棒性

圖3為BA-WS相依網絡模型下攻擊比例為p的節點各魯棒性指標的變化情況。可以看出，3種相依方式體現的魯棒性在p＜0.1時幾乎相同，但在p＞0.1以后發生分歧，和BA-BA網絡同樣表現為同配相依時魯棒性最好(pc≈0.6)，異配相依時魯棒性最差(pc≈0.4)。此外，3個指標的表現與BA-BA網絡的基本相同，區別在于EM和LREM的差距較小。WS網絡的度分布較為均勻，沒有度數明顯高的節點，因此在全網高度數蓄意攻擊下容易先從BA網絡攻擊。同理，BA網絡在大規模的蓄意攻擊下，相依網絡會迅速崩潰，但由于WS網絡的存在使得網絡的崩潰程度不及BA-BA網絡。

圖3 BA-WS相依網絡蓄意攻擊下的魯棒性

圖4為WS-WS相依網絡模型下攻擊比例為p的節點各魯棒性指標的變化情況。可以看到，無論哪種相依方式都有pc＞0.8，即網絡完全崩潰的攻擊比例都在0.8以上。由于相依網絡中不含有BA無標度網絡，所以相較于含有BA網絡的相依網絡來說，無論什么相依方式都比上述兩種類型的相依網絡模型抵御蓄意攻擊而產生的級聯故障的能力要強。這說明了WS-WS相依網絡模型具有很強的魯棒性，同時體現了WS小世界網絡抵御蓄意攻擊能力較強的特性。從指標來看，在WS-WS網絡下，LREM的表現與之前相比發生了變化，在網絡破壞程度較小時有LREM的值大于EM的情況出現。再結合圖2和圖3的結果，可以看出，在較為脆弱的網絡中，LREM對魯棒性的反映比EM更小，在較為健壯的網絡中則更大。這并不意味著LREM的敏感性在較為健壯的網絡中不如EM，而是說明LREM能更細致地凸顯網絡魯棒性的強弱程度，也能看出LREM更加敏感。

圖4 WS-WS相依網絡蓄意攻擊下的魯棒性

綜合以上結果可以得出，在全網蓄意攻擊下，含有BA無標度網絡的相依網絡的抵抗能力會減弱，同時同配相依時魯棒性較好，異配相依時魯棒性較差。在指標的表現上，本文提出的最大連通子圖相對效能比LREM能夠正確反映相依網絡在級聯失效過程中的魯棒性變化情況，且任何情況下隨著網絡的逐漸破壞，LREM的值始終小于最大連通子圖比例F，即魯棒性的減少程度明顯大于F。對于網絡效能比EM，網絡破壞程度較小時，在較為脆弱的網絡中(如BA-BA網絡)LREM小于EM，在較為健壯的網絡中(如WS-WS網絡)則大于EM；在網絡接近崩潰時，由于子網絡連通性強于相依網絡整體連通性導致LREM會略微大于EM。由此表明，相比于現有常用指標最大連通子圖比例F和網絡效能比EM，本文提出的最大連通子圖相對效能比LREM對相依網絡中魯棒性的變化更加敏感，尤其在規模較大以及結構相對脆弱的網絡中優勢更大，能更準確細致地衡量相依網絡在級聯失效過程中的魯棒性變化，適合大規模相依網絡中的魯棒性度量。

5 結 束 語

本文針對相依網絡，結合現有常用的最大連通子圖比例和網絡效能比指標，綜合考慮每個子網絡在攻擊前后網絡全局和最大連通子圖的連通性，提出了一個結合了最大連通子圖比例和網絡效能的魯棒性度量指標—最大連通子圖相對效能比LREM，并在BA-BA、BA-WS、WS-WS相依網絡模型下與現有常用指標進行對比研究。研究發現，最大連通子圖相對效能比LREM相比于現有常用指標能更精確地衡量相依網絡在級聯失效過程中的魯棒性變化，尤其在規模較大以及結構相對脆弱的相依網絡中具有明顯優勢，是一個評估相依網絡魯棒性變化的合理度量指標。

本文為保證研究的代表性，主要針對兩層一對一相依網絡進行魯棒性研究，而在現實的相依網絡中還會存在很多非對稱的相依關系，如部分相依、有向相依、一對多或多對多相依等，并且可能會出現更多層的網絡以及節點或邊帶權等情況，需要綜合考慮的因素較多。因此，在未來的工作中需要將LREM魯棒性指標放入更加實際的應用環境中進行驗證，綜合考慮各種因素改進LREM指標，使其具有更加準確的度量效果。

本文研究工作還得到昆明市衛健委項目(2020-09-04-112)的資助，在此表示感謝。