基于級聯(lián)失效的相互作用網(wǎng)絡(luò)的動態(tài)分析

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

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

關(guān)鍵詞：BA優(yōu)化模型;hub節(jié)點;遺傳算法優(yōu)化模型

中圖分類號：TP393.03? ? ? 文獻標(biāo)識碼：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? 引? 言

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

1? 問題背景

近幾年，相互作用網(wǎng)絡(luò)受到國內(nèi)外的廣泛關(guān)注。級聯(lián)失效的存在會導(dǎo)致整個相互依賴系統(tǒng)的崩潰。由于相互作用網(wǎng)絡(luò)的特點，會導(dǎo)致一個節(jié)點的失效被放大進而導(dǎo)致整個相互依賴系統(tǒng)的崩潰，故其研究對于電力-計算機網(wǎng)絡(luò)的結(jié)構(gòu)發(fā)展創(chuàng)新起著重要作用[1]。

2? 問題分析

2.1? 問題一分析

問題一：建立合適的優(yōu)化模型，對于選擇的m個節(jié)點進行攻擊，使得最終最大相互連通集團的節(jié)點數(shù)量g最少。并當(dāng)m為1～50個時，對4個相互作用網(wǎng)絡(luò)的g進行求解，利用MATLAB編程繪制出m與g的關(guān)系圖。

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

2.2? 問題二分析

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

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

3? 模型建立與求解

3.1? BA優(yōu)化模型

3.1.1? 模型建立

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

式中，ki為節(jié)點i的度數(shù)，j為所有已存在的節(jié)點。

建立BA優(yōu)化模型，基于BA無標(biāo)度網(wǎng)絡(luò)構(gòu)造模型中的構(gòu)造方法中的（2）可知新節(jié)點連接原網(wǎng)絡(luò)的方式，按照偏好概率往原網(wǎng)絡(luò)中添加一定數(shù)量的新節(jié)點，然后對網(wǎng)絡(luò)中添加的節(jié)點進行概率統(tǒng)計，統(tǒng)計后取出概率大的節(jié)點，以此概率作為節(jié)點的重要度評價指標(biāo)。

3.1.2? 模型求解

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

3.1.3? 模型結(jié)果

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

根據(jù)上述數(shù)據(jù)結(jié)合題目和實際操作分析，當(dāng)網(wǎng)絡(luò)中各個節(jié)點的偏好概率p（i）大致相同時，說明從中選取的節(jié)點相對別的節(jié)點的重要度變化不大，對選取的節(jié)點進行攻擊后引起的級聯(lián)失效不能產(chǎn)生明顯的效果。

3.2? 遺傳算法優(yōu)化模型

3.2.1? 模型思路

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

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

3.2.2? 模型建立

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

將每次迭代后的結(jié)果進行對比可以得出適應(yīng)度值較大的節(jié)點編號，以此作為相應(yīng)的網(wǎng)絡(luò)中相對重要的hub點。

3.2.3? 模型求解

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

網(wǎng)絡(luò)一圖源程序代碼為：

global num

num=0;? ?%最大相互連通集團的節(jié)點數(shù)初始化

load（'data1.mat'）; %載入數(shù)據(jù)

tic;

g=[];

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

h1 = graph（A1）;? ? ? ? ? %h1為結(jié)構(gòu)變量

h2 = graph（A2）;? ? ? ? ? %h2為結(jié)構(gòu)變量

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

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

deg=[deg1;deg2];

%deg=deg1+deg2;

%提取度最大的節(jié)點

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

% b=[];

% for e=1：2000

% b（e）=num;

%end

mian1_1（A1，A2，da）;? ? ? ?%對已經(jīng)選出的節(jié)點進行攻擊

g（m）=num;

end

subplot（2，1，1）

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

xlabel（'m'）;

ylabel（'g'）;

title（'m和g關(guān)系圖'）

legend（'網(wǎng)絡(luò)一均值關(guān)系曲線'）

根據(jù)圖1可知，網(wǎng)絡(luò)一中的節(jié)點的偏好概率p（i）相對較平均，圖像為一條直線，印證了表1的分析結(jié)果。

4? 模型評價

4.1? 模型優(yōu)點

4.1.1? BA優(yōu)化模型

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

4.1.2? 遺傳算法優(yōu)化模型

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

4.2? 模型缺點

4.2.1? BA優(yōu)化模型

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

4.2.2? 遺傳算法優(yōu)化模型

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

5? 結(jié)? 論

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

參考文獻：

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

[2] 陳志龍，郭平，謝嵩源，等.關(guān)聯(lián)網(wǎng)絡(luò)中的級聯(lián)失效模型與分析 [J].后勤工程學(xué)院學(xué)報，2011，27（6）：87-91.

[3] 費凡.基于蛋白質(zhì)相互作用網(wǎng)絡(luò)的信息通路提取 [D].廣州：華南理工大學(xué)，2017.

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

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

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