考慮社群結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)的級(jí)聯(lián)故障抵制模型

陸靖橋, 傅秀芬, 蒙在橋

(1.廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州，510006;2.中山大學(xué) 信息科學(xué)與技術(shù)學(xué)院，廣東 廣州，510006)

?

考慮社群結(jié)構(gòu)的復(fù)雜網(wǎng)絡(luò)的級(jí)聯(lián)故障抵制模型

陸靖橋1, 傅秀芬1, 蒙在橋2

(1.廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州，510006;2.中山大學(xué) 信息科學(xué)與技術(shù)學(xué)院，廣東 廣州，510006)

研究復(fù)雜網(wǎng)絡(luò)的級(jí)聯(lián)故障對(duì)評(píng)估網(wǎng)絡(luò)系統(tǒng)的穩(wěn)定性具有重大意義.在經(jīng)典的線性負(fù)載容量模型基礎(chǔ)上，通過(guò)探測(cè)網(wǎng)絡(luò)的社群結(jié)構(gòu)，有選擇地對(duì)社群邊界節(jié)點(diǎn)的容量附加二次容忍值，建立級(jí)聯(lián)故障抵制模型.在級(jí)聯(lián)故障仿真中，采用不同干擾策略對(duì)IEEE118標(biāo)準(zhǔn)電網(wǎng)、國(guó)內(nèi)現(xiàn)實(shí)電網(wǎng)等模擬故障過(guò)程.仿真結(jié)果表明，所建抵制模型通過(guò)對(duì)社群邊界節(jié)點(diǎn)的容量進(jìn)行二次擴(kuò)容，能以較小的成本提高網(wǎng)絡(luò)的穩(wěn)定性，同時(shí)發(fā)現(xiàn)社群邊界節(jié)點(diǎn)具備“防火墻”和“引爆點(diǎn)”的雙重功能.通過(guò)將單一網(wǎng)絡(luò)推廣到兩層耦合網(wǎng)絡(luò)，發(fā)現(xiàn)在成本可控下新模型對(duì)相依網(wǎng)絡(luò)的級(jí)聯(lián)故障依然具備較好的抵制能力，說(shuō)明本文所提模型具備一定的適應(yīng)性.

社群結(jié)構(gòu)； 復(fù)雜網(wǎng)絡(luò)； 級(jí)聯(lián)故障； 相依網(wǎng)絡(luò)

復(fù)雜網(wǎng)絡(luò)是互聯(lián)網(wǎng)、基礎(chǔ)物理設(shè)施網(wǎng)、社交網(wǎng)絡(luò)等的抽象，級(jí)聯(lián)故障研究是其中一項(xiàng)重要課題.以電力系統(tǒng)為例：電力系統(tǒng)是社會(huì)生產(chǎn)和人民生活的物質(zhì)基礎(chǔ)設(shè)施，關(guān)系著整個(gè)國(guó)民經(jīng)濟(jì)命脈.電力系統(tǒng)由大量超高壓設(shè)備和電子元件通過(guò)大規(guī)模的線路連接，電子元件在運(yùn)行中因各種因素的相互制約，導(dǎo)致電力系統(tǒng)的運(yùn)行過(guò)程異常復(fù)雜.現(xiàn)實(shí)的數(shù)次大規(guī)模停電事故，大多是由少數(shù)初始節(jié)點(diǎn)發(fā)生故障，然后通過(guò)節(jié)點(diǎn)的連接關(guān)系迅速地引起其他節(jié)點(diǎn)發(fā)生故障，連鎖效應(yīng)導(dǎo)致整個(gè)電力系統(tǒng)的崩潰，我們稱之為級(jí)聯(lián)故障[1-3].

