相互依賴網絡的多參數混合冪次迭代瓦解策略

付 豪，劉三陽，白藝光

西安電子科技大學 數學與統計學院，西安710126

進入21 世紀，人類之間的社交關系由于科技的進步變得更為緊密?；陉P系的社交網絡正在從傳統網絡結構向大尺度、高密度的形態轉變。更為復雜的網絡結構往往會為人類帶來巨大挑戰，如2019 年12 月爆發的Covid-19新冠肺炎，病毒伴隨著更為便捷的交通網絡與更為密切的社交接觸，向全球快速蔓延，對人類社會的正常運轉帶來了巨大挑戰。因此對各種基于復雜網絡的社會行為進行更深入的研究是有重要現實意義的。事實上單一的網絡結構不能準確、完整地描述現實生活中復雜問題的相互聯系。絕大多數嚴重災害都是由小事件引發的，這些小事件可能會在更為復雜的相互依賴網絡中引發一連串的故障，甚至導致網絡完全崩潰[1-2]。

在復雜網絡系統中，相互依賴網絡由于其不同子網絡的相耦合性，導致相互依賴網絡比單層的網絡更加脆弱。因此，其對于某個局部的攻擊將更加敏感，容易出現大規模的網絡癱瘓災難，如2003 年北美大停電[3]、2004 年意大利大停電等[4]。因此研究這些網絡的魯棒性對于防止網絡系統崩潰至關重要。對相互依賴網絡的研究是一個吸引人且活躍的領域。

網絡瓦解是指通過移除某些節點，使連通網絡分裂成不相連的簇甚至使整個網絡結構崩潰，目的是找到使得網絡完全崩潰的最小節點集[5]。網絡最優瓦解策略已經引起了大量研究者的關注，并被應用在許多新興領域，包括病毒控制[6]和交通網絡分析[7]等。網絡的最優瓦解問題是一個NP-Hard問題，無法在多項式時間內進行有效求解。在單個網絡中，眾多研究者基于節點中心性指標（如度、介數、k-Core、PageRank等）提出了大量的關于網絡最優瓦解的方法（隨機攻擊（RA）、基于重疊度攻擊（OD）、基于重疊介數中心性攻擊（OB））[8-9]。尤其是節點排序問題被專門用來度量給定網絡中節點的重要性[8，10]，實驗表明，攻擊重要性更高的節點，能夠使得網絡崩潰得更快。對應的，Iyer等人提出了各種基于中心性的瓦解方法，包括：基于鄰域的局部中心性（度中心性、局部中心性[9，11]），基于位置的全局中心（緊密性中心性、介數中心性、k核中心性[12-13]）以及路徑計算中心性（特征向量中心性、Katz中心性、PageRank、RA中心性[14-15]）等。

由于網絡系統的多樣性，每個網絡中的關鍵節點可以從不同的角度被具體化。例如，影響力最大化問題中的關鍵節點是傳播信息的影響源[16]；網絡中斷問題中的關鍵節點是保持網絡完整性[17]的中間節點。其中，影響力最大化問題近年來備受關注，針對該問題提出了多種單節點排序方法[18]和多種隨機識別方法[19]。同時，時序網絡的節點排序方法也開始受到研究者們的關注[20]。因此，關鍵節點在不同的應用背景中可能有不同的含義，對于關鍵節點的定義目前并沒有普遍的共識。Zareie 等人提出了一種基于熵的節點向內排序方法[21]。Wu 等人提出了一種基于兩個互補物理過程的算法，用于度量節點的重要性[22]。

相互依賴網絡不同于單一網絡，因為其內在關系的種類更多，不同層之間的相互聯系使得其結構也更加復雜。Schneider等人根據度中心性和介數中心性來識別節點，并選擇最小數量的節點，以保證魯棒性的平滑過渡[23]。Wang 等人提出了一種鄰居節點優先連接耦合策略[24]。Song提出一種算法來識別重要節點[25]，其在每次迭代中選擇一個盡可能降低系統結構強度的節點。Osat等人拓展模擬退火（SA）、高階退火（HD）和高度自適應（HDA）等算法到多層網絡[26]，以解決最優滲透問題。Zhao等人提出了一種逆向爆發滲透算法（IEP），是一種基于網絡重構的滲透算法[27]，在IEP中，從所有未插入節點中隨機選取m個候選節點以降低計算復雜度，并以節點的重疊度作為進一步的基準，然而，其結果并不是魯棒的。

