蔣文君 劉潤然? 范天龍2) 劉霜霜 呂琳媛2)?

1)(杭州師范大學,阿里巴巴復雜科學研究中心,杭州 311121)

2)(電子科技大學,基礎與前沿研究院,成都 611731)

現(xiàn)實生活中,與國計民生密切相關的基礎設施網(wǎng)絡大多不是獨立存在的,而是彼此之間相互聯(lián)系或依賴的,于是用于研究這些系統(tǒng)的多層網(wǎng)絡模型隨之產(chǎn)生.多層網(wǎng)絡中的節(jié)點在失效或者遭受攻擊后會因“層內(nèi)”和“層間”的相互作用而產(chǎn)生級聯(lián)效應,從而使得失效能夠在網(wǎng)絡層內(nèi)和層間反復傳播并使得失效規(guī)模逐步放大.因此,多層網(wǎng)絡比單個網(wǎng)絡更加脆弱.多層網(wǎng)絡級聯(lián)失效產(chǎn)生的影響和損失往往是非常巨大的,所以對多層網(wǎng)絡級聯(lián)失效的預防和恢復的研究具有重大意義.就多層網(wǎng)絡級聯(lián)失效的預防而言,主要包含故障檢測,保護重要節(jié)點,改變網(wǎng)絡耦合機制和節(jié)點備份等策略.就多層網(wǎng)絡發(fā)生級聯(lián)失效后的恢復策略而言,主要包含共同邊界節(jié)點恢復、空閑連邊恢復、加邊恢復、重要節(jié)點優(yōu)先恢復、更改拓撲結(jié)構、局域攻擊修復、自適應邊修復等策略.

1 引 言

在復雜網(wǎng)絡研究的早期,單個網(wǎng)絡上的多個動力學特性均受到了廣泛的關注,如疾病傳播[1,2]、網(wǎng)絡同步[3,4]、級聯(lián)失效[5]和網(wǎng)絡控制[6,7]等.而隨著研究的深入,人們發(fā)現(xiàn)很多現(xiàn)實網(wǎng)絡都不是孤立存在的,比如電力網(wǎng)絡和通訊網(wǎng)絡之間存在相互依賴關系.這些網(wǎng)絡會因與其他網(wǎng)絡之間的依賴關系,在面臨蓄意攻擊或隨機故障時比孤立網(wǎng)絡更加脆弱[8].現(xiàn)實中存在互相依賴和聯(lián)系的復雜系統(tǒng)非常多,如黑客或者病毒的攻擊會使得因特網(wǎng)出現(xiàn)故障甚至癱瘓,從而導致銀行金融系統(tǒng)、電力網(wǎng)絡、交通網(wǎng)絡和物流信息網(wǎng)絡等一系列關鍵基礎設施的數(shù)據(jù)采集與監(jiān)視控制系統(tǒng)(supervisory control and data acquisition,SCADA)無法正常工作,進而導致這些系統(tǒng)的癱瘓和崩潰.比如電力網(wǎng)絡中的發(fā)電站需要鐵路網(wǎng)絡等為其運送燃料和物資的補給,而鐵路網(wǎng)絡也需要通過電力網(wǎng)絡和通信網(wǎng)絡提供支撐和控制.圖1[9]總結(jié)了電力基礎設施網(wǎng)絡和其他基礎設施之間的依賴關系.這些基礎設施中的一個或某幾個一旦出現(xiàn)故障或受到攻擊,其影響都會快速地擴散到其他相關網(wǎng)絡中,引發(fā)一系列迭代級聯(lián)事故,從而將損害擴大到更廣范圍.發(fā)生在2003年意大利停電事故[10]和2005年8月印度尼西亞大停電事故均凸顯了這種大規(guī)模的耦合網(wǎng)絡故障對社會生產(chǎn)生活甚至國家安全帶來的巨大風險.Tootaghaj等[11]搜集了全球近年來比較重大的停電事故,如表1所列.為了避免和減少級聯(lián)失效對基礎設施所帶來的損害,2016年,我國通過了《網(wǎng)絡安全法》,構建起以信息共享為基礎,事前預防、事中控制、事后恢復與懲治的關鍵信息基礎設施保護體系[12].美國在這方面也甚為關注,自克林頓政府以來就出臺大量的相關法律文件: 第63號總統(tǒng)令和《國土安全法》等,擴展對關鍵基礎設施的保護范圍[13].

圖1 電力基礎設施依賴關系[9]Fig.1.Dependencies among power infrastructures[9].

表1 重大停電事故數(shù)據(jù)[11]Table 1.Data on major power outages[11].

如何才能避免相互依賴系統(tǒng)級聯(lián)效應的發(fā)生呢? 在這些系統(tǒng)發(fā)生級聯(lián)失效后,如何在系統(tǒng)完全崩潰之前修復并減小級聯(lián)失效所帶來的損失呢[14]?常用策略和方案通常分為兩種類型: 1)通過故障檢測和保護關鍵節(jié)點等預防措施來減少故障發(fā)生的可能性;2)當故障發(fā)生時采用合適的恢復策略,對故障進行恢復.

接下來,本文第2節(jié)介紹相依網(wǎng)絡級聯(lián)失效的經(jīng)典模型.第3,4節(jié)則分別梳理了預防多層網(wǎng)絡級聯(lián)失效的方法和級聯(lián)失效發(fā)生后的網(wǎng)絡恢復策略,而第5節(jié)是討論部分.