復(fù)雜網(wǎng)絡(luò)的級(jí)聯(lián)故障機(jī)制和演化特性造成的復(fù)雜性使得級(jí)聯(lián)故障研究面臨著巨大挑戰(zhàn).文獻(xiàn)[2]首次引入容量和負(fù)載的概念，提出經(jīng)典的負(fù)載容量ML模型，指出一個(gè)或若干節(jié)點(diǎn)失效即可導(dǎo)致網(wǎng)絡(luò)的整體故障，網(wǎng)絡(luò)對(duì)級(jí)聯(lián)故障的抵制能力相當(dāng)弱.文獻(xiàn)[3]率先對(duì)無(wú)標(biāo)度網(wǎng)絡(luò)的故障進(jìn)行研究，發(fā)現(xiàn)無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)隨機(jī)故障魯棒、對(duì)惡意攻擊脆弱，并指出根源在于無(wú)標(biāo)度網(wǎng)絡(luò)中度分布的非均勻性.文獻(xiàn)[4]在研究歐洲電力網(wǎng)絡(luò)和路由器自治網(wǎng)絡(luò)故障基礎(chǔ)上，通過(guò)隨機(jī)交換節(jié)點(diǎn)邊的策略有效地提高網(wǎng)絡(luò)的魯棒性.文獻(xiàn)[5]研究加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)的級(jí)聯(lián)故障，其將節(jié)點(diǎn)的初始負(fù)載表示為節(jié)點(diǎn)度的函數(shù)形式.文獻(xiàn)[6-7]在構(gòu)建故障模型的初始負(fù)載時(shí)考慮節(jié)點(diǎn)本身以及鄰居節(jié)點(diǎn).文獻(xiàn)[8-9]從宏觀上研究了社團(tuán)對(duì)網(wǎng)絡(luò)整體抗毀性的影響.

目前的級(jí)聯(lián)故障研究，大多關(guān)注節(jié)點(diǎn)本身或節(jié)點(diǎn)的簡(jiǎn)單鄰居關(guān)系，已有的社群角度研究也較宏觀不夠細(xì)致.本文認(rèn)為故障節(jié)點(diǎn)引發(fā)的級(jí)聯(lián)故障是節(jié)點(diǎn)所處社群的內(nèi)外因共同作用的結(jié)果.隨著網(wǎng)絡(luò)性質(zhì)的深入研究，發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)具備社群性質(zhì)，即整個(gè)網(wǎng)絡(luò)由若干群構(gòu)成，群內(nèi)部的節(jié)點(diǎn)連接相對(duì)緊密，而群之間的連接相對(duì)稀疏[10-11].目前，社群分析已經(jīng)在生物學(xué)、物理學(xué)、計(jì)算機(jī)圖形學(xué)和社會(huì)學(xué)中廣泛應(yīng)用.同時(shí)，經(jīng)典的ML模型依據(jù)容忍系數(shù)對(duì)全部節(jié)點(diǎn)同等程度地提高容量，從而提高抵制故障的能力.基于此，本文所提的級(jí)聯(lián)故障CML模型(Commuinity with ML)考慮社群結(jié)構(gòu)對(duì)電網(wǎng)級(jí)聯(lián)故障的影響，CML模型中節(jié)點(diǎn)的社群內(nèi)外鄰居對(duì)節(jié)點(diǎn)施加不同權(quán)重的影響.

1　級(jí)聯(lián)故障抵制模型

1.1社群結(jié)構(gòu)

社群劃分一般采用分級(jí)聚類的方法，依據(jù)是否移除邊的思想大體分為凝聚法和分裂法兩大類[12-13].本中采用凝聚法中經(jīng)典的louvain社群劃分算法[14]，其劃分結(jié)果可靠且效率較高，滿足大數(shù)據(jù)集的要求.louvain算法采用式(1)模塊度指標(biāo)Q，通過(guò)不斷壓縮探測(cè)社群的規(guī)模，以達(dá)到社群的快速劃分目的.

(1)

其中，m為網(wǎng)絡(luò)總邊數(shù)，A為網(wǎng)絡(luò)的鄰接矩陣，Auw=1表示節(jié)點(diǎn)u和w有邊，否則無(wú)邊；ku為節(jié)點(diǎn)u度，cu為節(jié)點(diǎn)u所在社群，當(dāng)u和w位于同一社群，則δ(cu,cw)=1，否則為0.

本文對(duì)網(wǎng)絡(luò)的社群劃分過(guò)程分為兩個(gè)階段：

