考慮級聯(lián)失效影響的復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點識別

吳嫣媛，劉向軍

(華北電力大學(xué) 電氣與電子工程學(xué)院，北京 102206)

0 引 言

目前對復(fù)雜網(wǎng)絡(luò)節(jié)點重要性判斷方法都是針對具體問題提出的，存在一定的片面性和局限性，且會隨著網(wǎng)絡(luò)結(jié)構(gòu)的變化使識別結(jié)果存在一定誤差[1,3]。文獻(xiàn)[4,5]指出了這種缺點，進(jìn)而引入優(yōu)化理論來進(jìn)行關(guān)鍵節(jié)點識別，從攻擊的角度通過節(jié)點失效后網(wǎng)絡(luò)性能下降的方法來確定節(jié)點的重要性，以網(wǎng)絡(luò)性能最小為目標(biāo)采用禁忌搜索算法得到節(jié)點排序，使得識別方法適用于不同結(jié)構(gòu)與類型的網(wǎng)絡(luò)。但文獻(xiàn)[4,5]在構(gòu)建網(wǎng)絡(luò)抗毀性測度衡量網(wǎng)絡(luò)性能時，假設(shè)一個節(jié)點的失效不會影響其它節(jié)點，沒有考慮拓?fù)浣Y(jié)構(gòu)的改變導(dǎo)致網(wǎng)絡(luò)中物質(zhì)流的變化，不能很好地反映真實的節(jié)點重要程度。文獻(xiàn)[6-8]在計算節(jié)點失效后的網(wǎng)絡(luò)性能測度時引入了級聯(lián)失效過程，很好地切合了實際網(wǎng)絡(luò)的這種動態(tài)特征。因此在關(guān)鍵節(jié)點識別過程中計算魯棒性測度衡量網(wǎng)絡(luò)性能時，應(yīng)當(dāng)考慮網(wǎng)絡(luò)級聯(lián)失效過程。同時文獻(xiàn)[4,5]采用的禁忌搜索算法是一種基于單點搜索的元啟發(fā)式算法，且具有對初始解依賴性較強(qiáng)、多樣性不足等缺 點。

本文采用優(yōu)化算法進(jìn)行復(fù)雜網(wǎng)絡(luò)的關(guān)鍵節(jié)點識別，在此基礎(chǔ)上，考慮網(wǎng)絡(luò)的動態(tài)性引入級聯(lián)失效模型改進(jìn)網(wǎng)絡(luò)魯棒性測度，并針對禁忌搜索算法的缺點，改進(jìn)人工魚群算法作為節(jié)點序列構(gòu)造模型的求解算法，最后對比攻擊不同策略識別的關(guān)鍵節(jié)點在模擬網(wǎng)絡(luò)上的效果，驗證本文策略的有效性和優(yōu)越性。

1 級聯(lián)失效模型

受制于硬件成本，每個節(jié)點都具有給定的負(fù)載容納能力。最初，網(wǎng)絡(luò)處于穩(wěn)定狀態(tài)，其中每個節(jié)點的負(fù)載小于其容量。由于節(jié)點的故障，網(wǎng)絡(luò)受到了干擾，故障改變網(wǎng)絡(luò)中流量的平衡，負(fù)載將重新分配給其它節(jié)點，并可能進(jìn)一步導(dǎo)致其余節(jié)點過載，并足以引起整個系統(tǒng)故障。級聯(lián)失效反映的是網(wǎng)絡(luò)的動態(tài)特性，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的改變造成網(wǎng)絡(luò)數(shù)據(jù)流的重新分配，此過程描述如下[9,10]：

任何一個網(wǎng)絡(luò)可由圖G=(V,E)作抽象表示。V(G)是有限非空集，V中元素稱為G的頂點，N=|V|表示網(wǎng)絡(luò)中的節(jié)點數(shù)，E(G)是V(G)中頂點之間的邊的集合。在很多情況下，常直接用介數(shù)或?qū)閿?shù)稍加修正作為真實流量的近似值，網(wǎng)絡(luò)的實時流量如下

(1)

