相依網(wǎng)絡上基于相連邊的擇優(yōu)恢復算法?

吳佳鍵1) 龔凱1)2)3) 王聰4) 王磊1)

1)(西南財經(jīng)大學經(jīng)濟信息工程學院,成都 611130)

2)(西南財經(jīng)大學,互聯(lián)網(wǎng)金融創(chuàng)新及監(jiān)管協(xié)同創(chuàng)新中心,成都 611130)

3)(西南財經(jīng)大學,金融智能與金融工程四川省重點實驗室,成都 611130)

4)(四川師范大學,可視化計算與虛擬現(xiàn)實四川省重點實驗室,成都 610068)

(2017年11月24日收到;2018年1月26日收到修改稿)

1 引 言

現(xiàn)實世界中,基礎設施網(wǎng)絡(如通訊、交通、能源等)之間相互依賴、協(xié)同工作的情況既是一種普遍現(xiàn)象,也是社會各界的共識[1].對此,有研究者把這樣一些存在相互依賴關系的基礎網(wǎng)絡構成的系統(tǒng)稱為相依網(wǎng)絡[2?4].網(wǎng)絡間的相互依賴一方面可以提高整個系統(tǒng)的運轉效率[5],同時也帶來了意料之外的脆弱性和風險性[6].一旦這些關乎國家安全和民生的基礎網(wǎng)絡發(fā)生故障甚至癱瘓(例如2003年意大利“9.28”停電事故和2012年印度“7.31”停電事故),勢必會給社會經(jīng)濟活動和民生造成極其嚴重影響.因此,如何有效地應對和控制故障傳播,避免相依網(wǎng)絡發(fā)生結構性破碎,成為復雜網(wǎng)絡研究領域的新熱點問題之一[7,8].

根據(jù)復雜網(wǎng)絡理論[9],采用鑒別關鍵節(jié)點并實施預先保護是一種主流思想[10?13].對于相依網(wǎng)絡,國內(nèi)外研究者也相繼提出了預先保護少數(shù)節(jié)點免受失效影響的策略,以此來減緩或阻止故障在整個系統(tǒng)中的傳播與爆發(fā).例如從網(wǎng)絡中篩選出大度數(shù)或高介數(shù)節(jié)點作為不受耦合影響的自治節(jié)點[14],或是提前保護那些相連邊數(shù)和相依邊數(shù)都很高的節(jié)點[15],或是預先保護前5%的大度數(shù)或高Pagerank值的節(jié)點[16],文獻[17]則是基于拓撲距離[18]提出了局域保護等.不過,多數(shù)研究中的故障傳播和預先保護都是互不干涉的靜態(tài)過程.然而,瞬息萬變的真實世界更需要的是及時有效的動態(tài)應急措施,這樣的措施能夠在相依系統(tǒng)遭受故障時迅速做出響應,恢復失效節(jié)點,盡可能將損失降到最低,避免故障的升級擴大[19].

最近,文獻[20]提出了一種基于相依網(wǎng)絡的恢復模型.在該模型中,級聯(lián)失效階段和恢復節(jié)點階段是有序交替的動態(tài)過程,其恢復的基本思想是通過定義共同邊界節(jié)點(mutual boundary nodes),在每輪恢復階段找出符合條件的共同邊界節(jié)點并以一定比例實施恢復,進而遏制故障在相依網(wǎng)絡上的擴散.當前的做法是根據(jù)隨機概率進行選擇,簡稱隨機恢復算法.這種方法雖然簡單直觀,但顯然存在很大的提升空間.考慮到現(xiàn)實社會中資源有限等客觀因素的限制,系統(tǒng)遭受故障時無論采取何種應急措施都將面臨擇優(yōu)的難題[21?23].本文利用共同邊界節(jié)點在極大連通網(wǎng)絡(giant component,GC)內(nèi)外的連接邊數(shù)計算定義邊界節(jié)點的重要性,提出一種基于相連邊的擇優(yōu)恢復(preferential recovery based on connectivity link,PRCL)算法.仿真結果顯示,PRCL算法能夠很好地鑒別恢復過程中具有重要作用的少數(shù)邊界節(jié)點,有效且及時地遏制故障在網(wǎng)絡間的級聯(lián)傳播.本文結構如下:介紹共同邊界節(jié)點的定義,詳述相依網(wǎng)絡上的恢復模型;提出共同邊界節(jié)點在極大連通網(wǎng)絡內(nèi)外連接邊數(shù)的量化指標,并根據(jù)PRCL算法公式計算求出每輪恢復階段中節(jié)點的邊界重要指數(shù),按照比例實施擇優(yōu)恢復;通過隨機網(wǎng)絡(ER)和無標度網(wǎng)絡(SF)構建的ER-ER(SF-SF/ER-SF/SF-ER)相依網(wǎng)絡上的級聯(lián)仿真,分別對隨機、度數(shù)中心性和局域中心性為基礎的恢復算法的實施效果進行比較分析;討論了PRCL算法的參數(shù)值.實驗結果表明,PRCL算法具備恢復能力強、起效時間早且迭代步數(shù)少的優(yōu)勢,能夠在不同的相依網(wǎng)絡上找到對結構連通性具有重要影響作用的少數(shù)邊界節(jié)點,有效地阻止故障在網(wǎng)絡間的級聯(lián)擴散,從而避免相依網(wǎng)絡發(fā)生結構性破碎.