第一階段：初始化網(wǎng)絡(luò)的所有節(jié)點(diǎn)為N個(gè)社團(tuán)；計(jì)算節(jié)點(diǎn)u加入鄰居節(jié)點(diǎn)w所在社團(tuán)后的模塊度增量ΔQ，并將u加入ΔQ最大的社團(tuán)中，若ΔQ非正值，則節(jié)點(diǎn)u不移動(dòng)；遍歷所有節(jié)點(diǎn)判斷是否存在需移動(dòng)節(jié)點(diǎn)，若無(wú)則遍歷結(jié)束且開(kāi)始第二階段，否則重復(fù)上一步.

第二階段：依據(jù)第一階段結(jié)果，將社團(tuán)內(nèi)的全部節(jié)點(diǎn)視作一個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)之間的權(quán)值為原節(jié)點(diǎn)間的權(quán)值之和；迭代第一階段的模塊度增量的計(jì)算方法，直至網(wǎng)絡(luò)穩(wěn)定.

1.2建立級(jí)聯(lián)故障抵制模型

首先，本文定義社群邊界節(jié)點(diǎn)為連接2個(gè)或2個(gè)以上社群的節(jié)點(diǎn)，即社群邊界節(jié)點(diǎn)的鄰居節(jié)點(diǎn)至少分布在2個(gè)以上社群中(具體計(jì)算依據(jù)社群劃分后的節(jié)點(diǎn)社群屬性).文中所提級(jí)聯(lián)故障抵制模型中，節(jié)點(diǎn)的級(jí)聯(lián)故障的影響力來(lái)源節(jié)點(diǎn)社群內(nèi)外屬性共同作用的結(jié)果，依據(jù)節(jié)點(diǎn)的社群特性，賦予節(jié)點(diǎn)容量不同的社群容量附加值.考慮社群的特性，可以形象地將社群間的邊界節(jié)點(diǎn)視作“門(mén)”，則進(jìn)出不同的社群均需通過(guò)該“門(mén)”.基于此，在社群內(nèi)節(jié)點(diǎn)的容量保持不變的情況下，可以僅僅通過(guò)對(duì)社群邊界節(jié)點(diǎn)的容量附加二次容忍值，以提高抵制社群外(內(nèi))故障的能力，達(dá)到保護(hù)社群內(nèi)(外)部的節(jié)點(diǎn)，同時(shí)降低抵制成本.圖1是級(jí)聯(lián)故障發(fā)生時(shí)的負(fù)載重分配示意圖，圖中存在3個(gè)社群，節(jié)點(diǎn)u的5個(gè)鄰居節(jié)點(diǎn)中有2個(gè)位于其他社群中，直觀上我們發(fā)現(xiàn)節(jié)點(diǎn)u作為“防火墻”節(jié)點(diǎn)可以有效地阻隔社群外的故障干擾(u為社群邊界節(jié)點(diǎn))；換一個(gè)角度，若u作為“引爆點(diǎn)”卻可以引發(fā)社群內(nèi)外的大規(guī)模的級(jí)聯(lián)故障.在此，前文暫時(shí)主要考慮前一種情況，后一種情況在后文補(bǔ)充說(shuō)明.

圖1　考慮社群結(jié)構(gòu)的級(jí)聯(lián)故障的負(fù)載重分配

Fig.1Load redistribution of cascading failures considering community structure

在現(xiàn)實(shí)不同網(wǎng)絡(luò)中，節(jié)點(diǎn)負(fù)載一般與經(jīng)過(guò)該節(jié)點(diǎn)的最短路徑數(shù)目有關(guān)，因此可以定義節(jié)點(diǎn)u的初始負(fù)載為節(jié)點(diǎn)介數(shù)的函數(shù)式：

(2)

其中bu為節(jié)點(diǎn)u的介數(shù)，α>1為可調(diào)參數(shù)，控制著節(jié)點(diǎn)初始負(fù)載的強(qiáng)度.

節(jié)點(diǎn)u的容量Cu在經(jīng)典的ML模型中與初始負(fù)載Lu存在線性關(guān)系[15-17]，即Cu= (1+T)Lu.本文在ML模型基礎(chǔ)上依據(jù)節(jié)點(diǎn)的社群屬性對(duì)節(jié)點(diǎn)容量附加不同的二次容忍值，定義為

Cu=(1+T)Lu+S∑m∈ΓuLm.