B(x)用于表示節(jié)點的流量。gij(x)定義為從節(jié)點i到j(luò)經(jīng)過節(jié)點x的最短路徑的數(shù)量。gij是從節(jié)點i到j(luò)的所有最短路徑數(shù)。此外，節(jié)點自身的數(shù)據(jù)量L也是總負(fù)載的重要組成部分。因此，節(jié)點x在時間t的負(fù)載可以表示為

(2)

其中，Lx(t)表示在時間t節(jié)點x的總負(fù)載，L為節(jié)點x的自身負(fù)載。由于大多數(shù)網(wǎng)絡(luò)節(jié)點的承載有限，將節(jié)點負(fù)載的上限定義為容量Cp，是節(jié)點過載和性能降低之前可以處理的最大負(fù)載，用時間t=0時的負(fù)載Lx(t)乘以容忍系數(shù)T表示

Cp=T·Lx(0),x=1,2,…,N

(3)

其中，T≥1。當(dāng)在時間t-1處節(jié)點x的流量負(fù)載超過Cp時，在時間t處節(jié)點將過載。以一簡單的隨機(jī)網(wǎng)絡(luò)為例說明這個過程，令N=100，隨機(jī)移除10個節(jié)點，負(fù)載變化如圖1所示。以44號節(jié)點為例，網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化后負(fù)載約為原始的1.597倍，倘若T小于這個數(shù)目，此節(jié)點過載失效，其余負(fù)載增大的節(jié)點同理，從而引發(fā)新一輪負(fù)載的變化。

圖1 隨機(jī)網(wǎng)絡(luò)中移除10個節(jié)點負(fù)載變化

2 基于級聯(lián)失效的魯棒性測度

網(wǎng)絡(luò)性能常用抗毀性測度衡量，通常被定義為i個節(jié)點被移除后，其最大連通分量的規(guī)模的變化[5]。文獻(xiàn)[11]考慮網(wǎng)絡(luò)級聯(lián)失效特點，采用級聯(lián)失效前后，最大連通分量節(jié)點數(shù)之比衡量網(wǎng)絡(luò)受損性能。本文結(jié)合級聯(lián)失效改進(jìn)網(wǎng)絡(luò)魯棒性測度。假使網(wǎng)絡(luò)G中有n個節(jié)點，標(biāo)號分別為1～n，則一個節(jié)點序列可表示為(k1,k2,…,kn)，是節(jié)點的一個排序。按照節(jié)點排序K={k1,k2,…,kn}去逐個攻擊網(wǎng)絡(luò)G中的節(jié)點，當(dāng)節(jié)點失效，執(zhí)行上一節(jié)模型描述的級聯(lián)失效過程。隨著節(jié)點的失效，該網(wǎng)絡(luò)在節(jié)點失效后的魯棒性R可以定義為

(4)

其中，C(i)表示網(wǎng)絡(luò)G中i個節(jié)點遭到攻擊，網(wǎng)絡(luò)負(fù)載重分配完畢或級聯(lián)失效過程完全完成后網(wǎng)絡(luò)的最大連通分量規(guī)模。R(G,K)越小，隨著節(jié)點失效下降得越快，說明網(wǎng)絡(luò)在這些節(jié)點失效后越容易遭到破壞，節(jié)點越重要，識別方法越準(zhǔn)確。

3 基于改進(jìn)人工魚群算法的關(guān)鍵節(jié)點識別

3.1 求解模型與基本人工魚群算法

基于優(yōu)化理論進(jìn)行關(guān)鍵節(jié)點識別，目標(biāo)是構(gòu)造出節(jié)點失效后網(wǎng)絡(luò)魯棒性R(G,K)下降最嚴(yán)重的節(jié)點序列K,R(G,K)越小，說明當(dāng)節(jié)點序列K失效時網(wǎng)絡(luò)越容易崩潰。因此其構(gòu)造方式可以視為一個優(yōu)化問題[4,5]。表示如下

(5)

其中，Set_K是所有節(jié)點序列構(gòu)成的集合。

(1)覓食行為：人工魚的感知距離范圍Visual內(nèi)隨機(jī)選擇一個新位置，向著對應(yīng)適應(yīng)度值更小的新位置移動。如果到達(dá)嘗試次數(shù)后仍不滿足前進(jìn)條件，執(zhí)行隨機(jī)行為。

