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

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

1)(西南財(cái)經(jīng)大學(xué)經(jīng)濟(jì)信息工程學(xué)院,成都 611130)

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

3)(西南財(cái)經(jīng)大學(xué),金融智能與金融工程四川省重點(diǎn)實(shí)驗(yàn)室,成都 611130)

4)(四川師范大學(xué),可視化計(jì)算與虛擬現(xiàn)實(shí)四川省重點(diǎn)實(shí)驗(yàn)室,成都 610068)

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

1 引 言

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

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

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

2 相依網(wǎng)絡(luò)的恢復(fù)模型

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

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

圖1 相依網(wǎng)絡(luò)的共同邊界節(jié)點(diǎn),節(jié)點(diǎn)a2對(duì)應(yīng)的耦合節(jié)點(diǎn)b2與GCB的拓?fù)渚嚯xl=2,所以(a2,b2)不是共同邊界節(jié)點(diǎn)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.

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

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

具體邏輯流程如下.

I.Stagenin A

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

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

II.Stagenin B

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

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

III.Recovering

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

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

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

在恢復(fù)模型中,隨機(jī)恢復(fù)算法之所以有效是因?yàn)楣餐吔缣匦?邊界節(jié)點(diǎn)與極大連通網(wǎng)絡(luò)的拓?fù)潢P(guān)系確?；謴?fù)行為能夠最大程度地增強(qiáng)剩余網(wǎng)絡(luò)的結(jié)構(gòu)魯棒性,同時(shí),利用相依關(guān)系的對(duì)稱性,實(shí)施恢復(fù)又可以最大限度地避免被恢復(fù)節(jié)點(diǎn)受相依邊的耦合作用導(dǎo)致無效恢復(fù).然而,從現(xiàn)實(shí)角度考慮,相依系統(tǒng)遭受故障時(shí)無論采取何種應(yīng)急措施都會(huì)面臨選擇誰實(shí)施恢復(fù)的難題,這是由資源有限等客觀因素所決定的.例如真實(shí)世界中防控疾病傳播要重點(diǎn)關(guān)注高危人群[25]、阻斷互聯(lián)網(wǎng)謠言散播需要重點(diǎn)監(jiān)管意見領(lǐng)袖[26,27]等.所以,采取擇優(yōu)算法相比隨機(jī)方法而言,具備更廣的適用性和更強(qiáng)的指導(dǎo)性.

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

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

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

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

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

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

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

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

圖3 基于相連邊的擇優(yōu)恢復(fù)過程,(a)節(jié)點(diǎn)對(duì)(a1,b1)和(a2,b2)是兩組共同邊界節(jié)點(diǎn),節(jié)點(diǎn)a1和a2都有6條相連邊,其中節(jié)點(diǎn)a1的kgc=3且kngc=3;(b)依據(jù)計(jì)算公式可知I(a1)=9/3,同理得知I(a2)=8/3,因而優(yōu)先恢復(fù)a1和耦合節(jié)點(diǎn)b1,然后修復(fù)(a1,b1)的相依邊以及與其他正常節(jié)點(diǎn)的連接關(guān)系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算法的恢復(fù)效果,以經(jīng)典復(fù)雜網(wǎng)絡(luò)理論中常見的三種中心性指標(biāo)為基準(zhǔn)算法:隨機(jī)(random,RR)、度數(shù)中心性(degree,PRD)和局域中心性(local,PRL).這里,RR算法是指通過隨機(jī)方式選取邊界節(jié)點(diǎn)進(jìn)行恢復(fù),PRD算法是指優(yōu)先選取大度的邊界節(jié)點(diǎn)進(jìn)行恢復(fù)[34],PRL算法是指根據(jù)邊界節(jié)點(diǎn)的原有鄰居拓?fù)潢P(guān)系優(yōu)先選擇局域中心性最高的邊界節(jié)點(diǎn)進(jìn)行恢復(fù)[35].

4 仿真結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

表2 實(shí)施恢復(fù)算法后極大連通網(wǎng)絡(luò)的節(jié)點(diǎn)平均度?k?,邊界節(jié)點(diǎn)恢復(fù)比例λ=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 算法討論

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

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

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

6 結(jié)論與展望

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

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

本文利用邊界節(jié)點(diǎn)與極大連通網(wǎng)絡(luò)內(nèi)外連接關(guān)系的思想對(duì)恢復(fù)模型中邊界節(jié)點(diǎn)的重要性進(jìn)行度量,進(jìn)而擇優(yōu)恢復(fù)相依網(wǎng)絡(luò)上的重要節(jié)點(diǎn).該研究工作對(duì)于現(xiàn)實(shí)世界中相依系統(tǒng)遭受隨機(jī)故障時(shí)的應(yīng)急決策和實(shí)施行為具有科學(xué)的指導(dǎo)意義和實(shí)際的可操作性,同時(shí),也為深入研究相依網(wǎng)絡(luò)抗毀性等后續(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)[陳世明,呂輝,徐青剛,許云飛,賴強(qiáng)2015物理學(xué)報(bào)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)[汪小帆,李翔,陳關(guān)榮 2012 網(wǎng)絡(luò)科學(xué)導(dǎo)論(北京:高等教育出版社)]

[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科學(xué)通報(bào) 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上海理工大學(xué)學(xué)報(bào)34 235]