(3)

其中，Γu為節(jié)點(diǎn)u的社群外鄰居節(jié)點(diǎn)的集合；常量1≥T≥0為網(wǎng)絡(luò)的容忍系數(shù)(相應(yīng)成本在本文也稱一次容忍值)，0≥S≥1為CML模型中新增的二次容忍系數(shù)，用以調(diào)節(jié)社群邊界節(jié)點(diǎn)的容量附加值幅度.顯然，T和S越大，網(wǎng)絡(luò)抵制故障能力越強(qiáng)，但抵制成本也越高.當(dāng)S=0，CML模型退化成經(jīng)典的ML模型.

一旦某節(jié)點(diǎn)發(fā)生故障，該節(jié)點(diǎn)的負(fù)載將重分配，定義故障節(jié)點(diǎn)u的β%的負(fù)載依照式(4)分配到鄰居節(jié)點(diǎn)上.

(4)

其中，Γu為故障節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)集合.因此，節(jié)點(diǎn)u故障后分配給節(jié)點(diǎn)w的負(fù)載為ΔLuw=βΠwLu，其中β用以調(diào)節(jié)故障節(jié)點(diǎn)傳遞給鄰居節(jié)點(diǎn)的負(fù)載大小.

故障節(jié)點(diǎn)的鄰居節(jié)點(diǎn)接收額外負(fù)載，若Lw+ΔLuw>Cw，則節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)w因總負(fù)載大于所能承受的容量，節(jié)點(diǎn)w級(jí)聯(lián)失效，相應(yīng)的負(fù)載進(jìn)一步迭代分配給w的鄰居節(jié)點(diǎn).

本文需要一個(gè)量化指標(biāo)用以評(píng)估級(jí)聯(lián)故障的崩潰規(guī)模.假設(shè)級(jí)聯(lián)故障的初始節(jié)點(diǎn)為u，級(jí)聯(lián)故障結(jié)束時(shí)的故障節(jié)點(diǎn)總數(shù)為CFu，則歸一化衡量網(wǎng)絡(luò)故障崩潰規(guī)模的指標(biāo)[18]為：

(5)

其中h為初始故障節(jié)點(diǎn)的集合.

2　仿真分析

2.1不同網(wǎng)絡(luò)的拓?fù)湫再|(zhì)

考慮到不同類型的網(wǎng)絡(luò)具備不同的拓?fù)浣Y(jié)構(gòu)，從而對(duì)模型的仿真結(jié)果產(chǎn)生影響，本文選擇了2類不同的電力網(wǎng)絡(luò)(IEEE標(biāo)準(zhǔn)電網(wǎng)、廣東某電網(wǎng))，以求仿真結(jié)果的普適性. 表1是網(wǎng)絡(luò)的拓?fù)湫再|(zhì).顯然，網(wǎng)絡(luò)直徑普遍較小，說(shuō)明網(wǎng)絡(luò)滿足“小世界”效應(yīng)[14，19].大部分網(wǎng)絡(luò)的模塊度值較高，說(shuō)明網(wǎng)絡(luò)的社群結(jié)構(gòu)明顯[14].同時(shí)，本文計(jì)算了各個(gè)網(wǎng)絡(luò)的社群邊界節(jié)點(diǎn)數(shù)目占全部節(jié)點(diǎn)的比例,IEEE標(biāo)準(zhǔn)電網(wǎng)為30.5%，廣東某電網(wǎng)為19.6%，這說(shuō)明社群邊界節(jié)點(diǎn)只占總節(jié)點(diǎn)的小部分，表明較ML模型等對(duì)全部節(jié)點(diǎn)擴(kuò)容以提高抵制故障能力而言，CML模型選取部分社群邊界節(jié)點(diǎn)擴(kuò)容可以有效地降低選取目標(biāo)節(jié)點(diǎn)數(shù)目.

表1　不同網(wǎng)絡(luò)的拓?fù)湫再|(zhì)

2.2IEEE標(biāo)準(zhǔn)電網(wǎng)仿真結(jié)果分析