2 相依網(wǎng)絡級聯(lián)失效模型

雖然很多人都注意到了網(wǎng)絡之間的耦合關系,也認為多個基礎設施網(wǎng)絡之間往往不是單一存在的,但是這一問題的研究一直未能形成一個清晰的框架.直到 2010年,Buldyrev等[10]在 Nature雜志上提出了由兩個一對一相互依賴的網(wǎng)絡構成的雙層網(wǎng)絡級聯(lián)失效模型,并建立了相關的理論分析方法,發(fā)現(xiàn)相依網(wǎng)絡在遭受攻擊后的破碎形式為一階不連續(xù)相變,這與單層網(wǎng)絡的二階連續(xù)相變有著本質(zhì)的不同.這一結(jié)果意味著級聯(lián)過程對原有的多層網(wǎng)絡動力學具有深刻的影響.但Buldyrev等提出的模型較為嚴格,具有度分布 pA(k)的網(wǎng)絡A和度分布 pB(k)的網(wǎng)絡B需要有相同的節(jié)點數(shù)N,并且兩個網(wǎng)絡中的所有節(jié)點之間要建立一對一的完全依賴關系,也就是說,屬于網(wǎng)絡A中的節(jié)點ai唯一依賴網(wǎng)絡B中的節(jié)點bj,而網(wǎng)絡B中的bj也必定唯一依賴網(wǎng)絡A中的ai,并且當網(wǎng)絡A中的節(jié)點失效后,網(wǎng)絡B中與之對應的節(jié)點也會立刻失效,反之亦然.其級聯(lián)失效的過程如下: 從網(wǎng)絡A中隨機刪除一定比例的節(jié)點后,網(wǎng)絡A中新產(chǎn)生的孤立節(jié)點會失效,隨后網(wǎng)絡B中與網(wǎng)絡A中的所有失效節(jié)點有依賴關系的節(jié)點也會失效,而網(wǎng)絡B中失效的節(jié)點又會反饋到網(wǎng)絡A中,如此反復迭代,直到不再有新的節(jié)點失效,網(wǎng)絡達到穩(wěn)態(tài),級聯(lián)失效過程結(jié)束.圖2展示了兩個網(wǎng)絡的級聯(lián)失效過程.

圖2 級聯(lián)失效迭代過程的建模[10](a)網(wǎng)絡在初始狀態(tài)下遭到攻擊;(b),(c)和(d)網(wǎng)絡在遭受攻擊后網(wǎng)絡級聯(lián)失效的不同階段,并最終達到了穩(wěn)態(tài),級聯(lián)過程結(jié)束Fig.2.Modeling of cascading failure iterative processes[10]:(a)The network is attacked in the initial state;(b),(c),and(d)are the cascading failure processes of the network due to the dependencies between dependent networks after the attack,respectively.Eventually reached a steady state.

經(jīng)典相依網(wǎng)絡級聯(lián)失效模型的提出引發(fā)了更多學者開展對多層網(wǎng)絡的動力學研究.在兩層網(wǎng)絡的基礎上,Gao等[15,16]進一步提出了多個網(wǎng)絡存在相互依賴的“網(wǎng)絡的網(wǎng)絡(network of network,NON)”模型.隨著對相依網(wǎng)絡級聯(lián)失效模型研究的推進,關于網(wǎng)絡魯棒性的研究[17]以及多層網(wǎng)絡之間的動力學研究也吸引了愈來愈多的學者并取得豐碩成果.Baxter等[18]闡明了一階相變的本質(zhì)其實是混合相變,當臨界節(jié)點形成的臨界簇發(fā)散的時候,一旦其中的“基石”節(jié)點(keystone vertex)失效,整個臨界簇就會發(fā)生雪崩現(xiàn)象,導致多層網(wǎng)絡互連巨分量出現(xiàn)不連續(xù)的跳躍.多層網(wǎng)絡的結(jié)構特性也對網(wǎng)絡的魯棒性有著重要的影響,如簇結(jié)構和度關聯(lián)等.Faqeeh等[19]在具有模塊的網(wǎng)絡中發(fā)現(xiàn)了不止一個滲流簇(coexist percolation cluster,CPC),對理解網(wǎng)絡的魯棒性以及傳染病模型中的疾病爆發(fā)具有重要意義.在網(wǎng)絡的同配性研究方面[20,21],文獻[20]比較了同配性對單層網(wǎng)絡和多層網(wǎng)絡上動力學過程的不同影響,發(fā)現(xiàn)在多層網(wǎng)絡上,增加層間同配程度可以提高信息擴散效率;而增加層間異配程度則可以分散鏈路通信負載,增強網(wǎng)絡魯棒性.此外還有一些學者研究了空間地理效應[22,23]和有向網(wǎng)絡[24-27]等因素對網(wǎng)絡的魯棒性所產(chǎn)生的影響.通過考慮多層網(wǎng)絡層內(nèi)節(jié)點的不同耦合方式,一些文獻也研究了多層網(wǎng)絡上的擴展?jié)B流模型,例如k-core滲流[28]、 靴攀滲流(bootstrap percolation)[29,30]和弱滲流[31]等,極大地豐富了相依網(wǎng)絡級聯(lián)失效方面的研究.

3 預防策略