由于現有的中心性測度大多集中在特定的結構特征上，對節點的真實排序有一定限制。前文提到的各種中心性措施都趨向于高度值節點，然而，有研究人員發現，許多低度節點在復雜系統中也是有重要意義的[28]。因此，為了準確識別關鍵節點，需要優化中心性測度，盡可能全面地捕捉網絡節點的結構信息。為了說明這一思想，圖1給出了具有不同結構特征的重要節點的例子。

圖1 具有不同結構的重要節點Fig.1 Significant nodes with different structures

圖1（a）中紅色的局部優勢節點保持與大部分網絡節點的連接，圖1（b）中紅色的中間節點保證了網絡的完整性，對網絡組件之間的交流有更多的控制，圖1（c）中藍色節點具有局部優勢節點的特征，紅色節點同時具有局部優勢節點和中間節點的特征。可見，帶有紅色和藍色節點在網絡結構中起著至關重要的作用，準確的節點排序需要考慮所有的結構特征。

事實上，高影響力鄰居節點對中心節點的影響大于低影響力的鄰居節點，如果一個節點有很多高影響力的鄰居節點，那么這個節點就具有更高影響力。本文的目標是解決關鍵節點識別問題，受兩個經典物理過程（質量擴散MD和熱傳導HC）機制的啟發，提出了一個復雜而有效的中心性迭代方法來全面捕獲網絡結構信息。首先，利用鄰居節點對每個節點的影響提出一種改進冪次迭代排序算法。接著，從所有候選節點中選擇會導致剩余集群最小的節點，以快速瓦解相互依賴網絡。此外，在該算法中，定義了一種新的權重加權迭代機制，并探討了所提加權迭代機制的合理性。為了評估所提出的算法的性能，分別將其應用于合成網絡和真實網絡。

本文主要貢獻：（1）通過充分耦合MD 和HC 兩個經典處理方法，可以深入挖掘出“影響力弱”的重要性節點，而這些節點往往在已有的算法中所忽視。（2）基于冪次迭代的排序提供了剩余集群的局部更新策略，極大提升了計算效率。

實驗結果表明，本文方法在網絡最優瓦解問題上優于其他先進的方法。

1 模型定義

1.1 相互依賴網絡模型

雙層相互依賴的網絡模型A(VA,EA)-B(VB,EB)，由兩個相互依賴的子網絡A(VA,EA)和B(VB,EB)組成，兩個子網絡有著相同的節點數量N，通過相互耦合連接形成一個完整的相互依賴網絡。其中，VA和EA分別是網絡A的節點和連接邊，VB和EB分別是網絡B的節點和連接邊。只有當節點屬于其所在的子網絡層的最大連接集群，該節點才會保持功能，否則該節點將失效。圖2中一對一相互依賴網絡結構，上子網中的每個節點都依賴于下子網中的一個且只有一個節點，反之亦然。

圖2 相互依賴網絡模型Fig.2 Interdependence network model

1.2 級聯失效和GMCC

網絡中一個或多個節點的故障可能導致多米諾骨牌效應，使得失效節點的鄰居節點甚至是所有節點從整個相互依賴耦合網絡里面斷開，最后導致整個網絡崩潰，這個過程稱為級聯失效過程。在相互依賴的網絡中，通常的級聯故障是由移除網絡節點而引發的，初始移除一個節點往往等于移除它的從屬節點。例如在圖3中，移除子網A上的一部分節點后，B中所有連接到A中這些節點且未運行的節點都將失效，進而導致這些不再屬于兩個子網龐大集群的節點失效。直到A和B上沒有節點被移除，這個動態過程才會結束。剩余網絡中的有效節點形成一個簇，稱為巨型相互連接集群（GMCC）。

圖3 中實線表示內部鏈路，虛線表示外部鏈路，長方型為被攻擊節點，正三角表示不屬于巨型集群的節點，黑色圓用符號表示沒有依賴節點的節點，藍色圓表示功能節點。

圖3 級聯失效過程Fig.3 Cascading failure process

1.3 參數

考慮有N個節點的無向網絡A(VA,EA)和B(VB,EB)，通過一對一的條件進行相互耦合，假定Ai只是依賴于Bi，則鄰接矩陣分別為A=(aij)N×N和B=(bij)N×N。

網絡A中節點i的度定義為：

在耦合網絡中，節點Ai的重疊度[25]表示為：

網絡A中節點i的介數中心性定義為：

在耦合網絡中，節點Ai的重疊介數中心性[25]可以表示為：

