相互依賴網(wǎng)絡(luò)的多參數(shù)混合冪次迭代瓦解策略

付 豪，劉三陽，白藝光

西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西安710126

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

在復(fù)雜網(wǎng)絡(luò)系統(tǒng)中，相互依賴網(wǎng)絡(luò)由于其不同子網(wǎng)絡(luò)的相耦合性，導(dǎo)致相互依賴網(wǎng)絡(luò)比單層的網(wǎng)絡(luò)更加脆弱。因此，其對(duì)于某個(gè)局部的攻擊將更加敏感，容易出現(xiàn)大規(guī)模的網(wǎng)絡(luò)癱瘓災(zāi)難，如2003 年北美大停電[3]、2004 年意大利大停電等[4]。因此研究這些網(wǎng)絡(luò)的魯棒性對(duì)于防止網(wǎng)絡(luò)系統(tǒng)崩潰至關(guān)重要。對(duì)相互依賴網(wǎng)絡(luò)的研究是一個(gè)吸引人且活躍的領(lǐng)域。

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

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

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

由于現(xiàn)有的中心性測(cè)度大多集中在特定的結(jié)構(gòu)特征上，對(duì)節(jié)點(diǎn)的真實(shí)排序有一定限制。前文提到的各種中心性措施都趨向于高度值節(jié)點(diǎn)，然而，有研究人員發(fā)現(xiàn)，許多低度節(jié)點(diǎn)在復(fù)雜系統(tǒng)中也是有重要意義的[28]。因此，為了準(zhǔn)確識(shí)別關(guān)鍵節(jié)點(diǎn)，需要優(yōu)化中心性測(cè)度，盡可能全面地捕捉網(wǎng)絡(luò)節(jié)點(diǎn)的結(jié)構(gòu)信息。為了說明這一思想，圖1給出了具有不同結(jié)構(gòu)特征的重要節(jié)點(diǎn)的例子。

圖1 具有不同結(jié)構(gòu)的重要節(jié)點(diǎn)Fig.1 Significant nodes with different structures

圖1（a）中紅色的局部?jī)?yōu)勢(shì)節(jié)點(diǎn)保持與大部分網(wǎng)絡(luò)節(jié)點(diǎn)的連接，圖1（b）中紅色的中間節(jié)點(diǎn)保證了網(wǎng)絡(luò)的完整性，對(duì)網(wǎng)絡(luò)組件之間的交流有更多的控制，圖1（c）中藍(lán)色節(jié)點(diǎn)具有局部?jī)?yōu)勢(shì)節(jié)點(diǎn)的特征，紅色節(jié)點(diǎn)同時(shí)具有局部?jī)?yōu)勢(shì)節(jié)點(diǎn)和中間節(jié)點(diǎn)的特征。可見，帶有紅色和藍(lán)色節(jié)點(diǎn)在網(wǎng)絡(luò)結(jié)構(gòu)中起著至關(guān)重要的作用，準(zhǔn)確的節(jié)點(diǎn)排序需要考慮所有的結(jié)構(gòu)特征。

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

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

實(shí)驗(yàn)結(jié)果表明，本文方法在網(wǎng)絡(luò)最優(yōu)瓦解問題上優(yōu)于其他先進(jìn)的方法。

1 模型定義

1.1 相互依賴網(wǎng)絡(luò)模型

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

圖2 相互依賴網(wǎng)絡(luò)模型Fig.2 Interdependence network model

1.2 級(jí)聯(lián)失效和GMCC

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

圖3 中實(shí)線表示內(nèi)部鏈路，虛線表示外部鏈路，長(zhǎng)方型為被攻擊節(jié)點(diǎn)，正三角表示不屬于巨型集群的節(jié)點(diǎn)，黑色圓用符號(hào)表示沒有依賴節(jié)點(diǎn)的節(jié)點(diǎn)，藍(lán)色圓表示功能節(jié)點(diǎn)。

圖3 級(jí)聯(lián)失效過程Fig.3 Cascading failure process

1.3 參數(shù)

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

網(wǎng)絡(luò)A中節(jié)點(diǎn)i的度定義為：

在耦合網(wǎng)絡(luò)中，節(jié)點(diǎn)Ai的重疊度[25]表示為：

網(wǎng)絡(luò)A中節(jié)點(diǎn)i的介數(shù)中心性定義為：

在耦合網(wǎng)絡(luò)中，節(jié)點(diǎn)Ai的重疊介數(shù)中心性[25]可以表示為：

1.4 標(biāo)準(zhǔn)質(zhì)量擴(kuò)散（MD）和標(biāo)準(zhǔn)熱傳導(dǎo)（HC）