運(yùn)行狀態(tài)的網(wǎng)絡(luò)在遭受干擾(或攻擊)的幾秒或幾分鐘內(nèi)，系統(tǒng)中某些節(jié)點(diǎn)的負(fù)載會(huì)產(chǎn)生較大幅度的變化，進(jìn)而連鎖破壞網(wǎng)絡(luò)系統(tǒng)的完整性.一般情況下，節(jié)點(diǎn)的重要性與自身的度值成正比，故本文攻擊網(wǎng)絡(luò)的度大節(jié)點(diǎn)模擬大干擾，攻擊度小節(jié)點(diǎn)模擬小干擾.其中，文中的干擾策略獲取的故障結(jié)果為通過(guò)100次不同仿真結(jié)果取均值，仿真平臺(tái)采用Python與Networkx(不失一般性，令α=1，β=100).

圖2所示為IEEE標(biāo)準(zhǔn)電網(wǎng)的級(jí)聯(lián)故障仿真結(jié)果.首先，如果曲線越傾斜于左下方，說(shuō)明網(wǎng)絡(luò)抵制故障的能力越強(qiáng)，且成本越低.顯然，IEEE標(biāo)準(zhǔn)電網(wǎng)在T和S均較小時(shí)，由于電網(wǎng)中全局節(jié)點(diǎn)的容量均很小，任意節(jié)點(diǎn)均沒(méi)有足夠的容量抵制額外的負(fù)載，故微小的擾動(dòng)也可以導(dǎo)致電網(wǎng)全部癱瘓.在T大于等于某一臨界值Tc時(shí)(下文統(tǒng)一稱之“關(guān)鍵閾值”)，即T≥Tc，即便不考慮S，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的容量已然足夠大，任意節(jié)點(diǎn)的故障均不會(huì)導(dǎo)致級(jí)聯(lián)故障，電網(wǎng)基本保持完整；而T

分析T

總的來(lái)說(shuō)，在可調(diào)的T和S參數(shù)下，小干擾對(duì)應(yīng)的安全閾值Tc較小，觸發(fā)的級(jí)聯(lián)故障規(guī)模能更快地收斂到穩(wěn)態(tài).安全閾值通常小于0.4，不區(qū)分網(wǎng)絡(luò)類型和干擾類型，級(jí)聯(lián)故障抵制的成本最大不會(huì)超過(guò)50%.

圖2　IEEE標(biāo)準(zhǔn)電網(wǎng)的級(jí)聯(lián)故障仿真結(jié)果

2.3社群邊界節(jié)點(diǎn)與內(nèi)部節(jié)點(diǎn)觸發(fā)級(jí)聯(lián)故障規(guī)模的比較

在前文中，本文僅對(duì)特定節(jié)點(diǎn)(最大度節(jié)點(diǎn)或最小度節(jié)點(diǎn))進(jìn)行級(jí)聯(lián)故障仿真并分析.為了更好地評(píng)估整體網(wǎng)絡(luò)的抵制級(jí)聯(lián)故障能力，本文同樣選擇IEEE標(biāo)準(zhǔn)電網(wǎng)對(duì)全部節(jié)點(diǎn)迭代仿真級(jí)聯(lián)故障，并將節(jié)點(diǎn)分成社群邊界節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)兩大類，對(duì)同一類中的節(jié)點(diǎn)導(dǎo)致的故障規(guī)模取均值，并定義CFdiff=CFbou/CFint為社群邊界節(jié)點(diǎn)平均故障規(guī)模與社群內(nèi)部節(jié)點(diǎn)平均故障規(guī)模的比值，結(jié)果如圖3所示.顯然，在同等參數(shù)條件下，CFdiff越大，相對(duì)社群內(nèi)部節(jié)點(diǎn)而言，社群邊界節(jié)點(diǎn)引發(fā)故障的能力越大.

圖3　社群邊界節(jié)點(diǎn)與內(nèi)部節(jié)點(diǎn)的平均故障規(guī)模比

Fig.3Difference of average failures between community boundary nodes and internal nodes