(2)聚群行為：聚群行為是指每條魚在移動過程中趨向于相鄰伙伴的中心以避免過度擁擠的行為。當(dāng)前位置和中心位置對應(yīng)適應(yīng)度值Yi和Yc，nf為中心位置附近視野中的人工魚的數(shù)量，δ為擁擠因子；Yc值更小且Yc/nf<δYi，則前進(jìn)到中心位置。不滿足條件則執(zhí)行覓食行為。

(3)追尾行為：追尾行為表示每條人工魚在視覺范圍內(nèi)都朝著當(dāng)前的最佳方向移動。假設(shè)Xmin是當(dāng)前狀態(tài)Xi的鄰域內(nèi)最優(yōu)鄰居。如果Ymin

(4)隨機(jī)行為：隨機(jī)行為是在其視野中隨機(jī)選擇一個新狀態(tài)Xnext，然后在該方向上移動一步。實際上這是默認(rèn)行為。

(5)公告板：公告板用于記錄魚群中的最佳狀態(tài)Xnext。

算法完成后，最終公告板的值是系統(tǒng)的最佳解決方案。

3.2 算法性能改進(jìn)

AFSA存在一些缺陷，例如更容易陷入局部最優(yōu)值和缺乏多樣性等。為了彌補(bǔ)這一不足，對AFSA進(jìn)行改進(jìn)。

(1)初始解的構(gòu)造：本文通過引入佳點集的方法，優(yōu)化AFSA算法的初始人工魚群分布，提高AFSA算法的全局搜索性能。本質(zhì)上，優(yōu)化人工魚群的初始分布是為了更科學(xué)地表征解空間的特征，人工魚群體在解空間中的均勻分布是一種有效的策略，而隨機(jī)產(chǎn)生的人工魚群體在大多數(shù)情況下不能覆蓋解空間的所有狀況。由數(shù)論中的佳點集理論可知，佳點集的精度與空間維度無關(guān)，可以較好地適用于高維空間中的計算，同時，對于未知分布的對象，通過佳點集理論獲得的佳點集Ps(i)的偏差遠(yuǎn)遠(yuǎn)優(yōu)于通過隨機(jī)方法獲得的集合。因此，基于佳點集的特征，可以為群體智能算法中的群體分布提供更好的初始分布方案[14]。假設(shè)初始人工魚群數(shù)為s，在n維空間中選擇s點作為人工魚位置，作佳點集

Ps(i)={({r1*i},{r2*i},…,{rn*i}),i=1,2,…,s}

(6)

r稱為佳點，可由下式計算

(7)

其中，p為滿足(p-n)/2≥n的最小質(zhì)數(shù)，符號{a}表示數(shù)a的小數(shù)部分。由于本算法的解空間是節(jié)點序列的集合，將此佳點集映射到問題的可行域中，則第i個可行解的第k維的值為K(k,i)=[1+Ps(i)k(s-1)],i=1,2,…,s，符號[a]表示數(shù)a的整數(shù)部分。

(2)覓食行為的改進(jìn)：在迭代過程中，標(biāo)準(zhǔn)AFSA算法通過覓食行為來實現(xiàn)全局搜索。當(dāng)適應(yīng)度值提高時，算法的收斂速度降低。細(xì)菌覓食優(yōu)化算法(BFOA)中的趨化行為通過翻轉(zhuǎn)與游泳操作使細(xì)菌聚集在一個更有利的環(huán)境中，能增強(qiáng)覓食行為，進(jìn)入更大的搜索空間，并避免陷入局部最優(yōu)狀態(tài)。因此，采用BFOA算法的趨化行為對覓食行為進(jìn)行改進(jìn)[15]。與標(biāo)準(zhǔn)AFSA算法相比，趨化行為在處理覓食行為時增加了鄰域搜索的頻率和范圍。適應(yīng)度值在翻轉(zhuǎn)操作完成后進(jìn)行計算。當(dāng)?shù)玫降倪m應(yīng)度值更優(yōu)，人工魚將向該方向移動幾步，直到游泳步數(shù)Ns達(dá)到極限值Nsmax或適應(yīng)度值重合，否則執(zhí)行隨機(jī)行為。覓食行為在當(dāng)前位置停止覓食，并翻轉(zhuǎn)為另一條人工魚，當(dāng)所有人工魚完成翻轉(zhuǎn)，該過程完成。改進(jìn)的覓食行為可以加快收斂速度并增加潛在解。人工魚的位置i可以更新如下