2 相依網(wǎng)絡的恢復模型

最初,孤立網(wǎng)絡上的恢復模型通常具備自發(fā)性恢復機制[24],基本思想是每隔一段時間,網(wǎng)絡中滿足條件的失效節(jié)點進行自我恢復.最近,Muro等[20]通過定義相依網(wǎng)絡中的共同邊界節(jié)點,開創(chuàng)性地提出一種適用于相依網(wǎng)絡的恢復模型(本文簡稱恢復模型).該模型創(chuàng)新之處主要體現(xiàn)在兩方面:第一,能夠被恢復的節(jié)點只能是符合條件的共同邊界節(jié)點;第二,相依網(wǎng)絡的級聯(lián)失效階段和恢復節(jié)點階段不是孤立的靜態(tài)過程,而是有序交替的動態(tài)過程.

在恢復模型中,共同邊界節(jié)點是指:如果網(wǎng)絡A中的失效節(jié)點ai與極大連通網(wǎng)絡GCA的拓撲距離l=1(即節(jié)點ai與GCA中任意節(jié)點存在連接關系),并且對應的耦合節(jié)點bj與其極大連通網(wǎng)絡GCB的拓撲距離也同樣滿足l=1,那么把這對節(jié)點(ai,bj)稱為共同邊界節(jié)點,見圖1.恢復模型中只有滿足共同邊界條件的失效節(jié)點才能作為候選恢復目標,這樣的定義具有現(xiàn)實性和合理性:第一,現(xiàn)實世界中,當基礎設施網(wǎng)絡發(fā)生故障時,受時空等物理條件的限制,通常都是優(yōu)先搶修正常區(qū)域周邊的設施單位,由近到遠逐步恢復;第二,如果候選恢復目標不是共同邊界節(jié)點,那么就很有可能因其對應的耦合節(jié)點脫離極大連通網(wǎng)絡而反復失效,導致這樣的恢復行為沒有實際意義.

圖1 相依網(wǎng)絡的共同邊界節(jié)點,節(jié)點a2對應的耦合節(jié)點b2與GCB的拓撲距離l=2,所以(a2,b2)不是共同邊界節(jié)點Fig.1.Schematic demonstration of the mutual boundary of the GCs.Since the topological distance between b2and GCBis equal to 2,the point of(a2,b2)is not mutual boundary nodes.

歸納起來,恢復模型是由初始化、級聯(lián)失效和實施恢復等三個階段構成.初始階段,隨機選擇網(wǎng)絡A中比例等于1?p的節(jié)點發(fā)生故障,p是指初始正常節(jié)點比例,失效是指故障節(jié)點連同自身相連邊和相依邊一并從網(wǎng)絡中移除.根據(jù)典型相依網(wǎng)絡模型的級聯(lián)規(guī)則[2],當節(jié)點滿足以下條件之一就會失效:不屬于極大連通網(wǎng)絡或對應的耦合節(jié)點故障.在級聯(lián)失效階段,當網(wǎng)絡A碎裂成多個網(wǎng)絡時,不屬于極大連通網(wǎng)絡GCA的節(jié)點隨即失效,這些故障節(jié)點通過相依邊的作用導致網(wǎng)絡B中的耦合節(jié)點也發(fā)生級聯(lián)故障,進而改變網(wǎng)絡B的連通性,且不屬于GCB的節(jié)點失去功能.反過來,網(wǎng)絡B中失效節(jié)點同樣通過相依邊的耦合關系造成網(wǎng)絡A中的節(jié)點失效,進一步導致網(wǎng)絡A破碎.重復迭代直至沒有新增失效節(jié)點.顯然,初始階段和級聯(lián)失效階段正是典型相依網(wǎng)絡的動力學過程.在此,引入恢復機制.簡單地說,在迭代步數(shù)n>0時,網(wǎng)絡A將自身故障傳遞到網(wǎng)絡B.接著,網(wǎng)絡B因其受到耦合關系的牽連,導致網(wǎng)絡內(nèi)某些節(jié)點脫離GCB,同時又造成網(wǎng)絡A上的耦合節(jié)點失效.但不同的是,在網(wǎng)絡B將故障傳遞回網(wǎng)絡A之前,恢復機制會介入并找出當前的共同邊界節(jié)點,按比例實施恢復.實施結束后,網(wǎng)絡B繼續(xù)將故障傳遞回網(wǎng)絡A,見示意圖2.