預防策略是指在多層網(wǎng)絡發(fā)生故障前采取的預防應對措施,主要包括故障檢測、預先保護重要節(jié)點、節(jié)點備份以及改變耦合機制等.通過采取恰當?shù)念A防策略可以減少網(wǎng)絡關鍵節(jié)點發(fā)生失效的概率并有效防御惡意攻擊,從而極大降低由于故障和攻擊所帶來的社會經(jīng)濟損失.例如,安裝殺毒軟件可以大概率防止電腦被計算機病毒感染和損壞.相比事后的修復和采取應對措施,恰當?shù)念A防策略相對成本低且效用大.

3.1 故障檢測

故障檢測是指定期查找設備或系統(tǒng)是否出現(xiàn)故障并對這些故障進行修復的過程.很多時候這些故障可能不會立即產(chǎn)生可以覺察的危害和損失,但如果不加以排除,則會在關鍵時刻或者隨著時間積累對系統(tǒng)產(chǎn)生嚴重損害,所以應該定期加以排查.這里將各種基礎設施抽象成了網(wǎng)絡,但在現(xiàn)實生活中不同的系統(tǒng)根據(jù)其自身特點有不同側(cè)重點和相應的檢測方法,不能一概而論.比如,對于電力網(wǎng)絡來說需要檢測的可能會發(fā)生的故障包括發(fā)電機組故障、母線故障、輸電線路故障和變電所故障等,而對于計算機網(wǎng)絡來說其故障檢測則包括硬件故障、軟件故障、人為故障和病毒故障等.通過故障檢測可以提前排查系統(tǒng)中存在的問題,減少其對系統(tǒng)造成的危害.故障檢測是事前采取針對性措施,減少和防范故障發(fā)生的策略.

3.2 預先保護重要節(jié)點

重要節(jié)點一般是指少量對網(wǎng)絡結(jié)構或功能非常重要,且其影響可以快速地波及到網(wǎng)絡中大部分節(jié)點的節(jié)點[32],關于重要節(jié)點的衡量方法有很多[33,34].通過保護重要節(jié)點,可以大大提高復雜網(wǎng)絡的魯棒性[35-37].

文獻[38]研究在相互依賴的網(wǎng)絡上,分別以其中一個網(wǎng)絡中的大度節(jié)點或者小度節(jié)點為攻擊目標時網(wǎng)絡魯棒性的變化,他們發(fā)現(xiàn)即使是在較低的攻擊概率下,在相互依賴的無標度(scale-free)網(wǎng)絡[39]上采取保護大度節(jié)點的策略后,網(wǎng)絡仍是十分脆弱的.Du等[40]發(fā)現(xiàn)具有較大數(shù)量的相連邊(同一層網(wǎng)絡節(jié)點之間的連邊)和相依邊(不同層網(wǎng)絡具有相互依賴關系節(jié)點之間的連邊)的節(jié)點很重要,所以不僅要保護層內(nèi)或?qū)娱g連接程度較高的節(jié)點,而且要保護層內(nèi)和層間連邊數(shù)量之和較大的節(jié)點,以此來增加系統(tǒng)的魯棒性.

另一方面,應該優(yōu)先對那些能夠使得網(wǎng)絡快速瓦解的節(jié)點進行保護.Osat等[41]將單層網(wǎng)絡的最優(yōu)滲流推廣到多層網(wǎng)絡上,并通過最優(yōu)滲流找到那些被刪除后網(wǎng)絡不會再出現(xiàn) N1/2規(guī)模的簇的最小節(jié)點集.最優(yōu)滲流問題的解決方案在網(wǎng)絡魯棒性研究中具有直接的適用性,是瓦解網(wǎng)絡最簡易的方法.Baxter等[18]發(fā)現(xiàn)多層網(wǎng)絡中存在能夠?qū)е戮W(wǎng)絡臨界簇雪崩的基石節(jié)點,并且發(fā)現(xiàn)在網(wǎng)絡瓦解過程中巨分支崩潰的方式是不連續(xù)的混合相變,這與單個網(wǎng)絡中平滑的連續(xù)相變存在明顯差異.除此之外,文獻[42]定義了一種節(jié)點的通用性(versatility)屬性,來刻畫那些在多種不同的動力學過程中都扮演重要角色的節(jié)點,并基于此提出了多種中心性指標來識別這類節(jié)點,如Eigenvector versatility和PageRank versatility等.如果我們優(yōu)先對上述文獻中的這些重要節(jié)點采取保護措施,就可以有效減緩或者抑制網(wǎng)絡的破碎.此外,還有一些其他指標也可以作為選取重要節(jié)點進行保護的依據(jù),如度中心性[43,44]、介數(shù)中心性[45]、k-殼分解[46]、半局部中心性[47]、PageRank[48]、LeaderRank[49]、圈比[34]等.

另有文獻[17]將兩層網(wǎng)絡看成一個整體,將單層網(wǎng)絡上一些衡量節(jié)點重要性的指標運用在了雙層網(wǎng)絡(或更多層的網(wǎng)絡)上,從而找到在多層網(wǎng)絡中需要保護的重要節(jié)點,提高了相依網(wǎng)絡的魯棒性,主要包括以下方法.