(8)

其中，Step為實數(shù)。

(3)隨機(jī)行為的改進(jìn)：列維飛行是一種隨機(jī)游走策略，是一種典型的飛行、跳躍的步長可進(jìn)行變化的策略，從而使得搜索空間的結(jié)果更有效。因此，將列維飛行添加到自然啟發(fā)算法中，可確保算法的改進(jìn)。在AFSA中，隨機(jī)行為是一種變異策略，可以防止算法陷入局部最優(yōu)。在本節(jié)中，將列維飛行引入AFSA隨機(jī)行為。列維飛行可簡單近似為冪律行為，滿足此分布的隨機(jī)步長S可以通過Mantegna方法計算為

(9)

其中，u和v服從正態(tài)分布如下

u=N(0,σ2),v=N(0,1)

(10)

(11)

(12)

4 實驗仿真與分析

為驗證本文所提的關(guān)鍵節(jié)點識別方法的準(zhǔn)確性，本節(jié)在3種不同拓?fù)浣Y(jié)構(gòu)的典型復(fù)雜網(wǎng)絡(luò)及真實網(wǎng)絡(luò)中進(jìn)行仿真實驗，包括本文所改進(jìn)的優(yōu)化算法與文獻(xiàn)[5]中該領(lǐng)域已采用的優(yōu)化算法、標(biāo)準(zhǔn)AFSA算法對比，及不同節(jié)點識別方法的對比。改進(jìn)人工魚群算法最大嘗試次數(shù)50，最大迭代次數(shù)100，Nsmax取4，δ為0.618，人工魚每次移動的最大步長step取1，visual取0.1。標(biāo)準(zhǔn)AFSA相同參數(shù)取相同值。整體關(guān)鍵節(jié)點識別方法與傳統(tǒng)采用的基于度的衡量方法、文獻(xiàn)[16]綜合評價方法、文獻(xiàn)[17]方法在不同網(wǎng)絡(luò)結(jié)構(gòu)上進(jìn)行分析比較。3種典型網(wǎng)絡(luò)的生成參照文獻(xiàn)[18]。美國航空網(wǎng)絡(luò)是研究負(fù)載變化的重要網(wǎng)絡(luò)[8]，本文用于實驗的真實網(wǎng)絡(luò)采用美國航空網(wǎng)絡(luò)數(shù)據(jù)集[19]。復(fù)雜網(wǎng)絡(luò)的建立及后續(xù)的實驗均采用Matlab R2012a在Intel Core i7處理器配置下完成。

4.1 不同容忍系數(shù)下保護(hù)關(guān)鍵節(jié)點的網(wǎng)絡(luò)性能比較