圖2 相依網(wǎng)絡的恢復模型Fig.2.Schematic model of the failures-recovery in interdependent networks.

具體邏輯流程如下.

I.Stagenin A

1)如果網(wǎng)絡A中正常節(jié)點ai的耦合節(jié)點bi在n?1步時已失效,則ai失效;

2)當前已脫離極大連通網(wǎng)絡GCA的節(jié)點都失效.

II.Stagenin B

3)如果網(wǎng)絡B中正常節(jié)點bj的耦合節(jié)點aj在步驟2)失效,則bj失效;

4)當前已脫離極大連通網(wǎng)絡GCB的節(jié)點都失效.

III.Recovering

5)找出所有的共同邊界節(jié)點,按照一定比例λ(這里指恢復過程中邊界節(jié)點的恢復比例)進行選擇恢復,當前采取的做法是按隨機概率恢復;凡是被恢復的節(jié)點,其自身與極大連通網(wǎng)絡內(nèi)的所有連邊一并恢復,并且恢復與本輪其他被恢復節(jié)點的原有連邊;

6)重復步驟1)—5),一旦當前網(wǎng)絡達到穩(wěn)態(tài)(不再新增失效節(jié)點),整個恢復模型的動力學過程終止,此時網(wǎng)絡是剩余的極大連通網(wǎng)絡.

3 基于相連邊的擇優(yōu)恢復算法

在恢復模型中,隨機恢復算法之所以有效是因為共同邊界特性:邊界節(jié)點與極大連通網(wǎng)絡的拓撲關系確?；謴托袨槟軌蜃畲蟪潭鹊卦鰪娛Ｓ嗑W(wǎng)絡的結構魯棒性,同時,利用相依關系的對稱性,實施恢復又可以最大限度地避免被恢復節(jié)點受相依邊的耦合作用導致無效恢復.然而,從現(xiàn)實角度考慮,相依系統(tǒng)遭受故障時無論采取何種應急措施都會面臨選擇誰實施恢復的難題,這是由資源有限等客觀因素所決定的.例如真實世界中防控疾病傳播要重點關注高危人群[25]、阻斷互聯(lián)網(wǎng)謠言散播需要重點監(jiān)管意見領袖[26,27]等.所以,采取擇優(yōu)算法相比隨機方法而言,具備更廣的適用性和更強的指導性.

一般地,擇優(yōu)選擇首先要考慮的是怎樣合理地利用結構特征對節(jié)點進行有效鑒別從而發(fā)現(xiàn)重要節(jié)點[28].受文獻[29]的啟發(fā),可以發(fā)現(xiàn)邊界節(jié)點的相連邊在恢復過程中存在兩種情況:與當前極大連通網(wǎng)絡內(nèi)的正常節(jié)點存在原有連接(見圖3藍色虛線),或是與當前極大連通網(wǎng)絡外的失效節(jié)點存在原有連接(見圖3黑色虛線).仔細分析,邊界節(jié)點與極大連通網(wǎng)絡內(nèi)相連邊數(shù)量的多少,意味著恢復該節(jié)點后的極大連通網(wǎng)絡內(nèi)節(jié)點平均度的增減變化,而已知節(jié)點平均度與網(wǎng)絡魯棒性呈正相關[30,31].另一方面,邊界節(jié)點與極大連通網(wǎng)絡外的相連邊數(shù)量又意味著該節(jié)點在原始網(wǎng)絡上的結構連通性或是局限性[32],這類連邊數(shù)越多,說明后續(xù)恢復階段的候選目標數(shù)就越多,重要邊界節(jié)點被選中的潛在性也就越高.可想而知,恢復模型上邊界節(jié)點的重要性既依賴于該節(jié)點與極大連通網(wǎng)絡內(nèi)的連接關系,也依賴與極大連通網(wǎng)絡外的連接關系,所以,衡量邊界節(jié)點重要性時需要綜合考慮上述兩類相連邊以及它們在恢復作用上的比重關系,這不同于以往研究工作將連邊數(shù)最多的節(jié)點簡單地定義成重要節(jié)點的思想[33].本文利用邊界節(jié)點在極大連通網(wǎng)絡內(nèi)外的連接邊數(shù)計算邊界節(jié)點的重要性,提出PRCL算法.這里用符號I代表恢復模型中邊界節(jié)點的邊界重要指數(shù).PRCL算法的具體步驟如下.

1)迭代步數(shù)n時,在恢復階段找出相依網(wǎng)絡上所有的共同邊界節(jié)點.

2)遍歷網(wǎng)絡A上的邊界節(jié)點,按照如下規(guī)則計算求出每個節(jié)點的邊界重要指數(shù):