1)T-度中心性保護策略.將單層網(wǎng)絡中的度中心性概念推廣到兩層網(wǎng)絡上,得T-度(twolayer-degree)保護策略.在T-度中心性保護策略中,將不同層中的節(jié)點同等看待,計算每個節(jié)點在各自層內(nèi)的度值大小,節(jié)點的重要性按它的T-度從大到小依次遞減.例如,圖3(a)給出了一個由網(wǎng)絡A和網(wǎng)絡B組成的相依網(wǎng)絡.傳統(tǒng)的方法是選擇網(wǎng)絡A中的節(jié)點1和節(jié)點2(度值分別為5和4),使它們和其依賴節(jié)點在故障發(fā)生時能夠正常工作.而實驗表明,在保護節(jié)點比例不變的情況下,保護網(wǎng)絡A中的節(jié)點1和網(wǎng)絡B中的節(jié)點1(度值分別為5和5)效果更好,這正是因為它們的T-度最大.

圖3 基于相依網(wǎng)絡的保護節(jié)點模型[17]Fig.3.Nodes protection model based on interdependent networks[17].

2)T-介數(shù)中心性保護策略.給定兩層網(wǎng)絡G=(C,(LA,LB,LAB)),其中LA表示包含 nA個節(jié)點的網(wǎng)絡A中的邊,LB表示包含 nB個節(jié)點的網(wǎng)絡B的邊,LAB則表示網(wǎng)絡A和網(wǎng)絡B之間的相依邊.將整個相依網(wǎng)絡看成一個由(nA+nB)個節(jié)點構成的網(wǎng)絡,LA,LB和LAB全都同等視為網(wǎng)絡C中的正常連邊.如圖3(b)中的深色節(jié)點,它具有三條連邊.對整個網(wǎng)絡C計算所有節(jié)點的介數(shù)中心性 C(i),即

其中 δjq為從節(jié)點j到q的所有最短路徑的數(shù)目,δjq(i)表 示從節(jié)點j到節(jié)點q的 δjq條最短路徑中經(jīng)過節(jié)點i的數(shù)目.選擇介數(shù)中心性最高的部分節(jié)點進行保護,稱為T-介數(shù)(two-layer-betweenness)保護策略.這些既包含相連邊又包含相依邊的交叉路徑在信息傳遞和故障傳播中發(fā)揮著重要作用,但在傳統(tǒng)的研究中卻被忽視.

3)T-社團(two-layer-comm)保護策略[50].① 同上,將兩個相依的網(wǎng)絡A和網(wǎng)絡B看作一個網(wǎng)絡C,初始時假設每個節(jié)點本身就是一個社團,當出現(xiàn)最大的模塊度增量[51]后,合并相應的社團i和j.當達到了局部最大模塊度時,此步驟停止.② 將此時的每個社區(qū)繼續(xù)當作一個“節(jié)點”,重復步驟直到模塊度停止變化.節(jié)點i的模塊度增益 Δ Q 為

3.3 優(yōu)化層間耦合機制

不同的網(wǎng)絡拓撲結(jié)構使多層網(wǎng)絡的魯棒性之間存在較大差異.Reis等[52]針對隨機連接的相依模型網(wǎng)絡魯棒性低,而自然界中的真實相依網(wǎng)絡魯棒性卻相對較高的問題進行研究,發(fā)現(xiàn)多層網(wǎng)絡的魯棒性由每一層的內(nèi)部結(jié)構和層間的節(jié)點連接模式共同決定.他們指出一個網(wǎng)絡的中心節(jié)點(hub nodes)與另一個網(wǎng)絡中心節(jié)點之間存在度同配相關性的相依網(wǎng)絡在隨機故障中具有更好的魯棒性.Parshani等[35]提出了部分依賴模型,通過降低相互依賴節(jié)點的數(shù)量,降低級聯(lián)失效的危害.Liu等[31]提出的弱依賴模型則降低了相互依賴網(wǎng)絡之間的依賴程度,這也使得網(wǎng)絡的破碎形式從一階相變變成二階相變,增強了網(wǎng)絡的魯棒性.文獻[53]則提出多層網(wǎng)絡間非對稱性的依賴,來控制網(wǎng)絡層間的依賴程度,從而增加網(wǎng)絡的魯棒性.Hu等[54]分析了相依網(wǎng)絡結(jié)構相似性對級聯(lián)故障帶來的影響,他們發(fā)現(xiàn)增加結(jié)構相似性會減弱級聯(lián)故障的程度.文獻[55]也指出網(wǎng)絡間的相似性越高,則發(fā)生節(jié)點隨機失效時系統(tǒng)的魯棒性也越高.文獻[56]提出網(wǎng)絡同配性研究可以為提高網(wǎng)絡魯棒性帶來新的啟發(fā),從而提高關鍵基礎設施的保護水平.Radicchi等[57]將具有相互依賴關系的節(jié)點在一個失效后其余節(jié)點也會失效這一規(guī)則更改為: 當一個節(jié)點有至少兩個副本節(jié)點(多層網(wǎng)絡的不同層中具有相互依賴關系的節(jié)點)存活時,這個節(jié)點就不會失效.在多層(＞ 2)網(wǎng)絡中建立冗余的相互依賴關系可以提高整個系統(tǒng)的魯棒性.除此之外還可以通過減弱網(wǎng)絡層間的相關性[58]、設置加強節(jié)點[59]等策略抑制系統(tǒng)的級聯(lián)效應.

3.4 節(jié)點備份

