多層網(wǎng)絡(luò)級(jí)聯(lián)失效的預(yù)防和恢復(fù)策略概述*

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

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

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

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

1 引 言

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

圖1 電力基礎(chǔ)設(shè)施依賴關(guān)系[9]Fig.1.Dependencies among power infrastructures[9].

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

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

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

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

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

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

3 預(yù)防策略

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

3.1 故障檢測(cè)

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

3.2 預(yù)先保護(hù)重要節(jié)點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

3.4 節(jié)點(diǎn)備份

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

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

4 恢復(fù)策略

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

4.1 邊界節(jié)點(diǎn)恢復(fù)策略

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

圖4 故障恢復(fù)策略圖解[14] 網(wǎng)絡(luò)A和網(wǎng)絡(luò)B的巨分支如圖所示.情況1: 兩個(gè)通過(guò)相依邊連接的失效節(jié)點(diǎn)(節(jié)點(diǎn)1和節(jié)點(diǎn)2)分別距離其巨分支的距離l=1,然后以恢復(fù)概率γ進(jìn)行修復(fù);情況2: 如果兩個(gè)相互依賴的故障節(jié)點(diǎn)(節(jié)點(diǎn)3和節(jié)點(diǎn)5)中至少有一個(gè)與其巨分支的距離大于1,則不符合恢復(fù)的條件,所以放棄恢復(fù)這一對(duì)節(jié)點(diǎn)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é)點(diǎn)進(jìn)行恢復(fù)有以下兩個(gè)原因:第一,當(dāng)故障發(fā)生時(shí),通常都是優(yōu)先搶修正常區(qū)域周邊的基礎(chǔ)設(shè)施;第二,如果候選恢復(fù)目標(biāo)不是共同邊界節(jié)點(diǎn),其對(duì)應(yīng)的相依節(jié)點(diǎn)若是脫離巨分支的節(jié)點(diǎn),這個(gè)節(jié)點(diǎn)就會(huì)因其依賴節(jié)點(diǎn)的失效而失效,那么對(duì)該節(jié)點(diǎn)的修復(fù)就沒(méi)有意義.

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

4.2 空閑連邊恢復(fù)策略

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

圖5 網(wǎng)絡(luò)B中恢復(fù)策略的實(shí)現(xiàn)示意圖[67](a)GC表示網(wǎng)絡(luò)巨分支,虛線表示空閑連邊,帶有空閑連邊的簇表示可修復(fù)的簇,沒(méi)有空閑連邊的簇表示無(wú)法進(jìn)行恢復(fù)的簇;(b)網(wǎng)絡(luò)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.

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

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

4.3 加邊恢復(fù)策略

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

4.4 優(yōu)先恢復(fù)重要節(jié)點(diǎn)策略

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

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

圖6 恢復(fù)模型Fig.6.Schematic diagram of recovery model.

4.5 更改拓?fù)浣Y(jié)構(gòu)策略

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

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

4.6 局域攻擊修復(fù)策略

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

4.7 自適應(yīng)邊恢復(fù)策略

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

5 討 論

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

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