本小節(jié)主要探討級聯(lián)失效模型所涉及的關(guān)鍵參數(shù)T下保護(hù)不同方法識別的關(guān)鍵節(jié)點對網(wǎng)絡(luò)抗毀性能的影響，具體關(guān)鍵節(jié)點識別方法的性能在后述小節(jié)進(jìn)行對比，本小節(jié)不作詳細(xì)敘述。采用不同方法在不同的容忍系數(shù)T下識別的節(jié)點序列中，保護(hù)前10%個節(jié)點，面對隨機(jī)攻擊的網(wǎng)絡(luò)性能如圖2所示。由網(wǎng)絡(luò)級聯(lián)失效模型可知，容忍系數(shù)T越大，則網(wǎng)絡(luò)承載級聯(lián)失效的能力越強(qiáng)。在4種網(wǎng)絡(luò)中比較總體性能，當(dāng)T不斷增大，由級聯(lián)失效引發(fā)的節(jié)點故障越少，網(wǎng)絡(luò)性能都有所提高。不保護(hù)任何節(jié)點的網(wǎng)絡(luò)性能曲線波動最大，基于優(yōu)化算法的曲線性能值最高，曲線最平穩(wěn)。這是由于不對任何節(jié)點進(jìn)行保護(hù)，當(dāng)隨機(jī)打擊的節(jié)點重要性較低，則對網(wǎng)絡(luò)的影響較小，否則網(wǎng)絡(luò)性能則受到較大影響，代表網(wǎng)絡(luò)性能的魯棒性值也就有所波動。使用優(yōu)化算法識別關(guān)鍵節(jié)點過程中考慮了級聯(lián)失效過程，保護(hù)對網(wǎng)絡(luò)影響較大的關(guān)鍵節(jié)點，也相當(dāng)于把引發(fā)較大級聯(lián)失效的節(jié)點保護(hù)起來，每一個T下達(dá)到的性能最高。文獻(xiàn)[17]方法雖然在仿真實驗中考慮了級聯(lián)失效動態(tài)特性，但關(guān)鍵節(jié)點識別仍是傳統(tǒng)方法，與其它方法一樣識別過程中不考慮級聯(lián)失效的影響，而忽略一些會引發(fā)較大級聯(lián)失效的關(guān)鍵節(jié)點，在隨機(jī)打擊下實驗曲線有所波動，小世界網(wǎng)絡(luò)中尤為明顯。無標(biāo)度網(wǎng)絡(luò)各曲線起點值明顯較高，對節(jié)點加以保護(hù)的各曲線均較為平穩(wěn)，也說明了當(dāng)無標(biāo)度網(wǎng)絡(luò)的少數(shù)關(guān)鍵節(jié)點保護(hù)起來以后，對隨機(jī)失效有較強(qiáng)的抗毀性。美國航空網(wǎng)絡(luò)的實驗曲線變化與無標(biāo)度網(wǎng)絡(luò)類似，曲線起點值高且曲線平穩(wěn)，面對隨機(jī)失效具有較強(qiáng)的魯棒性。

圖2 不同容忍系數(shù)T下保護(hù)關(guān)鍵節(jié)點的網(wǎng)絡(luò)性能比較

當(dāng)T到達(dá)一定值，級聯(lián)失效消失，而只有隨機(jī)攻擊引發(fā)的節(jié)點故障。以波動最大的小世界網(wǎng)絡(luò)為例進(jìn)行對比分析，基于優(yōu)化算法和文獻(xiàn)[16]綜合評價方法的曲線在T達(dá)到一定值時趨于穩(wěn)定，其它曲線波動較大，基于優(yōu)化算法的曲線值仍然最高，說明基于優(yōu)化算法的識別方法仍然比其它方法準(zhǔn)確；其次為文獻(xiàn)[16]的綜合評價方法，當(dāng)不考慮網(wǎng)絡(luò)級聯(lián)失效的特性，此種方法較為準(zhǔn)確。文獻(xiàn)[17]采用的評價指標(biāo)實質(zhì)計算上只涉及了度和介數(shù)兩種指標(biāo)，與基于度方法一樣曲線值波動較大，說明保護(hù)關(guān)鍵節(jié)點后的網(wǎng)絡(luò)性能得不到有效改善，識別的關(guān)鍵節(jié)點不太準(zhǔn)確。對性能最好的本文方法，和采用的傳統(tǒng)識別方法中性能最好的文獻(xiàn)[16]方法進(jìn)行詳細(xì)分析，要達(dá)到穩(wěn)定所需的T值，本文方法在隨機(jī)網(wǎng)絡(luò)中約為T=1.4，無標(biāo)度網(wǎng)絡(luò)中約為T=1.3，小世界網(wǎng)絡(luò)中約為T=1.5，美國航空網(wǎng)絡(luò)中約為T=1.3 達(dá)到的穩(wěn)定值分別約為0.75，0.85，0.8，0.9；文獻(xiàn)[16]方法對應(yīng)T值分別為1.5，1.35，1.6，1.5，穩(wěn)定值分別約為0.7，0.8，0.67，0.85，本文方法的網(wǎng)絡(luò)性能分別優(yōu)7.14%、6.25%、19.4%，5.88%；達(dá)到穩(wěn)定值所需T值越小，亦即要排除級聯(lián)失效影響需要對節(jié)點擴(kuò)充的容量較小，節(jié)省成本，保護(hù)關(guān)鍵節(jié)點能有效改善網(wǎng)絡(luò)性能。