從圖3中觀察到，平均故障規(guī)模比值在參數(shù)T下具有“峰值現(xiàn)象”.首先，經(jīng)典的ML模型中，單純地提高節(jié)點(diǎn)的容量，雖然可以提高節(jié)點(diǎn)抵制故障的能力[2]，同時(shí)也會(huì)造成某些社群邊界節(jié)點(diǎn)成為“引爆點(diǎn)”，一旦故障發(fā)生在此類節(jié)點(diǎn)，破壞程度比一般節(jié)點(diǎn)嚴(yán)重.其次，“引爆點(diǎn)”存在閾值，T過(guò)高或過(guò)低均不會(huì)觸發(fā)，ML模型中T≈0.3.CML模型雖同樣存在該問(wèn)題，但是通過(guò)調(diào)節(jié)S，一定程度可以減弱“峰值現(xiàn)象”，從而降低社群邊界節(jié)點(diǎn)成為“引爆點(diǎn)”的可能性.分析大小干擾策略、成本和社群邊界與內(nèi)部節(jié)點(diǎn)的平均故障差，筆者認(rèn)為當(dāng)T∈(0，0.2)，S∈(0.5，0.8)，可以在成本可控的前提下，降低不同干擾造成的故障規(guī)模，同時(shí)降低社群邊界節(jié)點(diǎn)“引爆”的可能性(具體的T和S依據(jù)不同的網(wǎng)絡(luò)而定).最后，留意該處“峰值”與前文中網(wǎng)絡(luò)的安全閾值存在關(guān)系，即安全閾值對(duì)應(yīng)參數(shù)下，社群邊界節(jié)點(diǎn)的引發(fā)故障能力同樣也是最強(qiáng)的.

2.4級(jí)聯(lián)故障的網(wǎng)絡(luò)可視化

通過(guò)圖形化的方式，可以更好地幫助我們理解級(jí)聯(lián)故障的內(nèi)在連鎖機(jī)制.令T=0.1、S=0.85，圖4為攻擊IEEE標(biāo)準(zhǔn)電網(wǎng)的最大度節(jié)點(diǎn)(編號(hào)12，度為11，用紅色標(biāo)記)導(dǎo)致的級(jí)聯(lián)故障效果圖，黑色粗邊相連的節(jié)點(diǎn)表示已失效.從圖中可知，一旦某一節(jié)點(diǎn)失效，則會(huì)演化為“引爆點(diǎn)”，大規(guī)模地引發(fā)全局雪崩.

3　相依網(wǎng)絡(luò)中CML模型的推廣

為了驗(yàn)證本文所提CML模型的普適性，筆者將研究對(duì)象由單一網(wǎng)絡(luò)推廣到多層耦合網(wǎng)絡(luò)，即相依網(wǎng)絡(luò).目前不同系統(tǒng)之間的交互性大大增強(qiáng)，系統(tǒng)或網(wǎng)絡(luò)構(gòu)成的相依網(wǎng)絡(luò)對(duì)干擾的抵制相當(dāng)脆弱.文獻(xiàn)[20-21]提出一種相依網(wǎng)絡(luò)構(gòu)建方案，即對(duì)兩個(gè)具有相同節(jié)點(diǎn)數(shù)目的網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)間的節(jié)點(diǎn)一對(duì)一隨機(jī)連接，最后構(gòu)建的相依網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)為原先兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)之和，如圖5所示.依據(jù)該思想，本文選擇廣東某電網(wǎng)進(jìn)行耦合，將單個(gè)網(wǎng)絡(luò)耦合成兩層網(wǎng)絡(luò)，構(gòu)建相依網(wǎng)絡(luò).表2為耦合網(wǎng)絡(luò)的拓?fù)湫再|(zhì).由于耦合網(wǎng)絡(luò)的構(gòu)建采用節(jié)點(diǎn)一對(duì)一隨機(jī)連接，在一定程度上這種構(gòu)建方式不利于社群結(jié)構(gòu)的形成，故構(gòu)建的耦合網(wǎng)絡(luò)的社群結(jié)構(gòu)不明顯，模塊度較低，社群邊界節(jié)點(diǎn)數(shù)目較多.

圖4　IEEE標(biāo)準(zhǔn)電網(wǎng)的級(jí)聯(lián)故障可視化過(guò)程

圖5　多層耦合網(wǎng)絡(luò)構(gòu)建示例圖

