基于級聯失效的相互作用網絡的動態分析

齊小彤 路立萍 隋緣 王思蒙 滕煒

摘? 要：相互作用網絡是一種除了相互作用網絡內部中節點間存在邊外，網絡之間還存在相互依賴的邊。這種情況下，如果其中一個節點失效，由于該點存在依賴邊指向另外一個網絡，會導致依賴邊所指向的節點失效，其稱為級聯失效，級聯失效的存在會導致整個相互依賴系統的崩潰。文章針對級聯失效所引起的整個相互依賴系統崩潰問題選取合適的優化模型，求出最大相互作用聯通網絡和最少的節點數量，最后根據實驗過程對不同模型求解的優劣進行分析。

關鍵詞：BA優化模型;hub節點;遺傳算法優化模型

中圖分類號：TP393.03? ? ? 文獻標識碼：A 文章編號：2096-4706（2020）22-0161-03

Dynamic Analysis of Interaction Network Based on Cascading Failure

QI Xiaotong，LU Liping，SUI Yuan，WANG Simeng，TENG Wei

（Business School，Qingdao University of Technology，Qingdao? 266520，China）

Abstract：Interaction network is a kind of interaction network，in which there are not only edges among nodes，but also interdependent edges among networks. In this case，if one of the nodes fails，because the dependent edge points to another network，it will lead to the failure of the node pointed by the dependent edge，which is called cascading failure. The existence of cascading failure will lead to the collapse of the whole interdependent system. In this paper，for the collapse of the whole interdependent system caused by cascading failure，we select the appropriate optimization model，find out the maximum interaction network and the minimum number of nodes. Finally，the advantages and disadvantages of different models are analyzed according to the experimental process.

Keywords：BA optimization model;hub node;genetic algorithm optimization model

0? 引? 言

相互作用網絡被廣泛運用到眾多領域之中，其中有一種效應被稱為級聯失效，是一種一個節點失效，并且該點存在依賴邊指向另外一個網絡時，導致依賴邊所指向的節點失效，從而放大了失效節點的后果。例如，2003年意大利和北美停電事故中，均存在電力-計算機網絡構成了相互作用網絡的問題。由此可見，相互作用網絡與我們的生活息息相關，2010年，Sergey等人在Nature雜志上提出了相互作用網絡的理論化模型和數學分析方法，引起了國內外學者的廣泛關注。從那以后，相互作用網絡模型被不斷改進，從最初的一對一模型到多對多模型，從全局耦合模型到部分耦合模型，從一般的級聯模型到負載級聯模型等。目前，相互作用網絡的研究主要集中在魯棒性、級聯控制與防御、攻擊策略、級聯模型的構建以及研究的數學方法的探索等。其中最為核心的問題是相互作用網絡的魯棒性研究。筆者結合學校的級聯失效數學競賽研究項目以及數學建模比賽參賽經驗，對不同算法求解級聯失效問題的效果做了進一步研究。

1? 問題背景

近幾年，相互作用網絡受到國內外的廣泛關注。級聯失效的存在會導致整個相互依賴系統的崩潰。由于相互作用網絡的特點，會導致一個節點的失效被放大進而導致整個相互依賴系統的崩潰，故其研究對于電力-計算機網絡的結構發展創新起著重要作用[1]。

2? 問題分析

2.1? 問題一分析

問題一：建立合適的優化模型，對于選擇的m個節點進行攻擊，使得最終最大相互連通集團的節點數量g最少。并當m為1～50個時，對4個相互作用網絡的g進行求解，利用MATLAB編程繪制出m與g的關系圖。

經過查閱相關文獻資料可知，本題中相互作用網絡屬于無標度網絡mi，問題中對m個節點進行的攻擊屬于蓄意攻擊，而蓄意攻擊對于無標度網絡而言，其魯棒性更弱，會使網絡迅速瓦解，崩潰的節點數驟增。經過硏究分析發現，發生崩潰的節點大部分為網絡中的hub節點，即節點度數高的節點，其往往會對網絡造成很大沖擊，進而引起嚴重的級聯失效。因此建立模型的目標是基于在無標度網絡模型中找到hub節點，并對其進行攻擊，可得出最大相互聯通集團的節點數最少，對其進行進一步的分析，確定m與g的關系，繪制出相應的關系圖。

2.2? 問題二分析

問題二：對問題一中所選定的優化模型在基于實際操作的基礎上進行展開分析，研究其時間和效率問題，并對操作過程中所發現的問題在題目中提示的啟發式算法中選取更適合的模型。

問題二首先要求對問題一中的優化模型進行評價，經建立BA優化模型求解過程，可發現BA優化模型[2]實際應用過程中存在著耗費時間長，效率低下的問題。因此，面對BA優化模型所存在的問題，需要尋求更高效率的算法，經過文獻資料和實際編程分析發現啟發式算法相對于優化模型來說，效率更高。在對題目進行分析后，采用啟發式算法中的遺傳算法優化模型進行研究分析。