節(jié)點備份也是一個有效預防級聯(lián)效應的措施,它是指對多層網(wǎng)絡中的少數(shù)重要節(jié)點預先從結(jié)構或功能方面設計并添加它們的備份,萬一這些節(jié)點日后失效,這些備用節(jié)點能夠立即啟用代替失效的節(jié)點,維持網(wǎng)絡功能正常運行[60].Valdez等[61]認為對一些節(jié)點備份后,即使在缺少其他網(wǎng)絡支持的情況下,這些節(jié)點仍然能保留功能,從而增加了系統(tǒng)的魯棒性.Quattrociocchi等[62]通過引入節(jié)點的自愈(self-healing)機制,即增加網(wǎng)絡固有的冗余度來增強網(wǎng)絡的魯棒性.Schneider等[37]選擇最少的自治節(jié)點[63,64](通過k-shell,介數(shù)中心性等方法進行篩選節(jié)點)進行備份,以避免網(wǎng)絡在遭受攻擊時發(fā)生突然瓦解和破碎.

然而節(jié)點備份的策略也有一些不足之處.文獻[60]提出在自修復網(wǎng)絡中通過相互復制進行自我修復是一把“雙刃劍”.除此之外,在現(xiàn)實應用中,節(jié)點備份策略和網(wǎng)絡冗余設計還需要增加網(wǎng)絡的設計和維護成本(有些情況下節(jié)點的備份還面臨技術難題),付出一定的時間和經(jīng)濟代價,造成一定的浪費,因此在實際應用中往往需要考慮這一策略的代價和效果的平衡.

4 恢復策略

恢復策略并不是重新設計或者構建一個網(wǎng)絡,而是在正發(fā)生級聯(lián)失效的網(wǎng)絡上同步進行補救和修復,使其級聯(lián)過程減緩甚至停止,并逐步恢復原有功能的辦法[65].Schneider等[66]認為對于給定度分布的網(wǎng)絡,在抵御惡意攻擊中最有效的網(wǎng)絡結(jié)構仍然是未知的;而對于給定連邊數(shù)量的網(wǎng)絡,魯棒性最高的結(jié)構是所有節(jié)點度都相同的網(wǎng)絡.他們在歐洲電力系統(tǒng)、互聯(lián)網(wǎng)以及復雜網(wǎng)絡模型上對此進行了仿真,結(jié)果表明,網(wǎng)絡結(jié)構的很小變化(低成本)就可以顯著提高不同網(wǎng)絡的魯棒性,并保持其功能不變.該研究結(jié)果不僅對提高現(xiàn)有基礎設施的魯棒性有重要意義,而且對設計經(jīng)濟可靠的網(wǎng)絡系統(tǒng)也有一定的參考價值.Di Muro等[14]提出的通過尋找共同邊界節(jié)點的恢復策略(詳見4.1節(jié))和La Rocca等[67]在2018年提出的空閑連邊策略(詳見4.2節(jié)),其相同點都是從網(wǎng)絡的巨分量入手來對抗級聯(lián)效應.此外還有一些策略關注到了相依網(wǎng)絡中節(jié)點的兩種不同屬性的邊(相依邊和相連邊[68,69]),他們認為對于來自相依網(wǎng)絡的節(jié)點,它的重要性與其相依邊和相連邊的數(shù)量有關.文獻[68]研究了如何在合理分配有限成本的情況下來添加連接邊和依賴邊.文獻[69]則是通過衡量節(jié)點的相依邊和相連邊的數(shù)量,來確定優(yōu)先恢復的節(jié)點.對于多層網(wǎng)絡,Berezin等[70]發(fā)現(xiàn)局部攻擊引起的危害比起同等情況下的隨機攻擊更加嚴重.文獻[71]對于局部攻擊產(chǎn)生的故障提出在故障節(jié)點存活鄰居中選擇兩個低度值的節(jié)點進行加邊的修復方法.

4.1 邊界節(jié)點恢復策略

Muro等[14]提出相依網(wǎng)絡恢復策略,旨在對未被級聯(lián)失效波及的剩余網(wǎng)絡進行保護.這一策略使得級聯(lián)失效過程和恢復過程動態(tài)交替進行,其核心是找到兩個相依網(wǎng)絡中的共同邊界節(jié)點.共同邊界節(jié)點是指兩個網(wǎng)絡中距離各自巨分支距離為1的一對失效的相互依賴節(jié)點.圖4中節(jié)點1和2即為共同邊界節(jié)點.初始網(wǎng)絡A發(fā)生了故障,網(wǎng)絡B中所對應的節(jié)點也會失效,在網(wǎng)絡B將故障傳遞回網(wǎng)絡A之前,恢復機制會介入并找出當前的共同邊界節(jié)點,每輪恢復階段以概率γ對共同邊界節(jié)點進行恢復,從而盡可能地遏制級聯(lián)失效在相依網(wǎng)絡上的傳播.Muro等發(fā)現(xiàn),最終網(wǎng)絡有以下三種情況,第一是系統(tǒng)不被修復也不會崩潰;第二是部分節(jié)點在這一過程中失效,但恢復策略避免了系統(tǒng)的崩潰;第三是恢復過程也不能阻斷級聯(lián)失效過程,最終系統(tǒng)崩潰.