①計算邊界節(jié)點vi與當前極大連通網(wǎng)絡GCA的失效連邊數(shù),即邊界節(jié)點vi與極大連通網(wǎng)絡內(nèi)正常節(jié)點存在原有連邊的數(shù)量,用符號表示;

②計算邊界節(jié)點vi與極大連通網(wǎng)絡GCA外失效節(jié)點存在原有連邊的數(shù)量,用符號表示;3

③根據(jù)(1)式求出節(jié)點vi的邊界重要指數(shù),

式中參數(shù)β(β∈[0,1])代表兩類相連邊在計算邊界節(jié)點重要性時的比重關系.為了便于計算,用參數(shù)f=β/(1?β)來量化這兩類相連邊的比重關系.如果參數(shù)f等于1,即β取值等于0.5時,說明極大連通網(wǎng)絡內(nèi)的相連邊與極大連通網(wǎng)絡外的相連邊就衡量邊界節(jié)點的重要性而言同樣重要.有關參數(shù)討論請見后文的算法分析.在此,簡單且不失一般性,本文參數(shù)f默認值為2.

3)網(wǎng)絡A遍歷結束后,按照恢復比例λ,根據(jù)邊界重要指數(shù)進行降序恢復.一旦網(wǎng)絡A的邊界節(jié)點恢復正常,網(wǎng)絡B對應的耦合節(jié)點也立刻恢復.見圖3.

圖3 基于相連邊的擇優(yōu)恢復過程,(a)節(jié)點對(a1,b1)和(a2,b2)是兩組共同邊界節(jié)點,節(jié)點a1和a2都有6條相連邊,其中節(jié)點a1的kgc=3且kngc=3;(b)依據(jù)計算公式可知I(a1)=9/3,同理得知I(a2)=8/3,因而優(yōu)先恢復a1和耦合節(jié)點b1,然后修復(a1,b1)的相依邊以及與其他正常節(jié)點的連接關系Fig.3.Schematic illustration of the PRCL strategy:(a)Two pairs of mutual boundary nodes((a1,b1)and(a2,b2))are shown;(b)by counting the number of first-type and second-type connectivity links of node a1,kgc=3 and kngc=3,after calculating the boundary importance index with f=2,then I(a1)=9/3;in the same way,I(a2)=8/3,so two interdependent nodes a1and b1are preferential repaired,all their connections with the GCs and all links between reactivated failure nodes are restored.

為了比較分析PRCL算法的恢復效果,以經(jīng)典復雜網(wǎng)絡理論中常見的三種中心性指標為基準算法:隨機(random,RR)、度數(shù)中心性(degree,PRD)和局域中心性(local,PRL).這里,RR算法是指通過隨機方式選取邊界節(jié)點進行恢復,PRD算法是指優(yōu)先選取大度的邊界節(jié)點進行恢復[34],PRL算法是指根據(jù)邊界節(jié)點的原有鄰居拓撲關系優(yōu)先選擇局域中心性最高的邊界節(jié)點進行恢復[35].

4 仿真結果與分析

為了檢驗恢復算法的有效性,本文利用ER隨機網(wǎng)絡[36]和無標度網(wǎng)絡[37]構建同構相依網(wǎng)絡和異構相依網(wǎng)絡.這四類網(wǎng)絡(ER-ER/SF-SF/ERSF/SF-ER)表征相依網(wǎng)絡不同的結構特征,能夠更全面地評估PRCL算法的恢復效果.參照文獻[20]的取值和方法,子網(wǎng)絡節(jié)點規(guī)模等于10000,相依網(wǎng)絡規(guī)模N=20000,節(jié)點平均度?k?=5.根據(jù)以上參數(shù),利用基于滲流理論[38]的隨機故障模型進行仿真模擬,數(shù)據(jù)均為獨立重復104次的平均值.