1.4 標準質量擴散（MD）和標準熱傳導（HC）

一個無向網絡可以表示為G(V,E)，其中V為節點的集合，E為邊的集合，ri為節點i的資源，Γi為其鄰居的集合。標準的質量擴散（MD）過程首先通過為節點分配初始資源級別ri=ri(0)，在每次迭代中，每個節點的資源被均勻地重新分配給它的鄰居。在這個再分配過程中，每個節點更新的資源等于它的鄰居貢獻的總和，數學上表示為：

其中，dj為節點j的屬性指標，在本文的策略中使用網絡的重疊度和重疊介數中心性，rj(t)為節點j在t時刻的資源占用級別。通過再分配過程的迭代，網絡中所有節點的資源趨于穩定。當資源不再變化時，這個過程就會收斂并達到平衡。一個節點所保留的資源與迭代更新中其他節點釋放的資源到達該節點的概率成正比。網絡節點的重要性排序是通過對所有節點按照其最終資源的取值大小進行降序排列來生成的。

與MD 過程類似，熱傳導（HC）過程也以類似于無規則過程的方式重新分配資源。網絡節點的初始溫度不同，熱從高溫節點傳遞到低溫鄰居節點。不同之處在于，HC過程通過一個最近鄰平均過程更新節點的狀態，在這個過程中，它們的鄰居的溫度總和除以它們的度數，而MD過程通過將資源平均分配給最近的鄰居來工作，HC過程在數學上表示為：

通過對平均過程的迭代，縮小了高資源節點和低資源節點之間的差距。注意，標準HC過程中的總資源是可變的，而標準MD過程中的資源總量是不變的。對于MD過程，資源將均勻地分配給它的鄰居。與此相反，在HC過程中，通過平均化過程對資源進行重新分配，節點接收到的資源水平等于其相鄰節點擁有的資源的平均數量。

2 迭代更新機制

本文構建一種混合更新機制，調節節點度對節點重要性的影響。結合節點度和節點介數中心性在標準MD 和HC 過程更新規則中的作用，通過適當調整權重參數，該混合更新機制對具有特定結構特征的關鍵節點具有良好的識別性能。連接矩陣A={aij}∈RN×N，當節點i和j是連接的時候aij=1，否則等于0，網絡節點的迭代更新操作可以表示為：

其中，R(t)是包含所有節點在第t步持有的排名分數的n維向量，W是轉移矩陣，R(t+1) 是所有節點在第t+1步持有的分數。該公式定義了W等于連接矩陣A時特征向量中心性的更新機制。由于MD 過程將節點的資源均勻分布到其相鄰矩陣中，因此MD過程對應的轉移矩陣WM的元素可定義為：

其中，dj為節點j的重疊度數。HC過程通過最近鄰平均化過程更新節點狀態，因此HC過程對應的轉移矩陣WH的元素可定義為：

為了使混合更新機制具體化并實現兩個物理過程之間的平滑過渡，通過非線性混合機制將MD 和HC 過程結合起來，并將權重參數化納入到過渡矩陣的歸一化中。混合更新機制的轉換矩陣WM+H定義為：

很明顯，當λ=0 時退化為MD算法，當λ=1 時退化為HC算法（本文取λ=0.7）。基于轉移矩陣WM+H，迭代更新操作可以重新表示為矩陣式為：

當節點之間之間存在一條邊時，一個節點重新分配給它的鄰居的資源與概率成正比。

3 算法核心

值得注意的是，本文所提出的混合更新機制避免了資源集中在幾個高度節點上，使得一些有意義的低度節點也能被選擇出來。在PIA 算法中，節點隨機初始化，使用混合更新機制更新節點的排名得分，利用網絡節點的穩定狀態對節點進行排名。

算法PI Algorithm

有效的節點排序算法只需運行迭代規則即可得到正確的排序列表，而不需要最終收斂。因此，將PIA 的終點設在δt+1≈δt處，而不在R(t+1)≈R(t)處。當W的顯性特征值和次顯性特征值（分別為λ′和λ″）的絕對值不同且|λ′|＞|λ″|時，該算法收斂。收斂速度與是成正比的。在實踐中，收斂通常很快發生。冪次迭代求解要求轉移矩陣W是對稱的，但即使存在條件較差的矩陣，冪次迭代求解也總是收斂的。

4 實驗結果