節(jié)點(diǎn)數(shù)/個(gè)邊數(shù)/條網(wǎng)絡(luò)直徑平均度平均路徑/條模塊度社群數(shù)/個(gè)邊界節(jié)點(diǎn)數(shù)/個(gè)22449093.554.990.61712176

圖6為廣東耦合網(wǎng)絡(luò)的大干擾和小干擾仿真結(jié)果.從圖中可知干擾策略對(duì)耦合網(wǎng)絡(luò)的故障結(jié)果與單一網(wǎng)絡(luò)顯著不同.一方面，在可調(diào)參數(shù)范圍內(nèi)，耦合網(wǎng)絡(luò)的抵制故障性能更早地收斂到極大.ML模型下，耦合網(wǎng)絡(luò)更加脆弱，關(guān)鍵閾值Tc≈0.2成為“絕對(duì)”臨界點(diǎn)，網(wǎng)絡(luò)或崩潰或完整.另一方面，CML模型中，在可調(diào)參數(shù)下，隨著S的增大，故障規(guī)模逐漸減小.值得注意的一點(diǎn)，CML模型中，耦合網(wǎng)絡(luò)的關(guān)鍵閾值Tc不是近似的固定常量，即不同網(wǎng)絡(luò)的關(guān)鍵閾值均隨S的不同而不同，說(shuō)明CML模型對(duì)于耦合網(wǎng)絡(luò)同樣具備較好的抵制故障能力.耦合網(wǎng)絡(luò)的成本圖形同樣和前文中的單層網(wǎng)絡(luò)類似.

4　結(jié)論

復(fù)雜系統(tǒng)中結(jié)構(gòu)復(fù)雜、節(jié)點(diǎn)眾多，某一節(jié)點(diǎn)的失效會(huì)“雪崩式”干擾整個(gè)網(wǎng)絡(luò)系統(tǒng)，故障發(fā)生的快速性和全局性導(dǎo)致相關(guān)研究較難準(zhǔn)確把握.本文通過(guò)在IEEE標(biāo)準(zhǔn)電網(wǎng)和真實(shí)的電網(wǎng)引入介于宏觀和微觀的中觀特性—社群結(jié)構(gòu)，對(duì)于了解網(wǎng)絡(luò)的級(jí)聯(lián)故障具有積極作用.

圖6　耦合網(wǎng)絡(luò)的級(jí)聯(lián)故障仿真結(jié)果

Fig.6Cascading failures simulation results of coupled network

實(shí)驗(yàn)仿真表明，CML級(jí)聯(lián)故障抵制模型對(duì)單一網(wǎng)絡(luò)和耦合網(wǎng)絡(luò)均有較好的抵制故障能力，且可以降低經(jīng)典ML模型中社群邊界節(jié)點(diǎn)成為“引爆點(diǎn)”的可能性.社群邊界節(jié)點(diǎn)的特殊性決定其“抵制”又“級(jí)聯(lián)”的雙重特性，即抵制故障卻又能觸發(fā)級(jí)聯(lián)故障，一定程度取決于初始故障節(jié)點(diǎn)所處社群位置和合適的模型參數(shù).

[1] HOLME P, KIM B J, YOON C N, et al. Attack vulnerability of complex networks[J]. Physical Review E, 2002, 65(5): 056109.

[2] MOTTER A E, LAI Y C. Cascade-based attacks on complex networks[J]. Physical Review E, 2002, 66(6): 065102.

[3] CRUCITTI P, LATORA V, MARCHIORI M, et al. Error and attack tolerance of complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2004, 340(1): 388-394.

[4] SCHNEIDER C M, MOREIRA A A, ANDRADE J S, et al. Mitigation of malicious attacks on networks[J]. Proceedings of the National Academy of Sciences, 2011, 108(10): 3838-3841.

[5] WU Z X, PENG G, WANG W X, et al. Cascading failure spreading on weighted heterogeneous networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(05): P05013.

[6] WANG J W, RONG L L. A model for cascading failures in scale-free networks with a breakdown probability[J]. Physica A: Statistical Mechanics and its Applications, 2009, 388(7): 1289-1298.

[7] YU K, RONG L L, WANG J W. A new attack on scale-free networks based on cascading failures[J]. Modern Physics Letters B, 2009, 23(20): 2497-2505.