圖4描述的是邊界節(jié)點恢復比例λ=3%時,存在極大連通網(wǎng)絡的概率隨初始正常節(jié)點比例的變化情況.橫坐標p表示初始時網(wǎng)絡正常節(jié)點的比例,縱坐標P∞表示相依網(wǎng)絡遭受隨機故障后存在極大連通網(wǎng)絡的概率[2].本文認定相依網(wǎng)絡遭受故障但經(jīng)修復達到穩(wěn)態(tài)后,如果子網(wǎng)絡A的剩余極大連通網(wǎng)絡節(jié)點數(shù)NGCA>2,并且子網(wǎng)絡B的剩余極大連通網(wǎng)絡的節(jié)點數(shù)NGCB>2,則視為存在;否則視作崩潰.在此,P∞的具體計算是統(tǒng)計存在極大連通網(wǎng)絡(NGCA=NGCB>2)的試驗次數(shù)占總試驗次數(shù)的比例.圖示方塊(圓圈/菱角/十字)表示采用PRCL算法(PRD/PRL/RR)的恢復情況,P∞值越大說明網(wǎng)絡魯棒性越強,也就說明恢復算法在相同p值時的恢復效果越好.觀察圖4(a)所代表的ER-ER網(wǎng)絡可見,PRCL算法實施恢復后的效果十分突出,其次是PRD算法和PRL算法,相比擇優(yōu)選擇的結果來看,RR算法的恢復效果最差.進一步觀察圖4(b)、圖4(c)和圖4(d),可見PRCL算法在異構或是同構的相依網(wǎng)絡上均表現(xiàn)出非常明顯的優(yōu)勢.而當λ取值等于5%(圖5)和10%(圖6)的情況時,PRCL算法在恢復效果上的有效性仍然保持不變.甚至在λ取值過大時(λ=30%,圖7),較高的恢復比例會造成恢復節(jié)點數(shù)太多從而模糊算法間的效果差異,例如PRD和PRL在多數(shù)情況下就因交織糾纏而難以辨別,但即便如此,PRCL算法也依然表現(xiàn)出微弱性優(yōu)勢.綜上可知,PRCL算法能夠更好地鑒別相依網(wǎng)絡恢復階段具有重要作用的少數(shù)邊界節(jié)點,有效地遏制住故障在網(wǎng)絡間的級聯(lián)擴散.

圖4 邊界節(jié)點恢復比例λ=3%時,存在極大連通網(wǎng)絡的概率P∞隨初始網(wǎng)絡正常節(jié)點比例p的變化Fig.4.Probability of existence of the giant connected component,P∞,as a function of p with λ =3%.

圖8 比較分析的是PRCL算法與其他恢復算法在迭代步數(shù)(number of iteration steps,NOI)方面的表現(xiàn)情況.NOI表示遭受隨機故障時相依網(wǎng)絡達到穩(wěn)態(tài)所經(jīng)歷的迭代步數(shù)[2,39].對于恢復算法而言,圖中迭代步數(shù)(NOI)峰值是指實施恢復后網(wǎng)絡達到穩(wěn)態(tài)時所需的最大迭代步數(shù).圖8(a)中,PRCL算法的NOI峰值最小(NOI為6.803),低于PRD(NOI為6.962)、PRL(NOI為7.113)和RR算法(NOI為7.322),同樣的情況也出現(xiàn)在其他相依網(wǎng)絡上,如圖8(b)、圖8(c)和圖8(d)所示.直觀可見,相比其他算法,PRCL算法能夠在最少迭代步數(shù)內(nèi)有效地控制住故障在相依網(wǎng)絡上的傳播擴散.另一方面,觀察四條曲線發(fā)現(xiàn),PRCL算法在NOI峰值處的正常節(jié)點比例p的數(shù)值明顯低于PRD,PRL和RR算法,例如在圖8(a),PRCL算法NOI峰值對應的pNOI=0.43,低于PRD(pNOI=0.435),PRL(pNOI=0.435)和RR算法(pNOI=0.45),這種優(yōu)勢在其他相依網(wǎng)絡中(圖8(b)、圖8(c)、圖8(d))同樣存在.可見,PRCL算法施加于相依網(wǎng)絡后發(fā)揮恢復作用的起效時間最早,具有很強的及時性.整體來看,PRCL算法在不同的相依網(wǎng)絡上都表現(xiàn)出起效時間早且迭代步數(shù)少的優(yōu)勢,因而能夠及時地阻斷故障在網(wǎng)絡間的級聯(lián)擴散.

圖5 邊界節(jié)點恢復比例λ=5%時,存在極大連通網(wǎng)絡的概率P∞隨初始網(wǎng)絡正常節(jié)點比例p的變化Fig.5.Probability of existence of the giant connected component,P∞,as a function of p with λ =5%.

圖6 邊界節(jié)點恢復比例λ=10%時,存在極大連通網(wǎng)絡的概率P∞隨初始網(wǎng)絡正常節(jié)點比例p的變化Fig.6.Probability of existence of the giant connected component,P∞,as a function of p with λ =10%.

圖7 邊界節(jié)點恢復比例λ=30%時,存在極大連通網(wǎng)絡的概率P∞隨初始網(wǎng)絡正常節(jié)點比例p的變化Fig.7.Probability of existence of the giant connected component,P∞,as a function of p with λ =30%.

圖8 迭代步數(shù)NOI隨初始正常節(jié)點比例p的變化,邊界節(jié)點恢復比例λ=5%Fig.8.The number of iteration steps(NOI)in the steady state as a function of p with λ=5%.