圖4 故障恢復策略圖解[14] 網(wǎng)絡A和網(wǎng)絡B的巨分支如圖所示.情況1: 兩個通過相依邊連接的失效節(jié)點(節(jié)點1和節(jié)點2)分別距離其巨分支的距離l=1,然后以恢復概率γ進行修復;情況2: 如果兩個相互依賴的故障節(jié)點(節(jié)點3和節(jié)點5)中至少有一個與其巨分支的距離大于1,則不符合恢復的條件,所以放棄恢復這一對節(jié)點Fig.4.Illustration of failure recovery strategy[14].The giant components of network A and network B are shown in the figure.Case 1: Two failed nodes(nodes 1 and 2)connected by dependent edges are respectively at a distance of l =1 from their maximal cluster,and then repaired with recovery probability γ.Case 2: If at least one of the two interdependent dent failed nodes(nodes 3 and 5)is more than 1 away from its maximal cluster,the recovery condition is not met,so the pair of nodes is abandoned to be restored.

選擇共同邊界節(jié)點進行恢復有以下兩個原因:第一,當故障發(fā)生時,通常都是優(yōu)先搶修正常區(qū)域周邊的基礎設施;第二,如果候選恢復目標不是共同邊界節(jié)點,其對應的相依節(jié)點若是脫離巨分支的節(jié)點,這個節(jié)點就會因其依賴節(jié)點的失效而失效,那么對該節(jié)點的修復就沒有意義.

吳佳鍵等[69]對此策略進行了一些修改,他們認為用恢復概率γ來隨機選擇恢復節(jié)點不是最優(yōu)方案.于是提出利用共同邊界節(jié)點在巨分支內(nèi)外的連接邊數(shù)計算和定義邊界節(jié)點的重要性,也就是基于相連邊的擇優(yōu)恢復算法(preferential recovery based on connectivity link,PRCL).實驗顯示,PRCL算法的恢復策略更好,可以識別出恢復過程中更重要的邊界節(jié)點.

4.2 空閑連邊恢復策略

在Buldyrev提出的相依網(wǎng)絡級聯(lián)失效模型的基礎上,La Rocca等[67]2018年提出在兩個相依網(wǎng)絡中對相較而言恢復代價更低的那個網(wǎng)絡進行恢復的策略.這里假設網(wǎng)絡B為符合條件的網(wǎng)絡,在步驟n=0時,從網(wǎng)絡A中移走1-p比例的節(jié)點,得到網(wǎng)絡A的巨分支.因為網(wǎng)絡A與網(wǎng)絡B的節(jié)點一對一依賴,所以可以得到網(wǎng)絡B此時的巨分支.以概率γ同時恢復網(wǎng)絡B中某個有限簇(其規(guī)模不小于2)中的兩個節(jié)點與巨分支之間的連邊.但如果該有限簇只有單個節(jié)點,那么就以相同方式恢復其與巨分支之間的一條連邊.需要注意的是所有可能被恢復的有限簇中的節(jié)點必須有空閑連邊.空閑連邊是一種虛擬連邊,指的是那些在級聯(lián)失效過程中斷開的連邊.當一條連邊斷開以后,則它兩端的節(jié)點各自得到一條空閑連邊,如圖5(a)中的虛線邊所示.

圖5 網(wǎng)絡B中恢復策略的實現(xiàn)示意圖[67](a)GC表示網(wǎng)絡巨分支,虛線表示空閑連邊,帶有空閑連邊的簇表示可修復的簇,沒有空閑連邊的簇表示無法進行恢復的簇;(b)網(wǎng)絡B完成重連后的巨分支Fig.5.Schematic diagram of the implementation of recovery strategy in network B[67]:(a)GC represents the giant component of the network,the dashed lines indicate idle connected edges,clusters with free connected edges represent repairable clusters,and clusters without free connected edges represent clusters that cannot be recovered;(b)the giant component of network B after reconnection.

之所以選擇一個有限簇里面的兩個節(jié)點與巨分支相連接,是為了減少這個有限簇再次脫離巨分支的概率.增加有限簇與巨分支相連的節(jié)點數(shù)量雖然可以提高網(wǎng)絡的魯棒性,但是在現(xiàn)實應用中也會增加成本.階段n=0結(jié)束后,以概率1-γ(γ是恢復概率)刪掉網(wǎng)絡B中沒有被恢復的有限簇,如圖5(a)中沒有空閑連邊的深色節(jié)點.至此第一輪網(wǎng)絡B恢復過程結(jié)束.當網(wǎng)絡B將這個結(jié)果反饋給網(wǎng)絡A的時候,與網(wǎng)絡B中失效節(jié)點相連接的網(wǎng)絡A中的節(jié)點就會失效,然后又反饋到網(wǎng)絡B,與網(wǎng)絡A中失效節(jié)點相依賴的網(wǎng)絡B中的節(jié)點失效,對此時的網(wǎng)絡B開啟新一輪的恢復過程.以此類推,兩個網(wǎng)絡就這樣迭代下去,直至兩個網(wǎng)絡構成的系統(tǒng)達到穩(wěn)態(tài).

La Rocca等[67]指出隨著γ的增加,臨界閾值pc降低,網(wǎng)絡破碎的形式也會從一階相變轉(zhuǎn)變?yōu)槎A相變,這就使得兩個網(wǎng)絡在發(fā)生網(wǎng)絡崩潰前可以克服更多節(jié)點的失效.這也是為什么La Rocca等認為將此恢復策略應用在兩個相依網(wǎng)絡中較為脆弱的那個網(wǎng)絡,會使整個系統(tǒng)的抗毀性提高.根據(jù)不同的恢復概率γ和網(wǎng)絡的初始保留概率p,就可以知道網(wǎng)絡是能被恢復的,還是不能避免它最終的崩潰.