3? 模型建立與求解

3.1? BA優化模型

3.1.1? 模型建立

根據題目中要求和相應的文獻資料查詢可知BA無標度網絡構造模型[3]如下：BA無標度網絡構造模型是構建無標度網絡的經典模型，其構造原理主要為增長和優先連接機制，其具體的構造方法為：（1）在起步階段主要是進行網絡節點的增長，開始時網絡只有很少的節點（n0），每一時間步驟內增加1個節點，新增加的節點與已存在的節點有n（≤n0）條邊。（2）其次在節點增長的基礎之上，采用偏好連接的方式，使增加的節點以偏好概率p（i）與已經存在的節點i進行連接，滿足的關系式為：

式中，ki為節點i的度數，j為所有已存在的節點。

建立BA優化模型，基于BA無標度網絡構造模型中的構造方法中的（2）可知新節點連接原網絡的方式，按照偏好概率往原網絡中添加一定數量的新節點，然后對網絡中添加的節點進行概率統計，統計后取出概率大的節點，以此概率作為節點的重要度評價指標。

3.1.2? 模型求解

模型求解的具體過程為：（1）hub點的尋找：在選定好相互作用網絡后，從其中選取m個相對重要的hub點，第一步首先將各個節點的度值求出，第二步基于構建的BA優化模型向原網絡中增加一定數量新的節點，各個新節點的連接都以偏好概率p（i）與節點i進行相連，然后將各個新節點連接的原網絡中的節點的編號進行概率統計，并將其中前m個概率大的編號進行保存，這也就是要尋找的hub點的位置編號。（2）蓄意攻擊：本題的相互作用網絡在蓄意攻擊下有較大的脆弱性，也就是說明對hub節點進行攻擊后經過級聯失效[2]后，網絡能得到相對較分散的相互連通集團，基于本題第一二問構建的main1_1函數，將相互作用網絡的兩個子網絡A1和A2以及1中找到的hub節點的編號作為輸入，對網絡進行蓄意攻擊。

3.1.3? 模型結果

對已選好的網絡進行hub點的尋找和蓄意攻擊后，每次選取不同的m值，便可得出相對應的最大相互連通的節點數g。這里以表1中網絡一的數據為例進行展示（m依次從1取到50，一共50個數）。

根據上述數據結合題目和實際操作分析，當網絡中各個節點的偏好概率p（i）大致相同時，說明從中選取的節點相對別的節點的重要度變化不大，對選取的節點進行攻擊后引起的級聯失效不能產生明顯的效果。

3.2? 遺傳算法優化模型

3.2.1? 模型思路

為了對模型進行改進，查閱眾多文獻資料[3]，得知BA優化模型存在耗費時間長，效率較低的問題，選取遺傳算法優化模型[4]作為所提及模型的改進。遺傳算法（Genetic Algorithm，GA）是一種通過模仿生物界特有的繁殖和基因傳遞模式而產生的啟發式算法[5]。其主要特點是直接對所確定的結構對象進行操作，不需要確定規則便可自動獲取和指導優化搜索空間，其可以自適應地調整搜索方向?，F在這一算法已經被廣泛應用于相互作用網絡的優化中，正是因為相互作用網絡數據具有高復雜度，最終結果不明確等特征，才使得利用遺傳算法這種非線性啟發式算法來完成高復雜度的數據計算成為可能。

對BA優化網絡確定節點重要度建立遺傳優化算法，以各個節點的度值作為適應度函數，以m作為染色體的長度，染色體上所攜帶的數值為節點編號，其通過染色體的復制、交叉、變異等功能操作進行迭代，并將每次的最優節點的組合保存下來，最后在各代的組合中取出最優的組合，以此作為hub點。

3.2.2? 模型建立

根據題目要求，建立啟發式算法中遺傳算法優化模型，其主要采用固定的交叉率、變異率和自定義的適應度函數，并且采用的是“輪盤賭”算法鎖定最優解。因為模型只是對傳統的遺傳算法進行了針對本題的改進，所以不對模型的基礎建立進行描述，只針對本題的遺傳算法優化模型的主要參數進行說明：將節點數m作為染色體的長度、節點的度值ki作為適應度函數、每條染色體上所攜帶的信息為要攻擊節點的編號，交叉率、變異率都是自定義數值，針對此問題取交叉率較小、變異率較大的情況，原因是當變異率較大時就會涵蓋更多的節點。

將每次迭代后的結果進行對比可以得出適應度值較大的節點編號，以此作為相應的網絡中相對重要的hub點。

3.2.3? 模型求解

通過編寫的MATLAB遺傳優化算法的源程序main4_1，并將相互作用網絡和m的數值等編寫到b4_1腳本文件中，運行后可以得到四個網絡的m和g的關系圖，這里同樣只展示如圖1所示的網絡一。