根據(jù)文獻[20]中的分析可知,施加恢復算法后相依網(wǎng)絡存在三個相圖區(qū)域:崩潰、恢復和未崩塌.當給定恢復比例λ時,三個區(qū)域實質(zhì)上對應的是正常節(jié)點比例p的三個區(qū)間.崩潰區(qū)域是指正常節(jié)點比例p太低造成整個系統(tǒng)徹底破碎,這種情況已經(jīng)超出恢復算法的有效范圍;恢復區(qū)域是指受惠于恢復算法的有效作用,網(wǎng)絡遭受故障后結構可能有破損但不會完全崩塌;未崩塌區(qū)域是指正常節(jié)點比例p太高,這種狀態(tài)下即便不采取恢復,網(wǎng)絡也不會出現(xiàn)結構性崩塌.顯而易見,在恢復區(qū)域內(nèi),網(wǎng)絡結構完整程度的差異在一定程度上反映出不同算法在網(wǎng)絡抗毀性和魯棒性方面的提升效果,同時也反映算法的優(yōu)異性.對此,我們利用恢復魯棒系數(shù) (recovery robustness,Rrc)[16]來衡量實施恢復算法后在恢復區(qū)域內(nèi)的網(wǎng)絡魯棒性.Rrc計算公式如下:

表2描述了當恢復比例λ=5%時,實施不同恢復算法后網(wǎng)絡達到穩(wěn)態(tài)時極大連通網(wǎng)絡的節(jié)點平均度?k?的情況.在這里,如果正常節(jié)點比例p取值太低,整個網(wǎng)絡會因失效節(jié)點過多而完全破碎,如果取值太高又無法引起傳播.參考文獻[20]里相圖中的恢復區(qū)域,選取ER-ER(SFSF/ER-SF/SF-ER)網(wǎng)絡的正常節(jié)點比例p=0.46(0.47/0.47/0.47).觀察表2,PRCL算法在ERER(SF-SF/ER-SF/SF-ER)網(wǎng)絡實施恢復后,網(wǎng)絡達到最終穩(wěn)態(tài)時的?k?=3.1311(3.3184/3.1947/3.2979),不僅高于同類擇優(yōu)算法PRD和PRL的情況,相比RR算法的?k?更是提升了24.74%(30.84%/24.81%/28.84%).進一步觀察可見,與相依網(wǎng)絡遭受第一輪故障但尚未實施恢復的初始狀態(tài)相比,采用隨機方法的RR算法實施后的ER-ER(SF-SF/ER-SF/SF-ER)網(wǎng)絡的?k?降低了4.05%(2.27%/3.51%/1.31%),也就是說,RR算法并沒有提高剩余網(wǎng)絡的結構連通性.相反,采用擇優(yōu)方法的PRCL算法實施恢復后,與相依網(wǎng)絡遭受第一輪故障時初始狀態(tài)相比,最終穩(wěn)態(tài)的ER-ER(SF-SF/ER-SF/SF-ER)網(wǎng)絡的?k?提高了19.69%(27.86%/20.44%/27.15%).總之,相比其他恢復算法,PRCL算法發(fā)現(xiàn)的邊界節(jié)點能夠明顯地增強剩余網(wǎng)絡的結構連通性,有效地控制故障惡化避免結構破碎.

表1 恢復算法施加在相依網(wǎng)絡時的恢復魯棒系數(shù)Rrc,邊界節(jié)點恢復比例為λ=5%Table 1.Comparisons of the recovery robustness Rrc obtained by recovering 5%mutual boundary nodes with dif f erent strategies.

表2 實施恢復算法后極大連通網(wǎng)絡的節(jié)點平均度?k?,邊界節(jié)點恢復比例λ=5%Table 2.Comparisons of average degree of the steady state of the giant connected component network by recovering 5%mutual boundary nodes with dif f erent strategies.

5 算法討論