一個(gè)無向網(wǎng)絡(luò)可以表示為G(V,E)，其中V為節(jié)點(diǎn)的集合，E為邊的集合，ri為節(jié)點(diǎn)i的資源，Γi為其鄰居的集合。標(biāo)準(zhǔn)的質(zhì)量擴(kuò)散（MD）過程首先通過為節(jié)點(diǎn)分配初始資源級(jí)別ri=ri(0)，在每次迭代中，每個(gè)節(jié)點(diǎn)的資源被均勻地重新分配給它的鄰居。在這個(gè)再分配過程中，每個(gè)節(jié)點(diǎn)更新的資源等于它的鄰居貢獻(xiàn)的總和，數(shù)學(xué)上表示為：

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

與MD 過程類似，熱傳導(dǎo)（HC）過程也以類似于無規(guī)則過程的方式重新分配資源。網(wǎng)絡(luò)節(jié)點(diǎn)的初始溫度不同，熱從高溫節(jié)點(diǎn)傳遞到低溫鄰居節(jié)點(diǎn)。不同之處在于，HC過程通過一個(gè)最近鄰平均過程更新節(jié)點(diǎn)的狀態(tài)，在這個(gè)過程中，它們的鄰居的溫度總和除以它們的度數(shù)，而MD過程通過將資源平均分配給最近的鄰居來工作，HC過程在數(shù)學(xué)上表示為：

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

2 迭代更新機(jī)制

本文構(gòu)建一種混合更新機(jī)制，調(diào)節(jié)節(jié)點(diǎn)度對(duì)節(jié)點(diǎn)重要性的影響。結(jié)合節(jié)點(diǎn)度和節(jié)點(diǎn)介數(shù)中心性在標(biāo)準(zhǔn)MD 和HC 過程更新規(guī)則中的作用，通過適當(dāng)調(diào)整權(quán)重參數(shù)，該混合更新機(jī)制對(duì)具有特定結(jié)構(gòu)特征的關(guān)鍵節(jié)點(diǎn)具有良好的識(shí)別性能。連接矩陣A={aij}∈RN×N，當(dāng)節(jié)點(diǎn)i和j是連接的時(shí)候aij=1，否則等于0，網(wǎng)絡(luò)節(jié)點(diǎn)的迭代更新操作可以表示為：

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

其中，dj為節(jié)點(diǎn)j的重疊度數(shù)。HC過程通過最近鄰平均化過程更新節(jié)點(diǎn)狀態(tài)，因此HC過程對(duì)應(yīng)的轉(zhuǎn)移矩陣WH的元素可定義為：

為了使混合更新機(jī)制具體化并實(shí)現(xiàn)兩個(gè)物理過程之間的平滑過渡，通過非線性混合機(jī)制將MD 和HC 過程結(jié)合起來，并將權(quán)重參數(shù)化納入到過渡矩陣的歸一化中?；旌细聶C(jī)制的轉(zhuǎn)換矩陣WM+H定義為：

很明顯，當(dāng)λ=0 時(shí)退化為MD算法，當(dāng)λ=1 時(shí)退化為HC算法（本文取λ=0.7）?；谵D(zhuǎn)移矩陣WM+H，迭代更新操作可以重新表示為矩陣式為：

當(dāng)節(jié)點(diǎn)之間之間存在一條邊時(shí)，一個(gè)節(jié)點(diǎn)重新分配給它的鄰居的資源與概率成正比。

3 算法核心

值得注意的是，本文所提出的混合更新機(jī)制避免了資源集中在幾個(gè)高度節(jié)點(diǎn)上，使得一些有意義的低度節(jié)點(diǎn)也能被選擇出來。在PIA 算法中，節(jié)點(diǎn)隨機(jī)初始化，使用混合更新機(jī)制更新節(jié)點(diǎn)的排名得分，利用網(wǎng)絡(luò)節(jié)點(diǎn)的穩(wěn)定狀態(tài)對(duì)節(jié)點(diǎn)進(jìn)行排名。

算法PI Algorithm

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

4 實(shí)驗(yàn)結(jié)果

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

子網(wǎng)絡(luò)構(gòu)建算法如下。

BA網(wǎng)絡(luò)：

增長(zhǎng)：初始化一個(gè)具有m0節(jié)點(diǎn)的完全連接圖，并向網(wǎng)絡(luò)中已有的多個(gè)節(jié)點(diǎn)添加m個(gè)新連接(m＜m0)。

連接：根據(jù)輪盤賭游戲添加連接。

ER網(wǎng)絡(luò)：

初始化：給定N個(gè)節(jié)點(diǎn)和需要添加的邊數(shù)M。

