多層網絡級聯失效的預防和恢復策略概述*

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

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

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

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

1 引 言

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

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

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

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

接下來,本文第2節介紹相依網絡級聯失效的經典模型.第3,4節則分別梳理了預防多層網絡級聯失效的方法和級聯失效發生后的網絡恢復策略,而第5節是討論部分.

2 相依網絡級聯失效模型

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

圖2 級聯失效迭代過程的建模[10](a)網絡在初始狀態下遭到攻擊;(b),(c)和(d)網絡在遭受攻擊后網絡級聯失效的不同階段,并最終達到了穩態,級聯過程結束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.

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

3 預防策略

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

3.1 故障檢測

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

3.2 預先保護重要節點

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

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

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

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

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

圖3 基于相依網絡的保護節點模型[17]Fig.3.Nodes protection model based on interdependent networks[17].

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

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

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

3.3 優化層間耦合機制

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

3.4 節點備份

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

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

4 恢復策略

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

4.1 邊界節點恢復策略

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

圖4 故障恢復策略圖解[14] 網絡A和網絡B的巨分支如圖所示.情況1: 兩個通過相依邊連接的失效節點(節點1和節點2)分別距離其巨分支的距離l=1,然后以恢復概率γ進行修復;情況2: 如果兩個相互依賴的故障節點(節點3和節點5)中至少有一個與其巨分支的距離大于1,則不符合恢復的條件,所以放棄恢復這一對節點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.

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

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

4.2 空閑連邊恢復策略

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

圖5 網絡B中恢復策略的實現示意圖[67](a)GC表示網絡巨分支,虛線表示空閑連邊,帶有空閑連邊的簇表示可修復的簇,沒有空閑連邊的簇表示無法進行恢復的簇;(b)網絡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.

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

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

4.3 加邊恢復策略

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

4.4 優先恢復重要節點策略

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

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

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

4.5 更改拓撲結構策略

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

其中N是網絡中的節點數,S(Q)是在刪除了Q個節點之后網絡巨分量中節點的數目.

4.6 局域攻擊修復策略

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

4.7 自適應邊恢復策略

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

5 討 論

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

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