網絡一圖源程序代碼為：

global num

num=0;? ?%最大相互連通集團的節點數初始化

load（'data1.mat'）; %載入數據

tic;

g=[];

for m=1：50? ? ? ? ? ? ? ? ? ? ? ? ? %選擇m個節點進行攻擊

h1 = graph（A1）;? ? ? ? ? %h1為結構變量

h2 = graph（A2）;? ? ? ? ? %h2為結構變量

deg1= degree（h1）;? ? ? %將每個節點的度求出

deg2= degree（h2）;? ? ? %將每個節點的度求出

deg=[deg1;deg2];

%deg=deg1+deg2;

%提取度最大的節點

[x，da]=xlmax（deg，m）;? ? %取出m個最大值x為最大值向量，da為位置向量

% b=[];

% for e=1：2000

% b（e）=num;

%end

mian1_1（A1，A2，da）;? ? ? ?%對已經選出的節點進行攻擊

g（m）=num;

end

subplot（2，1，1）

plot（1：m，g，'bo-'）;

xlabel（'m'）;

ylabel（'g'）;

title（'m和g關系圖'）

legend（'網絡一均值關系曲線'）

根據圖1可知，網絡一中的節點的偏好概率p（i）相對較平均，圖像為一條直線，印證了表1的分析結果。

4? 模型評價

4.1? 模型優點

4.1.1? BA優化模型

根據題目要求及文獻資料的查詢，選定優化模型中的BA無標度網絡構造模型，BA模型將復雜的網絡的無標度特性，總結概括為增長和優先連接兩個簡潔明了的機制，便于進行研究和分析。BA模型開創性的把冪律度分布引入相互作用網絡中，網絡通過增添節點的方式在不斷增長，并且新節點總是擇優連接到高連通的節點上。經過實際操作可知，BA無標度網絡構造模型以偏好概率連接，能夠更加快速準確地找到所需的hub節點，其對于無標度網絡的帶有普遍意義的形成機理。

4.1.2? 遺傳算法優化模型

相對比于傳統算法而言，遺傳算法優化模型是從串集開始搜索，而不是從單個的解開始，其具有覆蓋范圍廣、從全局角度進行擇優的優勢。遺傳算法優化模型可以在更大的搜索區域內高效準確的獲得相比于傳統方法的最優解或者次優解，并且它所模擬的生物體的遺傳和變異可以讓問題求解的可控性和不可控性擁有更大的伸縮和操作空間，算法性能得到極大地提升。遺傳算法優化模型主要是用概率機制進行迭代，具有一定的隨機性，并且其擴展性比較強，容易和其他的算法進行結合。

4.2? 模型缺點

4.2.1? BA優化模型

根據選取的BA優化模型，在實際操作過程中也存在一定的局限，在尋找hub節點的過程，其存在計算量大，效率較低，所耗費的時間較長的問題。

4.2.2? 遺傳算法優化模型

對于后期選取的遺傳算法優化模型，其雖然有效解決了BA優化模型存在的時間和效率問題，但其本身也存在一定的缺點，遺傳算法優化模型的編程比較復雜，對于參數的依賴性較大，并且算法的并行機制的潛在能力沒有得到充分的利用。

5? 結? 論

本文首先介紹了級聯失效問題的研究背景，進而對模型的建立以及模型的時間和效率進行分析，接著按照對兩個問題的分析結果分別建立BA優化模型與遺傳算法模型，并用兩個模型分別對級聯失效相互作用網絡進行動態分析。根據結果可知，BA優化模型能更準確的找到所需的hub節點，但實際操作中效率較低，耗費時間較長;遺傳算法優化模型擴展性較強，算法總體性能較優，但編程過程較為復雜，對參數的依賴度也較高。故在處理級聯失效問題時，還要根據問題的實際情況選擇適合的算法，才能更好地對問題進行求解。

參考文獻：

[1] 李建春，吳雪麗，韓冰，等.一種對蓄意攻擊具有魯棒性的無標度網絡 [J].河南大學學報（自然科學版），2013，43（3）：324-327.

[2] 陳志龍，郭平，謝嵩源，等.關聯網絡中的級聯失效模型與分析 [J].后勤工程學院學報，2011，27（6）：87-91.

[3] 費凡.基于蛋白質相互作用網絡的信息通路提取 [D].廣州：華南理工大學，2017.

[4] 李慶，魏光村，高蘭，等.用于求解TSP問題的遺傳算法改進 [J].軟件導刊，2020，19（3）：116-119.

[5] 曲志堅，張先偉，曹雁鋒，等.基于自適應機制的遺傳算法研究 [J].計算機應用研究，2015，32（11）：3222-3225+3229.

作者簡介：齊小彤（1999.07—），女，漢族，山東濰坊人，本科在讀，研究方向：國際商務。