隨機(jī)連接：隨機(jī)選擇一對(duì)沒有內(nèi)部連接的節(jié)點(diǎn)，在節(jié)點(diǎn)之間添加一條邊；重復(fù)上述過程，直到在不同對(duì)節(jié)點(diǎn)之間添加了M個(gè)連接。

WS網(wǎng)絡(luò)：

初始化：生成一個(gè)有N個(gè)節(jié)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，其中每個(gè)節(jié)點(diǎn)連接到其左右的各K/2 個(gè)節(jié)點(diǎn)。

重連接：以概率p隨機(jī)重連接網(wǎng)絡(luò)中的邊緣。

為了比較不同拆除策略的效果，從網(wǎng)絡(luò)平均節(jié)點(diǎn)度和網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)兩個(gè)角度評(píng)估相互依賴網(wǎng)絡(luò)的魯棒性。每條曲線是15次模擬的平均值。

G反映了相互依賴網(wǎng)絡(luò)在最初出現(xiàn)故障后繼續(xù)運(yùn)作的能力，從圖4～9中可以看出，在相互依賴的網(wǎng)絡(luò)中，當(dāng)相同數(shù)量的節(jié)點(diǎn)被移除以后，對(duì)比其他策略，PIA 的所對(duì)應(yīng)G幾乎都是最小的。從圖9 中看出在某些特殊情況下，PIA 策略和其他策略效果類似。因此，可以得出在各種相互依賴的網(wǎng)絡(luò)中，PIA策略優(yōu)于其他策略。

圖4 去掉部分節(jié)點(diǎn)以后G的大?。∟=500，子網(wǎng)絡(luò)A的平均度等于8，B的平均度等于8）Fig.4 GMCC size after q fraction of nodes is removed

圖5 去掉部分節(jié)點(diǎn)以后G的大?。∟=500，子網(wǎng)絡(luò)A的平均度等于10，B的平均度等于10）Fig.5 GMCC size after q fraction of nodes is removed

圖6 去掉部分節(jié)點(diǎn)以后G的大?。∟=700，子網(wǎng)絡(luò)A的平均度等于8，B的平均度等于8）Fig.6 GMCC size after q fraction of nodes is removed

圖7 去掉部分節(jié)點(diǎn)以后G的大小（N=700，子網(wǎng)絡(luò)A的平均度等于10，B的平均度等于10）Fig.7 GMCC size after q fraction of nodes is removed

圖8 去掉部分節(jié)點(diǎn)以后G的大?。∟=1 000，子網(wǎng)絡(luò)A的平均度等于5，B的平均度等于5）Fig.8 GMCC size after q fraction of nodes is removed

圖9 去掉部分節(jié)點(diǎn)以后G的大?。∟=1 000，子網(wǎng)絡(luò)A的平均度等于8，B的平均度等于8）Fig.9 GMCC size after q fraction of nodes is removed

網(wǎng)絡(luò)瓦解也對(duì)應(yīng)于尋找移除節(jié)點(diǎn)的最小比例qc（q表示移除的節(jié)點(diǎn)占總節(jié)點(diǎn)比值），以確保G小于期望：

qc=ε表示在一串級(jí)聯(lián)失效以后G的期望。

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

圖10 不同策略對(duì)不同網(wǎng)絡(luò)效果的對(duì)比Fig.10 Comparison of different strategies for different network effects

圖11 去掉q 部分節(jié)點(diǎn)后各種策略真實(shí)網(wǎng)絡(luò)的模擬效果圖Fig.11 Simulation renderings of real networks with various strategies after removing part q nodes

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

根據(jù)模擬結(jié)果可以得出結(jié)論，PIA仍然比其他策略有更好的表現(xiàn)。

5 結(jié)語

在本文中，研究了相互依賴網(wǎng)絡(luò)的最優(yōu)解的問題，主要目的在于尋找去除這些節(jié)點(diǎn)后能使網(wǎng)絡(luò)崩潰的最小節(jié)點(diǎn)集。提出了一種新的分解策略PIA，根據(jù)三個(gè)指標(biāo)選擇促進(jìn)GMCC縮小最快的節(jié)點(diǎn)集。大量的仿真結(jié)果表明，在真實(shí)相互依賴網(wǎng)絡(luò)和人工雙層網(wǎng)絡(luò)中，PIA策略的性能都優(yōu)于IEP 和其他策略。但是本文只考慮非加權(quán)的相互依賴網(wǎng)絡(luò)，由于成本的限制，現(xiàn)實(shí)網(wǎng)絡(luò)往往都是加權(quán)網(wǎng)絡(luò)。接下來將研究加權(quán)網(wǎng)絡(luò)的結(jié)構(gòu)，將權(quán)重作為節(jié)點(diǎn)特性的一部分來進(jìn)行算法改進(jìn)。