4.3 加邊恢復策略

加邊恢復策略是以相依網(wǎng)絡級聯(lián)失效模型[15]為基礎通過進行一系列的加邊,來增加網(wǎng)絡魯棒性的恢復策略[72].過程如下: 在晶格網(wǎng)絡A中,對于一個被移除的節(jié)點,將其鄰居中沒有被移除的具有功能性的兩個節(jié)點以概率w相連.網(wǎng)絡B中與網(wǎng)絡A中的失效節(jié)點具有依賴關系的節(jié)點也會失效,因此網(wǎng)絡B也需要實施上述的恢復過程,即失效節(jié)點的兩個未失效且不直連的鄰居以概率w進行連接.其實恢復步驟是將每個失效節(jié)點的所有鄰居對當作候選者以概率w連接,節(jié)點失效,找出鄰居對連接,再有節(jié)點失效···,整個過程待兩個相依網(wǎng)絡達到動態(tài)平衡,即沒有連邊或者節(jié)點再失效后結(jié)束.隨著時間的推移,修復連接可能會極大地改變拓撲結(jié)構,新建立連接的兩個節(jié)點之間在原始晶格網(wǎng)絡上的距離可能越來越大.

4.4 優(yōu)先恢復重要節(jié)點策略

Gong等[73]提出在級聯(lián)失效后,優(yōu)先恢復重要節(jié)點的策略.通過在三個不同類型的耦合網(wǎng)絡(隨機網(wǎng)絡-隨機網(wǎng)絡(ER-ER)[74],隨機網(wǎng)絡-無標度網(wǎng)絡(ER-SF)[73],電力網(wǎng)絡-無標度網(wǎng)絡(power-SF)[73]上分別應用6種不同的重要節(jié)點識別指標(隨機、度中心性、介數(shù)中心性、PageRank、LeaderRank)來確定優(yōu)先恢復的節(jié)點,結(jié)果發(fā)現(xiàn)只需恢復網(wǎng)絡中5%的重要節(jié)點就可以顯著恢復網(wǎng)絡功能,尤其是介數(shù)中心性指標效果最優(yōu).而基于度中心性指標和PageRank指標的恢復策略的優(yōu)點在于其較低的計算復雜度,可用于具有數(shù)百萬節(jié)點的大規(guī)模相依網(wǎng)絡.

相依網(wǎng)絡的恢復過程如下(例如按照隨機選擇): 對于一個已經(jīng)級聯(lián)失效的網(wǎng)絡,初始時假設圖中的節(jié)點均為失效節(jié)點.如圖6(a)所示,假設恢復網(wǎng)絡C中的節(jié)點1,2,3和4,那么網(wǎng)絡D中與網(wǎng)絡C相依賴的節(jié)點5,6,7和8 被觸發(fā)而恢復正常(圖6(b)).然后,由于網(wǎng)絡C中已恢復節(jié)點4和它在D網(wǎng)絡中的依賴節(jié)點8不在各自網(wǎng)絡的巨分支中,所以它們會再次失效(圖6(c)).同理,網(wǎng)絡D中的節(jié)點5由于孤立失效,而導致與其依賴的C網(wǎng)絡中的節(jié)點1也再次失效(圖6(d)).此時網(wǎng)絡達到穩(wěn)態(tài),網(wǎng)絡中的節(jié)點2,3,6和7就是本次恢復過程執(zhí)行后最終被真正恢復的節(jié)點.

圖6 恢復模型Fig.6.Schematic diagram of recovery model.

4.5 更改拓撲結(jié)構策略

Schneider等[66]提出了一種有效恢復電力網(wǎng)絡故障的方法,他們發(fā)現(xiàn)在不增加連邊數(shù)量的情況下,只要對給定網(wǎng)絡的拓撲結(jié)構進行相對較小的修改,就有可能大大降低惡意攻擊的危害.這一結(jié)論在兩個真實網(wǎng)絡,即歐洲電網(wǎng)和互聯(lián)網(wǎng)中得到了驗證.這一發(fā)現(xiàn),一方面可以指導現(xiàn)有網(wǎng)絡通過結(jié)構的優(yōu)化來提升魯棒性,另一方面也可以用來設計未來的基礎設施,使其具有更好的魯棒性.我們通常是用臨界閾值來衡量網(wǎng)絡的魯棒性.而這種方法忽略了如果網(wǎng)絡受到了攻擊但是并沒有崩潰的情況.所以他們引進了一個獨特的測量魯棒性的方法,

其中N是網(wǎng)絡中的節(jié)點數(shù),S(Q)是在刪除了Q個節(jié)點之后網(wǎng)絡巨分量中節(jié)點的數(shù)目.

4.6 局域攻擊修復策略

局域攻擊也叫局部攻擊,指的是網(wǎng)絡位于某個地理空間范圍內(nèi)的節(jié)點受到了攻擊.在現(xiàn)實生活中,局域攻擊比隨機攻擊更為普遍,如軍事打擊、自然和人為的災害等[75].文獻[71]提出了優(yōu)先最小度修復策略(the healing strategy by prioritizing minimum degrees,HPMD),空間相依網(wǎng)絡出現(xiàn)局部攻擊時可以采用此策略.失效網(wǎng)絡的模型依托于文獻[76],優(yōu)先最小度策略是將一個失效節(jié)點的兩個度值最低的鄰居相連進行恢復,對比度中心性、隨機選擇和局部中心性,此方法更優(yōu).

4.7 自適應邊恢復策略

Liu等[77]提出在多層網(wǎng)絡中添加自適應邊的恢復策略.為了增加多層網(wǎng)絡的魯棒性,抵御大規(guī)模節(jié)點失效而導致的網(wǎng)絡崩潰,在多層網(wǎng)絡中,網(wǎng)絡A定義為控制層網(wǎng)絡,而網(wǎng)絡B,C,··是非控制層(不能人為干預),當網(wǎng)絡A中的節(jié)點ai脫離其巨分支時,我們規(guī)定節(jié)點ai會隨機產(chǎn)生M條邊連接在網(wǎng)絡A中的其他節(jié)點上,也就是說產(chǎn)生的M條自適應邊中只要有一條連接在了網(wǎng)絡A的巨分支上,節(jié)點ai就會從失效狀態(tài)恢復成具有正常功能的狀態(tài)(在此過程中假設與ai相依賴的其他網(wǎng)絡層中的節(jié)點均沒有失效,都具有正常功能).根據(jù)經(jīng)典的相依網(wǎng)絡級聯(lián)失效模型,我們知道當ai脫離巨分支時,其他網(wǎng)絡層中與之相互依賴的節(jié)點也要失效,而在節(jié)點ai脫離時,產(chǎn)生的M條自適應邊會很大程度上保證這個節(jié)點被修復,這意味著其他層中與節(jié)點ai具有依賴關系的節(jié)點會因為這個自適應邊的加入而以很大概率避免了脫離其各自網(wǎng)絡的巨分支.所以對其中一個網(wǎng)絡層的自適應擾動不僅可以增強控制層網(wǎng)絡自身的魯棒性,還可以增強其他互連網(wǎng)絡層的魯棒性.

5 討 論

多層網(wǎng)絡魯棒性是當前復雜網(wǎng)絡和復雜系統(tǒng)研究的核心問題之一.基于滲流理論的研究發(fā)現(xiàn)由于網(wǎng)絡之間的聯(lián)系和依賴,多層網(wǎng)絡往往是非常脆弱的.這一結(jié)果為一些基礎設施出現(xiàn)突發(fā)大規(guī)模級聯(lián)失效給出了理論解釋.但是還有一些基礎設施系統(tǒng)卻非常穩(wěn)定,大規(guī)模的失效現(xiàn)象很少出現(xiàn).因此,為了理解基礎設施系統(tǒng)的魯棒性和脆弱性,有關多層網(wǎng)絡魯棒性第一個方面的研究是對具有不同耦合機制、拓撲結(jié)構的多層網(wǎng)絡進行建模,并研究這些因素對多層網(wǎng)絡魯棒性的影響以及網(wǎng)絡在遭受攻擊時破碎的機理.第二個方面是如何設計有效的預防措施或節(jié)點恢復策略來降低級聯(lián)失效對多層網(wǎng)絡的損害.這兩個方面的研究相輔相成,第一個方面的研究為第二方面的研究提供了基礎理論和思路.本文所介紹的多層網(wǎng)絡級聯(lián)失效的預防策略大多基于第一個方面的研究成果,由滲流理論可知度值較小的節(jié)點很容易因網(wǎng)絡中其他節(jié)點的刪除而失效,而度值較大的節(jié)點失效的時候會產(chǎn)生較大的破壞性,因此,當跨網(wǎng)絡層的節(jié)點隨機耦合時多層網(wǎng)絡會比較脆弱,這為調(diào)整耦合機制提供了重要思路.此外,節(jié)點的保護策略也同樣基于對多層網(wǎng)絡破碎機理的研究,例如理論研究發(fā)現(xiàn)多層網(wǎng)絡臨界簇中的“基石節(jié)點”是至關重要的,這為保護多層網(wǎng)絡中的重要節(jié)點提供了重要思路.

多層網(wǎng)絡級聯(lián)失效的抑制策略研究同樣建立在對多層網(wǎng)絡破碎機理的理解之上,如邊界節(jié)點恢復模型、加邊恢復策略等.無論是對節(jié)點的恢復,還是對網(wǎng)絡進行加邊,都需要一定的代價.如何達到效用和代價的最優(yōu)? 為什么需要恢復邊界節(jié)點?哪些節(jié)點需要優(yōu)先加邊恢復? 回答這些問題同樣需要理解多層網(wǎng)絡的破碎規(guī)律和特點.對于不同的多層網(wǎng)絡發(fā)生級聯(lián)失效的時候,該采用什么樣的決策方法來選用恢復策略呢? 目前來說,回答這一問題尚有比較大的挑戰(zhàn),但可以肯定的是恢復策略的選用需要結(jié)合具體的情況,如多層網(wǎng)絡拓撲結(jié)構特性、耦合機制、網(wǎng)絡損害規(guī)模和實際需求,以及恢復的代價限制和速度要求等.隨著對多層網(wǎng)絡級聯(lián)效應研究的深入,相信對這一問題的研究會不斷取得突破,而且會有更多的、更加貼合現(xiàn)實情景的預防和恢復策略被提出.