4.2 改進(jìn)優(yōu)化算法性能分析

將本文改進(jìn)的AFSA算法與標(biāo)準(zhǔn)AFSA算法、文獻(xiàn)[5]的禁忌搜索算法于4種網(wǎng)絡(luò)中進(jìn)行關(guān)鍵節(jié)點識別，本小節(jié)主要通過對比比較算法的優(yōu)劣，驗證本方法改進(jìn)策略的有效性。在隨機(jī)網(wǎng)絡(luò)中選取T=1.3，無標(biāo)度網(wǎng)絡(luò)中選取T=1.2，小世界網(wǎng)絡(luò)中選取T=1.4，美國航空網(wǎng)絡(luò)中取T=1.2。在分析比較中，以第2節(jié)中魯棒性函數(shù)R為目標(biāo)函數(shù)進(jìn)行搜索識別。由于所用于實驗的網(wǎng)絡(luò)及算法的目標(biāo)函數(shù)是相同的，因而識別結(jié)果的差異主要受算法性能的影響。由圖3可以看出，基于3種優(yōu)化算法的識別結(jié)果有一定的相似度，在無標(biāo)度網(wǎng)絡(luò)中較為接近。在4種網(wǎng)絡(luò)結(jié)構(gòu)中基于改進(jìn)人工魚群算法的網(wǎng)絡(luò)性能下降最快，移除相同數(shù)目的節(jié)點網(wǎng)絡(luò)性能最低。其次為文獻(xiàn)[5]方法。本文方法的結(jié)果優(yōu)勢是明顯的，尤其是相較于標(biāo)準(zhǔn)AFSA算法而言。從優(yōu)化算法尋優(yōu)過程可知，各算法根據(jù)不同的節(jié)點序列排序使節(jié)點失效，依據(jù)適應(yīng)度值最小判斷出最優(yōu)的序列，因此最后得到的節(jié)點序列應(yīng)是失效后使網(wǎng)絡(luò)性能值最低的序列，但優(yōu)化算法不能遍歷所有情況，因此需要不斷尋求性能最佳的優(yōu)化算法。本文算法在這個過程中尋找的序列最為準(zhǔn)確，性能最好，這是由于AFSA算法相比于禁忌搜索算法而言具有并行處理能力，加之本文采用佳點集、趨化行為和列維飛行等改進(jìn)策略，得到了較好的搜索效果。標(biāo)準(zhǔn)AFSA算法識別的關(guān)鍵節(jié)點失效對網(wǎng)絡(luò)性能的影響比前兩種算法弱，在搜索次數(shù)相同的情況下，標(biāo)準(zhǔn)AFSA算法還得不到較優(yōu)的結(jié)果序列，作為相比于禁忌搜索算法本具有的優(yōu)勢也沒有體現(xiàn)出來，也說明了本文改進(jìn)策略的有效性。

圖3 移除不同優(yōu)化算法識別的關(guān)鍵節(jié)點后網(wǎng)絡(luò)性能比較

4.3 整體識別算法性能分析