[8] 丁超， 姚宏， 杜軍，等. 基于社團(tuán)劃分的復(fù)雜網(wǎng)絡(luò)級(jí)聯(lián)抗毀攻擊策略[J]. 計(jì)算機(jī)應(yīng)用, 2014, 34(6): 1666-1670.

DING C, YAO H, DU J, et al. Cascading invulnerability attack strategy of complex network via community detection[J]. Journal of Computer Applications, 2014, 34(6): 1666-1670.

[9] 李浩敏, 杜軍, 彭興釗,等. 蓄意攻擊下一類多社團(tuán)網(wǎng)絡(luò)級(jí)聯(lián)抗毀性研究[J]. 計(jì)算機(jī)應(yīng)用, 2014, 34(4): 935-938.

LI M H, DU J, PENG X Z, et al. Research on cascading invulnerability of community structure networks under intentional-attack[J]. Journal of Computer Applications, 2014, 34(4): 935-938.

[10] FLAKE G W, LAWRENCE S, GILES C L, et al. Self-organization and identification of web communities[J]. Computer, 2002, 35(3): 66-70.

[11] ADAMIC L A, ADAR E. Friends and neighbors on the web[J]. Social Networks, 2003, 25(3): 211-230.

[12] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6): 066133.

[13] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.

[14] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008, 2008(10): P10008.

[15] ZHENG J F, YANG L X, GAO Z Y, et al. Cascading failures in congested scale-free networks[J]. International Journal of Modern Physics C, 2010, 21(08): 991-999.

[16] WANG J W. Modeling cascading failures in complex networks based on radiate circle[J]. Physica A: Statistical Mechanics and its Applications, 2012, 391(15): 4004-4011.

[17] MOTTER A E. Cascade control and defense in complex networks[J]. Physical Review Letters, 2004, 93(9): 098701.

[18]王建偉, 榮莉莉. 基于襲擊的復(fù)雜網(wǎng)絡(luò)上的全局相繼故障[J]. 管理科學(xué), 2009 (3): 113-120.

WANG J W, RONG L L. Universal cascading failures on complex networks based on attacks[J]. Journal of Managerment Science, 2009, 22(3): 113-120.

[19] OPSAHL T, AGNEESSENS F, SKVORETZ J. Node centrality in weighted networks: Generalizing degree and shortest paths[J]. Social Networks, 2010, 32(3): 245-251.

[20] BULDYREV S V, PARSHANI R, PAUL G, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature, 2010, 464(7291): 1025-1028.

[21] HUANG X, GAO J, BULDYREV S V, et al. Robustness of interdependent networks under targeted attack[J]. Physical Review E, 2011, 83(6): 065101.

A Cascading Failure Resisting Model in Complex Networks Considering Community Structure

Lu Jing-qiao1, Fu Xiu-fen1, Meng Zai-qiao2

(1. School of Computers, Guangdong University of Technology, Guangzhou 510006, China;2. School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510006, China)

Cascading failures in complex networks is of great significance for the stability assessment of complex networks. Based on the classical linear load and capacity model, a model resisting cascading failures is built by detecting the community structure of the networks and adding secondary tolerance value to community boundary nodes. In the process of cascading failures, different strategies are used to attack IEEE standard grids, domestic real grids. The simulation results show that the model can raise networks stability with lower cost by adding secondary tolerance value to community boundary nodes, finding that the community boundary nodes have the dual functions of "firewall" and "tipping point". By simulating the two-tier coupled networks except for single networks, the new model is also found abler to resist cascading failures in interdependent networks, which indicates that the proposed model has some flexibility.

community structure; complex networks; cascading failures; interdependent networks

2015- 08- 31

廣東省科技計(jì)劃項(xiàng)目(2012B091000173)；廣東省自然科學(xué)基金資助項(xiàng)目(10451009001004804)

陸靖橋(1989-)，男，碩士研究生，主要研究方向?yàn)閿?shù)據(jù)挖掘和復(fù)雜網(wǎng)絡(luò).E-mail:ljq5132@aliyun.com

10.3969/j.issn.1007- 7162.2016.05.005

TP391

A

1007-7162(2016)05- 0022- 06