代表兩類相連邊比重關系的參數(shù)f是影響PRCL算法在相依網(wǎng)絡上恢復效果的關鍵因素之一,在此討論算法參數(shù)f取值與恢復效果的情況,如圖9所示.縱坐標pc表示存在極大連通網(wǎng)絡的概率大于或等于50%時正常節(jié)點比例的閾值[20],pc越低說明恢復效果越好.觀察ER-ER(SF-SF/ER-SF/SF-ER)相依網(wǎng)絡,參數(shù)f與閾值pc整體呈現(xiàn)兩端高中間低的U形現(xiàn)象:1)參數(shù)f=1的恢復效果在所有網(wǎng)絡都最差,pc=0.4319(0.443/0.4426/0.4337).該現(xiàn)象說明邊界節(jié)點進行擇優(yōu)恢復時,兩類相連邊發(fā)揮的影響作用不能相提并論;對于極大連通網(wǎng)絡內(nèi)的相連邊,其實質(zhì)作用是在本輪恢復階段及時地增強剩余網(wǎng)絡的結構連通性;反觀極大連通網(wǎng)絡外的相連邊,可以在后續(xù)恢復階段增加潛在恢復目標的數(shù)量,間接提高重要邊界節(jié)點被優(yōu)先恢復的概率,所以極大連通網(wǎng)絡內(nèi)的相連邊相對更重要;2)當參數(shù)f=∞時,也是當β=1時(只考慮邊界節(jié)點與極大連通網(wǎng)絡內(nèi)的相連邊,完全忽略與極大連通網(wǎng)絡外的相連邊),參數(shù)f與pc未呈線性負相關,反而出現(xiàn)pc顯著變大的上揚現(xiàn)象(0.4257/0.4386/0.4359/0.4297),該現(xiàn)象從側面反映出邊界節(jié)點的兩類相連邊雖各有不同,但只有綜合考慮才能最大程度地發(fā)揮恢復效果;3)當參數(shù)f取值有限且f>2時,f在一定取值范圍內(nèi)與pc呈現(xiàn)出近似線性反比的現(xiàn)象,但整體而言參數(shù)f與閾值pc之間不呈線性負相關,例如f∈[2,8]([2,6]/[2,6]/[2,6])局部范圍時,f越大pc越低,而隨著f>8(6/6/6),pc出現(xiàn)了時高時低的交替變化.

進一步分析,參數(shù)f存在一個近似最優(yōu)值能使pc達到相對的最低點,例如f=8(6,6,6)的ER-ER網(wǎng)絡(SF-SF,ER-SF,SF-ER)的pc值降到相對最低.不過,f最優(yōu)值的選定有可能需要深入研究相依網(wǎng)絡的子網(wǎng)結構與節(jié)點平均度對參數(shù)f造成的影響.

圖9 存在極大連通網(wǎng)絡的正常節(jié)點比例閾值pc隨參數(shù)f的變化,邊界節(jié)點恢復比例λ=5%Fig.9.The critical point pcfor dif f erent parameters of f with λ=5%under PRCL.

6 結論與展望

受客觀因素的影響,相依網(wǎng)絡遭受隨機故障時選擇誰優(yōu)先進行恢復是我們面臨的現(xiàn)實性難題.考慮到恢復模型中邊界節(jié)點的相連邊存在兩種情況:與當前極大連通網(wǎng)絡內(nèi)的正常節(jié)點存在原有連接,或是與當前極大連通網(wǎng)絡外的失效節(jié)點存在原有連接.在此,基于相依網(wǎng)絡的恢復模型,本文利用邊界節(jié)點在極大連通網(wǎng)絡內(nèi)外的連接邊數(shù)計算邊界節(jié)點的重要性,提出一種基于相連邊的擇優(yōu)恢復算法(PRCL算法).

通過由ER網(wǎng)絡和無標度網(wǎng)絡構建的ERER(SF-SF/ER-SF/SF-ER)相依網(wǎng)絡的隨機故障級聯(lián)仿真實驗表明,PRCL算法能夠更好地鑒別相依網(wǎng)絡恢復階段具有重要作用的邊界節(jié)點,有效地遏制故障在網(wǎng)絡間的級聯(lián)擴散;同時,利用NOI迭代步數(shù)等指標表明PRCL算法具備起效時間早和迭代步數(shù)少的優(yōu)勢.另外,本文利用恢復魯棒系數(shù)進行對比分析,發(fā)現(xiàn)施加PRCL算法后相依網(wǎng)絡具有更好的結構完整性,體現(xiàn)了本算法的優(yōu)異性和適用性.而極大連通網(wǎng)絡節(jié)點平均度的比較結果也進一步說明PRCL算法可以增強結構連通性.最后,通過算法分析發(fā)現(xiàn),算法參數(shù)f與恢復效果不呈線性正相關.當參數(shù)f取值有限且f>2時,PRCL算法發(fā)揮出較好的恢復效果.相比而言,參數(shù)f=1在所有網(wǎng)絡中的恢復效果都相對較差,而參數(shù)f→∞時,PRCL算法也沒有表現(xiàn)出更好的恢復效果.上述結果進一步說明PRCL算法的核心問題,即恢復模型的兩類相連邊發(fā)揮的影響作用各有不同,合理地利用兩類相連邊的比重關系能夠最大程度地增強相依網(wǎng)絡的恢復能力.

本文利用邊界節(jié)點與極大連通網(wǎng)絡內(nèi)外連接關系的思想對恢復模型中邊界節(jié)點的重要性進行度量,進而擇優(yōu)恢復相依網(wǎng)絡上的重要節(jié)點.該研究工作對于現(xiàn)實世界中相依系統(tǒng)遭受隨機故障時的應急決策和實施行為具有科學的指導意義和實際的可操作性,同時,也為深入研究相依網(wǎng)絡抗毀性等后續(xù)工作提供了借鑒.

[1]Vespignani A 2010Nature464 984