為分析整體關(guān)鍵節(jié)點識別方法性能，采用移除排序靠前節(jié)點來分析網(wǎng)絡(luò)性能的變化。如圖4所示，由網(wǎng)絡(luò)性能的變化可以看出本文方法的前10%至20%左右的節(jié)點移除后，網(wǎng)絡(luò)連通性急劇下降，網(wǎng)絡(luò)效率下降明顯，3種典型拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)中，隨機(jī)網(wǎng)絡(luò)模型中移除27%節(jié)點，無標(biāo)度網(wǎng)絡(luò)中移除17%節(jié)點，小世界網(wǎng)絡(luò)中移除36%的節(jié)點，網(wǎng)絡(luò)性能即降低到0.1以下，其次為文獻(xiàn)[16]方法，使網(wǎng)絡(luò)性能即降低到0.1以下需分別移除41%、32%、52%節(jié)點，說明本文算法較為優(yōu)越。以無標(biāo)度網(wǎng)絡(luò)為例列出各方法得到的節(jié)點序列前10%的結(jié)果見表1，可以看出本文方法與其它方法識別結(jié)果差異較大。由于本文利用優(yōu)化算法進(jìn)行關(guān)鍵節(jié)點識別的過程中考慮了級聯(lián)失效的影響，所識別的引發(fā)較大級聯(lián)失效的幾個節(jié)點，在其它方法序列前10%節(jié)點中基本都不含有，當(dāng)這些重要節(jié)點被攻擊，同時引發(fā)級聯(lián)失效以最大化地破壞網(wǎng)絡(luò)，網(wǎng)絡(luò)性能急劇下降，其它3種傳統(tǒng)關(guān)鍵節(jié)點識別方法則沒有考慮網(wǎng)絡(luò)的這種動態(tài)特性。3種傳統(tǒng)方法中網(wǎng)絡(luò)性能下降最快的是文獻(xiàn)[16]方法，在隨機(jī)網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)中較為明顯，在無標(biāo)度網(wǎng)絡(luò)中3種傳統(tǒng)方法效果差別不大。這是由于文獻(xiàn)[16]方法考慮的多個指標(biāo)中包括網(wǎng)絡(luò)的整體連通性，更為全面，另兩種方法評價節(jié)點重要性時則沒有考慮。無標(biāo)度網(wǎng)絡(luò)少數(shù)關(guān)鍵節(jié)點往往也是度最大的節(jié)點，由表1可看出，3種方法識別的節(jié)點較為接近。

圖4 移除不同方法識別的關(guān)鍵節(jié)點后網(wǎng)絡(luò)性能比較

表1 各方法對無標(biāo)度網(wǎng)絡(luò)的節(jié)點識別排序部分結(jié)果

在美國航空網(wǎng)絡(luò)的實驗中，本文方法仍取得最優(yōu)的結(jié)果，使網(wǎng)絡(luò)性能降低至0.1以下，本文方法、文獻(xiàn)[16]、文獻(xiàn)[17]、基于度方法識別的關(guān)鍵節(jié)點需分別移除36%，57%，66%，71%的節(jié)點，對網(wǎng)絡(luò)造成崩潰，對關(guān)鍵節(jié)點的攻擊強(qiáng)度本文比其它方法分別要低36.8%，45.5%，49.3%，本文方法最為優(yōu)越，對關(guān)鍵節(jié)點識別也最為準(zhǔn)確。綜合上述分析，本文方法考慮網(wǎng)絡(luò)級聯(lián)效應(yīng)影響進(jìn)行關(guān)鍵節(jié)點識別，較其它傳統(tǒng)不考慮級聯(lián)效應(yīng)影響的方法更為準(zhǔn)確，更為貼合網(wǎng)絡(luò)實際情況，本文的關(guān)鍵節(jié)點識別方法在不同拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)中均具有較高的準(zhǔn)確性，能較好地適用，本文改進(jìn)人工魚群算法的策略也有效地提高了算法的性能。

5 結(jié)束語

如何更準(zhǔn)確地尋找網(wǎng)絡(luò)關(guān)鍵節(jié)點，對提高網(wǎng)絡(luò)穩(wěn)定性，預(yù)防網(wǎng)絡(luò)大規(guī)模故障至關(guān)重要。本文一方面引入網(wǎng)絡(luò)級聯(lián)失效模型，在分析網(wǎng)絡(luò)性能時，考慮節(jié)點級聯(lián)失效以貼近網(wǎng)絡(luò)的實際情況；另一方面改進(jìn)人工魚群算法，使得采用優(yōu)化理論進(jìn)行關(guān)鍵節(jié)點識別時更為高效準(zhǔn)確。通過在不同類型拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)與實際網(wǎng)絡(luò)上進(jìn)行實驗與分析，驗證了本文關(guān)鍵節(jié)點識別方法的有效性和優(yōu)越性。