比較了PIA 與IEP、RA、OD 和OB 在六個相互依賴網絡（ER-BA、ER-WS、BA-BA、BA-WS、WS-WS）的差異。其中，RA 表示隨機選取節點進行攻擊的策略，OD表示選取節點度最高的節點進行攻擊的策略，OB 表示選取節點重疊介數中心性最高的節點進行攻擊的策略。在所有相互依賴的網絡中，子網A中的每個節點都僅依賴子網B中的一個節點，反之亦然（如圖2所示）。

子網絡構建算法如下。

BA網絡：

增長：初始化一個具有m0節點的完全連接圖，并向網絡中已有的多個節點添加m個新連接(m＜m0)。

連接：根據輪盤賭游戲添加連接。

ER網絡：

初始化：給定N個節點和需要添加的邊數M。

隨機連接：隨機選擇一對沒有內部連接的節點，在節點之間添加一條邊；重復上述過程，直到在不同對節點之間添加了M個連接。

WS網絡：

初始化：生成一個有N個節點的最近鄰耦合網絡，其中每個節點連接到其左右的各K/2 個節點。

重連接：以概率p隨機重連接網絡中的邊緣。

為了比較不同拆除策略的效果，從網絡平均節點度和網絡總節點數兩個角度評估相互依賴網絡的魯棒性。每條曲線是15次模擬的平均值。

G反映了相互依賴網絡在最初出現故障后繼續運作的能力，從圖4～9中可以看出，在相互依賴的網絡中，當相同數量的節點被移除以后，對比其他策略，PIA 的所對應G幾乎都是最小的。從圖9 中看出在某些特殊情況下，PIA 策略和其他策略效果類似。因此，可以得出在各種相互依賴的網絡中，PIA策略優于其他策略。

圖4 去掉部分節點以后G的大?。∟=500，子網絡A的平均度等于8，B的平均度等于8）Fig.4 GMCC size after q fraction of nodes is removed

圖5 去掉部分節點以后G的大小（N=500，子網絡A的平均度等于10，B的平均度等于10）Fig.5 GMCC size after q fraction of nodes is removed

圖6 去掉部分節點以后G的大?。∟=700，子網絡A的平均度等于8，B的平均度等于8）Fig.6 GMCC size after q fraction of nodes is removed

圖7 去掉部分節點以后G的大?。∟=700，子網絡A的平均度等于10，B的平均度等于10）Fig.7 GMCC size after q fraction of nodes is removed

圖8 去掉部分節點以后G的大?。∟=1 000，子網絡A的平均度等于5，B的平均度等于5）Fig.8 GMCC size after q fraction of nodes is removed

圖9 去掉部分節點以后G的大?。∟=1 000，子網絡A的平均度等于8，B的平均度等于8）Fig.9 GMCC size after q fraction of nodes is removed

網絡瓦解也對應于尋找移除節點的最小比例qc（q表示移除的節點占總節點比值），以確保G小于期望：

qc=ε表示在一串級聯失效以后G的期望。

圖10在六個不同的相互依賴網絡上，采用4種不同的m的PIA 策略和其他策略的qc(ε=0)值。從圖10 中可以得出結論，在所有網絡中，每個策略中對于不同m，PIA策略的效果均處在最優的位置。在不同的策略下，幾乎所有的PIA策略都比其他策略表現出更好的效率。此外，將算法應用在了一個真實世界中相互依賴的網絡中，使用從2000年1月2日自治網絡系統導出的子圖和IEEE 118總線測試用例的電網，是一個具有118個節點的電力和互聯網耦合網絡。圖11顯示了去除不同的m個節點后相互依賴網絡的GMCC大小，表1顯示了各種策略下的qc。

圖10 不同策略對不同網絡效果的對比Fig.10 Comparison of different strategies for different network effects

圖11 去掉q 部分節點后各種策略真實網絡的模擬效果圖Fig.11 Simulation renderings of real networks with various strategies after removing part q nodes

表1 各種策略下的的qcTable 1 qc under various strategies

根據模擬結果可以得出結論，PIA仍然比其他策略有更好的表現。

5 結語

在本文中，研究了相互依賴網絡的最優解的問題，主要目的在于尋找去除這些節點后能使網絡崩潰的最小節點集。提出了一種新的分解策略PIA，根據三個指標選擇促進GMCC縮小最快的節點集。大量的仿真結果表明，在真實相互依賴網絡和人工雙層網絡中，PIA策略的性能都優于IEP 和其他策略。但是本文只考慮非加權的相互依賴網絡，由于成本的限制，現實網絡往往都是加權網絡。接下來將研究加權網絡的結構，將權重作為節點特性的一部分來進行算法改進。