[2]Buldyrev S V,Parshani R,Paul G,Stanley H E,Havlin S 2010Nature464 1025

[3]Gao J X,Buldyrev S V,Stanley H E,Havlin S 2012Nat.Phys.8 40

[4]Chen S M,Lü H,Xu Q G,Xu Y F,Lai Q 2015Acta Phys.Sin.64 048902(in Chinese)[陳世明,呂輝,徐青剛,許云飛,賴強2015物理學報64 048902]

[5]Rinaldi S M,Peerenboom J P,Kelly T K 2001IEEE Contr.Syst.21 11

[6]Morris R G,Barthelemy M 2013Sci.Rep.3 2764

[7]Liu L J,Yin Y F,Zhang Z H,Malaiya Y K 2016Plos One10 e0164777

[8]Korkali M,Veneman J G,Tivnan B F,Bagrow J P,Hines P D H 2017Sci.Rep.7 44499

[9]Wang X F,Li X,Chen G R 2012Network Science:An Introduction(Beijing:Higher Education Press)(in Chinese)[汪小帆,李翔,陳關榮 2012 網(wǎng)絡科學導論(北京:高等教育出版社)]

[10]Cohen R,Erez K,Ben-Avraham D,Havlin S 2001Phys.Rev.Lett.86 3682

[11]Albert R,Albert I,Nakarado G L 2004Phys.Rev.E69 025103

[12]Gong K,Tang M,Hui P M,Zhang H F,Younghae D,Lai Y C 2013Plos One8 83489

[13]Zhang Z K,Liu C,Zhan X X,Lu X,Zhang C X,Zhang Y C 2016Phys.Rep.65 1

[14]Schneider C M,Yazdani N,Araújo N A M,Havlin S,Herrmann H 2013Sci.Rep.3 1969

[15]Du R J,Dong G G,Tian L X,Liu R R 2016Physica A450 687

[16]Gong M G,Ma L J,Cai Q,Jiao L C 2015Sci.Rep.5 8439

[17]Wang J D,Lao S Y,Ruan Y R,Bai L,Hou L L 2017Appl.Sci.7 597

[18]Shang Y L 2016Sci.Rep.6 30521

[19]Shekhtman L M,Danziger M M,Havlin S 2016Chaos Solition.Fract.90 28

[20]Muro M A D,Rocca C E L,Stanley H E,Havlin S,Braunstein L A 2016Sci.Rep.6 22834

[21]Schneider C M,Moreira A A,Andrade J S,Havlin S,Herrmann H J 2011Proc.Natl.Acad.Sci.USA108 3838

[22]Huang X Q,Gao J X,Buldyrev S V,Havlin S,Stanley H E 2011Phys.Rev.E83 065101

[23]Hu F Y,Yeung C H,Yang S N,Wang W P,Zeng A 2016Sci.Rep.6 24522

[24]Majdandzic A,Podobnki B,Buldyrev S V,Kenett D Y,Havlin S,Stanley H E 2013Nat.Phys.10 34

[25]Liu J G,Lin J H,Guo Q,Zhou T 2016Sci.Rep.6 21380

[26]Weng J S,Lim E P,Jiang J,He Q 2010Proceedings of the Third ACM International Conference on Web Search and Data Mining(New York:ACM Press)pp261–270

[27]Liu C,Zhang Z K 2014Commun.Nonlinear.Sci.19 896

[28]Ren X L,Lü L Y 2014Chin.Sci.Bull.13 1175(in Chinese)[任曉龍,呂琳媛 2014科學通報 13 1175]

[29]Liu R R,Li M,Jia C X,Wang B H 2016 Sci.Rep.6 25294

[30]Sun S W,Wu Y F,Ma Y L,Wang L,Gao Z K,Xia C Y 2016 Sci.Rep.6 32983

[31]Wang X Y,Cao J Y,Qin X M 2016 Plos One 11 e0160545

[32]Boccaletti S,Bianconi G,Criado R,del Genio C I,Gómez-Garde?es J,Romance M,Sendi?a-Nadal I,Wang Z,Zanin M 2014 Phys.Rep.544 1

[33]Valdez L D,Macri P A,Braunstein L A 2014 J.Phys.A:Math.Theor.47 055002

[34]Freeman L C 1979 Social Networks 1 215

[35]Chen D B,Lü L Y,Shang M S,Zhang Y C,Zhou T 2012 Physica A 391 1777

[36]Erd?s P,Rényi A 1959 Publ.Math.Debrecen 6 290

[37]Newman M E 2003 SIAM Rev.45 167

[38]Radicchi F 2015 Nat.Phys.11 7

[39]Liu R R,Jia C X,Zhang J L,Wang B H 2012 J.Univ.Shanghai Sci.Technol.34 235(in Chinese)[劉潤然, 賈春曉,章劍林,汪秉宏2012上海理工大學學報34 235]