相依網(wǎng)絡(luò)研究綜述*

老松楊，王竣德，白　亮

(國防科技大學(xué) 信息系統(tǒng)工程重點實驗室， 湖南 長沙　410073)

?

相依網(wǎng)絡(luò)研究綜述*

老松楊，王竣德，白亮

(國防科技大學(xué) 信息系統(tǒng)工程重點實驗室， 湖南 長沙410073)

摘要：網(wǎng)絡(luò)相依性和相依網(wǎng)絡(luò)研究已經(jīng)成為近年來復(fù)雜網(wǎng)絡(luò)領(lǐng)域的熱點，但是目前對相關(guān)研究進展進行綜合歸納的文獻卻不多見。在對國內(nèi)外相關(guān)文獻進行系統(tǒng)分析的基礎(chǔ)上，簡要介紹相依網(wǎng)絡(luò)研究涉及的滲流理論；描述該類型網(wǎng)絡(luò)的級聯(lián)失效過程；從相依網(wǎng)絡(luò)的子網(wǎng)絡(luò)特性、相依邊的方向和類型、子網(wǎng)絡(luò)組合方式等三個角度對相依網(wǎng)絡(luò)魯棒性的研究成果進行總結(jié)；并從理論和應(yīng)用兩方面對未來相依網(wǎng)絡(luò)研究的發(fā)展方向進行展望。

關(guān)鍵詞：相依網(wǎng)絡(luò)；級聯(lián)失效；滲流理論；魯棒性;綜述

經(jīng)過幾十年的發(fā)展，復(fù)雜網(wǎng)絡(luò)研究的理論體系已經(jīng)被逐步建立和完善，但這些理論仍然存在一定的局限性。因為以往對復(fù)雜網(wǎng)絡(luò)的研究大多建立在孤立網(wǎng)絡(luò)的基礎(chǔ)之上，而在現(xiàn)實世界中每個網(wǎng)絡(luò)都或多或少地與其他網(wǎng)絡(luò)之間存在著各種各樣的關(guān)聯(lián)，例如物理依附、邏輯依賴、能量或信息交換等，嚴格意義上的孤立網(wǎng)絡(luò)其實是不存在的。圖1描述了電力、供水、交通運輸、通信等基礎(chǔ)設(shè)施之間的這種聯(lián)系[1]。一旦某個網(wǎng)絡(luò)中節(jié)點發(fā)生故障，網(wǎng)絡(luò)間的聯(lián)系會將故障的影響傳播和放大，并可能影響其他網(wǎng)絡(luò)的功能，最終一個很小的故障就有可能對整個系統(tǒng)造成災(zāi)難性后果[2]。這方面的典型案例就是2003年9月23日意大利大停電事故。

圖1　網(wǎng)絡(luò)化基礎(chǔ)設(shè)施之間的聯(lián)系Fig.1　Connections between network infrastructures

整個事件的起因就是電網(wǎng)中某個節(jié)點由于故障而失效，導(dǎo)致與其相連的計算機控制節(jié)點斷電，而電網(wǎng)節(jié)點向計算機控制節(jié)點供電的同時，計算機控制節(jié)點也為電力節(jié)點提供控制信號。故障發(fā)生后因控制網(wǎng)絡(luò)無法對電力網(wǎng)絡(luò)進行有效調(diào)控而使得更多電力節(jié)點與電網(wǎng)脫離，最終誘發(fā)了全國規(guī)模的停電。產(chǎn)生這種現(xiàn)象的根源就是網(wǎng)絡(luò)間存在的相依性，具有這種特性的網(wǎng)絡(luò)就是相依網(wǎng)絡(luò)(interdependent networks)。

相依網(wǎng)絡(luò)有很多不同于孤立網(wǎng)絡(luò)的性質(zhì)。在相依網(wǎng)絡(luò)中，節(jié)點之間存在的相依性使得故障可以跨網(wǎng)絡(luò)傳播，導(dǎo)致級聯(lián)失效過程通常比單個網(wǎng)絡(luò)更加劇烈，使得相依網(wǎng)絡(luò)系統(tǒng)的魯棒性較差。再比如在單個網(wǎng)絡(luò)中，逐漸移除節(jié)點時的滲流過程通常表現(xiàn)為二階形式，也就是說孤立網(wǎng)絡(luò)的連通性是逐漸降低的；而在相依網(wǎng)絡(luò)中，逐漸移除系統(tǒng)中的節(jié)點達到一定比例時會使得系統(tǒng)的連通性發(fā)生急劇變化，在時序曲線上表現(xiàn)為一階形式。這些特性都意味著現(xiàn)實世界中相依的網(wǎng)絡(luò)化基礎(chǔ)設(shè)施在節(jié)點發(fā)生故障時面臨的風(fēng)險更高。因此研究相依網(wǎng)絡(luò)的這些性質(zhì)對于設(shè)計更加健壯的網(wǎng)絡(luò)化系統(tǒng)、提高網(wǎng)絡(luò)化基礎(chǔ)設(shè)施抵御風(fēng)險的能力有重要意義。

1主題

2010年，Buldyrev[3]等在Nature上發(fā)表了研究相依網(wǎng)絡(luò)級聯(lián)失效過程的文章，提出了全相依的相依網(wǎng)絡(luò)模型，即兩個網(wǎng)絡(luò)的節(jié)點之間存在一一對應(yīng)的相依關(guān)聯(lián)，這種情況下當(dāng)一個網(wǎng)絡(luò)中的節(jié)點失效后另一個網(wǎng)絡(luò)中與其相依的節(jié)點也會失效。相依網(wǎng)絡(luò)的級聯(lián)失效過程如圖2所示。

(a) 初態(tài)(a) Initial state (b) 第一階段(b) Stage 1 (c) 初態(tài)(c) Stage 2　(d) 第二階段(d) Steady state圖2　相依網(wǎng)絡(luò)的級聯(lián)失效過程[3]Fig.2　Cascading failure of interdependent networks

在該模型中，作者假定節(jié)點只有處于最大連通子圖(giant component)中才能維持正常功能。若網(wǎng)絡(luò)N1中的一個節(jié)點被攻擊而失效，則N1中所有與之相連的連邊均被移除，此時N1被分成3個子圖(如圖2(b)所示)。根據(jù)假設(shè)，N1的非最大連通子圖的節(jié)點也失效；由于節(jié)點間相依關(guān)系的存在，N1中節(jié)點失效將導(dǎo)致網(wǎng)絡(luò)N2中相應(yīng)節(jié)點失效，進而使N2分成4個子圖(如圖2(c)所示)，N2中非最大連通子團的節(jié)點也失效；反過來，N2中失效節(jié)點又引起N1中對應(yīng)的相依節(jié)點失效，如此反復(fù)迭代至穩(wěn)態(tài)[4]。以上過程就是相依網(wǎng)絡(luò)的級聯(lián)失效。此外，還利用滲流理論研究了相依網(wǎng)絡(luò)的滲流過程從二階相變轉(zhuǎn)變?yōu)橐浑A相變的現(xiàn)象，也就是說隨著失效節(jié)點的比例達到某一閾值時，相依網(wǎng)絡(luò)的連通性會急劇下降。

這篇文章引領(lǐng)了相依網(wǎng)絡(luò)研究的熱潮(如圖3、圖4所示)，此后研究人員分別從相依網(wǎng)絡(luò)的子網(wǎng)類型、相依強度、相依類型等角度研究了其魯棒性問題，并對不同攻擊方式下相依網(wǎng)絡(luò)聯(lián)通性進行了分析，取得了豐碩成果，建立了相對完善的相依網(wǎng)絡(luò)理論體系[5]。文獻[6]從理論體系、已有模型和應(yīng)用范圍等方面對這些成果進行了比較全面的總結(jié)。

圖3　每年出版的相依網(wǎng)絡(luò)方面的文獻數(shù)Fig.3　Published items of interdependent networks in each year

圖4　每年相依網(wǎng)絡(luò)方面的引文數(shù)Fig.4　Citations of interdependent networks in each year注：以上結(jié)果是在web of science中以interdependent networks作為關(guān)鍵詞對文獻標(biāo)題進行查詢得到(截至2015年1月)。

近年來相依網(wǎng)絡(luò)魯棒性研究的一般思路是利用滲流理論，結(jié)合仿真分析或數(shù)學(xué)推導(dǎo)(如利用迭代函數(shù)研究級聯(lián)失效、利用矩陣分析方法研究網(wǎng)絡(luò)連通性[7]等)的方法研究相依網(wǎng)絡(luò)在隨機或蓄意攻擊下的魯棒性問題[8]。

相依網(wǎng)絡(luò)有三個要素：組成相依網(wǎng)絡(luò)的子網(wǎng)絡(luò)、子網(wǎng)絡(luò)間的相依連邊及子網(wǎng)絡(luò)的組合方式，現(xiàn)有的相依網(wǎng)絡(luò)研究也多是從這幾個方面展開的。因此接下來在介紹相關(guān)理論的基礎(chǔ)上從上述角度對相關(guān)研究作以下綜述。

1.1相關(guān)理論

滲流理論(percolation theory)是目前研究相依網(wǎng)絡(luò)的常用方法，最初用來描述流體在隨機介質(zhì)中運動特性[9]。在復(fù)雜網(wǎng)絡(luò)方面，該理論最早被用來研究無限大二維正方形網(wǎng)格的連通性問題：以概率p隨機地占據(jù)網(wǎng)格上的點，當(dāng)兩個被占據(jù)的點相鄰時稱其是連通的。連通點的集合稱為連通子圖。當(dāng)p較小時，網(wǎng)格上只會存在一些孤立子圖；但當(dāng)p超過某一數(shù)值時，各個孤立子圖則會形成連通的極大子圖，相應(yīng)的數(shù)值就是滲流閾值Pc。以上過程反過來看，就成了在一個網(wǎng)絡(luò)中移除一定比例的節(jié)點后分析網(wǎng)絡(luò)的連通性、進而研究網(wǎng)絡(luò)魯棒性的問題。隨機移除網(wǎng)絡(luò)中比例為1-p的節(jié)點(即每個節(jié)點被移除的概率為1-p)，當(dāng)移除比例大于滲流閾值Pc時，網(wǎng)絡(luò)中的極大連通子圖存在的概率為P∞最終降為0。滲流過程中還伴隨著滲流相變現(xiàn)象，滲流相變可分為二階相變、一階相變。在時序曲線上二級相變一般為連續(xù)曲線，而一級相變?yōu)椴贿B續(xù)曲線，即在臨界值處會發(fā)生跳躍突變的現(xiàn)象，如圖5所示。

圖5　一階和二階滲流相變示意圖[10] Fig.5　Schematic demonstration of first and second order percolation transitions

1.2相依網(wǎng)絡(luò)的子網(wǎng)絡(luò)

子網(wǎng)對相依網(wǎng)絡(luò)魯棒性的影響主要通過子網(wǎng)絡(luò)類型及節(jié)點數(shù)、平均度等特性得以體現(xiàn)。

組成相依網(wǎng)絡(luò)的子網(wǎng)絡(luò)類型有很多種：ER(Erdos-Renyi)網(wǎng)絡(luò)、RR(Random Regular)網(wǎng)絡(luò)、SF(Scale Free)網(wǎng)絡(luò)、BA(Barabási-Albert)網(wǎng)絡(luò)、WS(Watts-Strogatz)網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)作為子網(wǎng)組成的相依網(wǎng)絡(luò)的魯棒性表現(xiàn)不盡相同?，F(xiàn)有研究表明，在除子網(wǎng)類型外的其他條件相同時，RR-RR相依網(wǎng)絡(luò)的魯棒性比ER-ER相依網(wǎng)絡(luò)好[11]，ER-ER相依網(wǎng)絡(luò)比SF-SF相依系統(tǒng)魯棒性好[12-13]。這幾種相依網(wǎng)絡(luò)的魯棒性可以歸納為RR-RR>ER-ER>SF-ER>SF-SF。這是子網(wǎng)絡(luò)中節(jié)點度分布決定的——只考慮節(jié)點度分布的影響時，子網(wǎng)絡(luò)的度分布越均勻，其組成的相依網(wǎng)絡(luò)的魯棒性越好[14]。度分布越不均勻，魯棒性越差。對于SF網(wǎng)絡(luò)，當(dāng)其度分布極不均勻時，由其構(gòu)成的相依網(wǎng)絡(luò)在單個節(jié)點失效時整個相依網(wǎng)絡(luò)也可能完全崩潰[15]。

除了網(wǎng)絡(luò)類型和度分布外，子網(wǎng)絡(luò)的其他性質(zhì)，如節(jié)點數(shù)、平均度[16]、網(wǎng)間相似性等對相依網(wǎng)絡(luò)的魯棒性也有一定的影響。

對于節(jié)點數(shù)量來說，子網(wǎng)絡(luò)的節(jié)點數(shù)量越多，相依網(wǎng)絡(luò)在滲流閾值Pc處的相變過程越劇烈。極限情況下，當(dāng)子網(wǎng)絡(luò)節(jié)點數(shù)量為無窮大時，該過程表現(xiàn)為一階形式。此外子網(wǎng)絡(luò)的平均度對相依系統(tǒng)的魯棒性也有影響，平均度越高，魯棒性越好。例如Hu[17]等發(fā)現(xiàn)在完全相依的ER網(wǎng)絡(luò)中，隨著平均度增大，相依網(wǎng)絡(luò)的級聯(lián)效應(yīng)逐漸減弱。

網(wǎng)間相似性(inter-similarity)是指子網(wǎng)絡(luò)內(nèi)部節(jié)點度高的節(jié)點間傾向于產(chǎn)生相依關(guān)聯(lián)。例如世界范圍內(nèi)的港口和機場網(wǎng)絡(luò)組成的相依系統(tǒng)，重要的港口節(jié)點傾向于同重要的機場連接(這里相依關(guān)聯(lián)是指地理位置相同)。Parshani[18]，Hu[17]等用仿真和解析方法研究了港口-機場組成的相依網(wǎng)絡(luò)系統(tǒng)，發(fā)現(xiàn)兩個網(wǎng)絡(luò)的內(nèi)部相似性越高，整個系統(tǒng)在面對隨機失效時的魯棒性就越好。該結(jié)論說明通過提高節(jié)點度較高節(jié)點間相依連邊的可靠性(如添加冗余)可以有效提高系統(tǒng)的魯棒性，這種特性可以指導(dǎo)設(shè)計更健壯的網(wǎng)絡(luò)化系統(tǒng)。

1.3相依網(wǎng)絡(luò)的相依邊

相依邊的物理意義是子網(wǎng)絡(luò)之間的物質(zhì)能量信息交換等關(guān)聯(lián)關(guān)系。相依邊是相依網(wǎng)絡(luò)存在的基礎(chǔ)，也是影響相依網(wǎng)絡(luò)魯棒性最直接的因素。相依邊主要通過其方向、類型及比例等屬性影響整個相依網(wǎng)絡(luò)的魯棒性。

1.3.1相依邊方向

根據(jù)實際網(wǎng)絡(luò)之間節(jié)點的依賴關(guān)系可以把相依網(wǎng)絡(luò)模型中的相依連邊分為有向和無向兩種。Fu[13]等研究了有向相依系統(tǒng)和無向相依系統(tǒng)的滲流過程，證明了當(dāng)其他條件相同時，相依連邊有向的相依網(wǎng)絡(luò)魯棒性比相依連邊無向的相依網(wǎng)絡(luò)差。

造成這種現(xiàn)象的原因是有向系統(tǒng)中更有可能產(chǎn)生更長的相依鏈(dependency chains)。相依鏈?zhǔn)侵冈趦蓚€子網(wǎng)A，B組成的相依模型中，A中節(jié)點u支持B中節(jié)點v，v反過來又支持A中節(jié)點w(w≠u)，如此往復(fù)形成的相依節(jié)點集。相依鏈上節(jié)點的故障會通過相依鏈在子網(wǎng)之間傳播，還有可能擴散到與相依鏈相連的其他節(jié)點中，引起故障的級聯(lián)，降低系統(tǒng)的魯棒性。有向系統(tǒng)中的相依鏈往往比無向系統(tǒng)中更長，從而使得故障在網(wǎng)絡(luò)間更加有效地傳播，因此有向相依網(wǎng)絡(luò)的魯棒性較差。

1.3.2相依邊類型

相依邊類型有連接邊(connectivity links)、依賴邊(dependency links)兩種。連接邊的作用是連接不同網(wǎng)絡(luò)的節(jié)點，使得相依網(wǎng)絡(luò)的子網(wǎng)絡(luò)能夠協(xié)同工作；依賴邊表示某個節(jié)點的功能依賴于其他節(jié)點。據(jù)此可以把相依網(wǎng)絡(luò)分為三類：子網(wǎng)絡(luò)間只存在依賴邊的相依網(wǎng)絡(luò)；子網(wǎng)絡(luò)間只存在連接邊的相依網(wǎng)絡(luò)；子網(wǎng)絡(luò)間同時存在依賴邊和連接邊的相依網(wǎng)絡(luò)。

1)只存在依賴邊。Buldyrev[3]等研究了網(wǎng)絡(luò)間只存在無向依賴邊且節(jié)點之間具有一一對應(yīng)關(guān)系的情形；Bashan Amir[19]等用解析方法分析了依賴邊的分布對網(wǎng)絡(luò)魯棒性的影響；Shao[20]等認為實際網(wǎng)絡(luò)中節(jié)點的對應(yīng)關(guān)系不是一一對應(yīng)的，而是一對多或多對多的?；诖颂岢隽司哂卸嘀匾蕾囮P(guān)系的相依網(wǎng)絡(luò)模型并研究了該類相依網(wǎng)絡(luò)的滲流過程，最后得出結(jié)論：當(dāng)相依網(wǎng)絡(luò)的子網(wǎng)絡(luò)之間依賴邊的平均度很大時，該相依網(wǎng)絡(luò)模型的滲流特性與單個ER網(wǎng)絡(luò)類似。

2)只存在連接邊。2010年，Leicht[21]等研究了網(wǎng)絡(luò)間只存在連接邊的相依網(wǎng)絡(luò)的滲流理論，結(jié)果顯示，這種情況下增加子網(wǎng)絡(luò)間的連邊可以有效降低滲流閾值，提高網(wǎng)絡(luò)的魯棒性。這與只存在依賴邊的網(wǎng)絡(luò)的性質(zhì)剛好相反。

3)同時存在依賴邊和連接邊。Hu[22]和Zhou[23]等利用滲流理論研究了同時包含依賴邊和連接邊兩種類型的相依網(wǎng)絡(luò)的性質(zhì)，觀察到了一階、二階混合相變的滲流相變現(xiàn)象。Amir Bashan[11]等研究了兩個平均度都為k、規(guī)模為s的ER網(wǎng)絡(luò)組成，且兩個ER網(wǎng)絡(luò)之間同時包含依賴邊和連接邊的相依網(wǎng)絡(luò)。在移除比例為1-p的節(jié)點后，該相依網(wǎng)絡(luò)依然存在最大連通子圖的概率可表示為：

P∞=ps-1[1-exp(-kpP∞)]s

(1)

1.3.3相依邊比例

相依邊比例表征相依網(wǎng)絡(luò)中具有相依關(guān)系的節(jié)點對的數(shù)量，可以用相依網(wǎng)絡(luò)之間的相依強度進行度量。

相依網(wǎng)絡(luò)的相依強度q指的是相依網(wǎng)絡(luò)中有相依關(guān)系的節(jié)點所占的比例：q=0對應(yīng)于網(wǎng)絡(luò)之間無相依關(guān)系，q=1表示子網(wǎng)絡(luò)間完全相依，即節(jié)點之間具有一一對應(yīng)的相依關(guān)系。Parshani和Zhang等通過研究指出，當(dāng)網(wǎng)絡(luò)之間的連接強度從0到1逐漸增加時，相依網(wǎng)絡(luò)的滲流相變過程會由連續(xù)的二階相變演化為跳變的一階相變[24-25]。比如對于RR網(wǎng)絡(luò)組成的相依網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)之間的相依強度較小時，相依網(wǎng)絡(luò)的滲流過程表現(xiàn)為平滑的二階相變，但隨著相依強度增大則逐漸演變?yōu)橐浑A相變。

Zhou[26]等對兩個SF網(wǎng)絡(luò)組成的相依網(wǎng)絡(luò)進行研究發(fā)現(xiàn)，這種相依網(wǎng)絡(luò)的相依強度q存在兩個臨界值q1和q2(q1

1.4相依網(wǎng)絡(luò)的組合方式

在早期開展研究中，研究人員大多從比較簡單的模型入手，通過研究由兩個子網(wǎng)絡(luò)構(gòu)成的相依網(wǎng)絡(luò)模型的滲流特性和魯棒性特點。隨著研究的深入，有學(xué)者從子網(wǎng)絡(luò)規(guī)模和組合方式的角度對相依網(wǎng)絡(luò)模型進行了拓展，目前這方面的一個研究重點就是網(wǎng)絡(luò)組成的網(wǎng)絡(luò)——多層網(wǎng)絡(luò)(Network Of Networks，NON)的魯棒性。

圖6　相依網(wǎng)絡(luò)的組合方式Fig.6　Combination modes of interdependent networks

目前研究較多的是由ER，RR等網(wǎng)絡(luò)作為子網(wǎng)絡(luò)，以鏈形、星形、樹形或環(huán)形組合方式組成的NON的性質(zhì)，如圖6所示。圖中每個節(jié)點表示一個子網(wǎng)絡(luò)，邊表示子網(wǎng)絡(luò)之間的相依關(guān)聯(lián)，這里相依邊可以是有向也可以是無向的[27-28]。

1.4.1鏈形、星形

對于鏈形、星形組合方式組成的相依網(wǎng)絡(luò)，利用滲流理論研究其魯棒性可以得到結(jié)論：在這兩種組合方式下，相依網(wǎng)絡(luò)的滲流閾值和極大連通子圖規(guī)模相同，并且極大子圖存在的概率可以表示為：

P∞=p[1-exp(-kP∞)]n

(2)

對于ER網(wǎng)絡(luò)組成的星形NON，存在一個相依強度的臨界值——當(dāng)相依強度大于這個臨界值時NON的滲流過程為一階相變，反之則為平滑的二階相變狀態(tài)[29-31]，并且級聯(lián)失效后存在最大連通子圖的概率取決于星形網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。

1.4.2樹形

根據(jù)子網(wǎng)絡(luò)的不同類型，Gao[32]等研究了由RR和ER網(wǎng)絡(luò)組成的兩種樹形NON的滲流特性。對于n個平均度為k的ER網(wǎng)絡(luò)組成的NON，移除一定比例節(jié)點后存在極大連通子圖的概率為：

P∞=p[1-exp(-kP∞)]n

(3)

而對于由n個平均度都為k的相依RR網(wǎng)絡(luò)組成的樹形NON，移除比例為1-p的節(jié)點后，存在最大連通子圖的概率為：

(4)

在極限情況即子網(wǎng)絡(luò)個數(shù)n=1時，樹形NON在pc處的滲流過程為二階形式，而n>1時則為一階相變。此外在相同條件下，RR網(wǎng)絡(luò)組成的樹形NON魯棒性比ER網(wǎng)絡(luò)組成的樹形NON更好，并且在ER型NON中關(guān)于子網(wǎng)絡(luò)平均度k存在臨界閾值kmin(n) (與子網(wǎng)絡(luò)個數(shù)n有關(guān))。當(dāng)子網(wǎng)絡(luò)平均度小于此閾值時，即使只有一個節(jié)點失效也會導(dǎo)致整個NON的崩潰。但由RR網(wǎng)絡(luò)構(gòu)成的樹形NON不存在這樣的閾值。

1.4.3環(huán)形

對于圖6(d)所示的環(huán)形NON：由n個平均度都為k的ER網(wǎng)絡(luò)組成，各個子網(wǎng)具有相依關(guān)系的節(jié)點比例q都相同，且相依邊的方向也一致。當(dāng)對每一個子網(wǎng)絡(luò)中的節(jié)點都移除同樣比例1-p的節(jié)點時，可以得到最大連通子圖的概率滿足：

P∞=p[1-exp(-kP∞)](qP∞-q+1)

(5)

1.4.4其他組合方式

除以上方式外，對于其他組合方式也有人做了一些探索，Buldyrev[33]等研究了由ER子網(wǎng)絡(luò)組成的RR型相依網(wǎng)絡(luò)——由n個ER網(wǎng)絡(luò)組成，每個子網(wǎng)都依賴于其他m個子網(wǎng)的魯棒性和滲流特性。與環(huán)形組合方式分析過程類似，假定每個子網(wǎng)初始失效節(jié)點的比例都為1-p，子網(wǎng)間具有相依關(guān)系的節(jié)點比例q都相同，則這類相依網(wǎng)絡(luò)級聯(lián)失效后的極大連通子圖與子圖的個數(shù)無關(guān)，可表示為：

(6)

對比式(2)～(6)可知：鏈形、星形和樹形NON在級聯(lián)失效后最大連通子圖的存在概率與子網(wǎng)個數(shù)有關(guān)，并且在節(jié)點失效比例等初始條件相同的情況下，網(wǎng)絡(luò)的滲流閾值和級聯(lián)失效后存在極大子圖的概率也相同。但環(huán)形以及RR型NON級聯(lián)失效后的最大連通子圖存在的概率與子網(wǎng)個數(shù)無關(guān)[27]。

2結(jié)論

在網(wǎng)絡(luò)化基礎(chǔ)設(shè)施相依關(guān)聯(lián)逐漸加強的背景下，從相依網(wǎng)絡(luò)的概念被提出到現(xiàn)在，研究人員逐步分析了不同子網(wǎng)類型、不同相依方式及強度[34]、不同攻擊方式下相依網(wǎng)絡(luò)的特性。近兩年又對不同子網(wǎng)類型、不同組合方式、不同耦合強度等條件下網(wǎng)絡(luò)相依性對NON魯棒性的影響進行了探討。在應(yīng)用范圍上，相依網(wǎng)絡(luò)研究已經(jīng)逐漸從最初的網(wǎng)絡(luò)化基礎(chǔ)設(shè)施設(shè)計和優(yōu)化[35]、安全操作和控制[36-38]等方面，拓展到了如生理系統(tǒng)、生態(tài)學(xué)、流行病傳播[39]、氣候變化、信息擴散[40]、經(jīng)濟網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等其他很多方面，為人們理解社會、自然的內(nèi)在運行規(guī)律提供了一種理論手段。

綜上所述，我們可以對今后該領(lǐng)域研究的大致方向進行預(yù)測，具體可以概括為以下兩方面：

1)理論方面。節(jié)點或邊上加上權(quán)值以表示節(jié)點或邊的容量、負載、失效概率等物理含義的加權(quán)相依網(wǎng)絡(luò)魯棒性分析仍是目前該領(lǐng)域研究的一個薄弱環(huán)節(jié)[41-43]。另外現(xiàn)有研究模型的規(guī)模多是固定的，而現(xiàn)實世界中網(wǎng)絡(luò)大都處于動態(tài)演化的狀態(tài)，因此考慮節(jié)點或邊演化的動態(tài)相依網(wǎng)絡(luò)性質(zhì)也應(yīng)該給予足夠的重視[44]。其他如孤立網(wǎng)絡(luò)的各種動力學(xué)行為在相依網(wǎng)絡(luò)中的表現(xiàn)、節(jié)點的空間約束對相依系統(tǒng)的影響等也是今后該領(lǐng)域研究的潛在熱點[45]。

2)實踐應(yīng)用方面。目前所建的相依網(wǎng)絡(luò)模型對實際系統(tǒng)的描述能力有限。以往開展的相依網(wǎng)絡(luò)研究大都從理論角度出發(fā)，沒有把目光集中于實際相依網(wǎng)絡(luò)的分析建模上，所建模型與現(xiàn)實世界中的系統(tǒng)沒有緊密聯(lián)系。因此，從現(xiàn)實出發(fā)、根據(jù)實際系統(tǒng)的特點和數(shù)據(jù)進行相依網(wǎng)絡(luò)分析應(yīng)該成為今后的研究重點。此外，網(wǎng)絡(luò)相依性理論在如社會學(xué)、經(jīng)濟學(xué)、生態(tài)學(xué)、生理系統(tǒng)等新領(lǐng)域的應(yīng)用也應(yīng)成為下一步關(guān)注的重點。

參考文獻(References)

[1]Gao J X, Li D Q, Havlin S. From a single network to a network of networks[J]. National Science Review, 2014, 1(3): 346-356.

[2]Rinaldi S M, Peerenboom J P, Kelly T K. Identifying, understanding, and analyzing critical infrastructure interdependencies[J]. Control Systems, IEEE, 2001, 21(6): 11-25.

[3]Buldyrev S V, Parshani R, Paul G, et al. Catastrophic cascade of failures in interdependent networks[J]. Nature, 2010, 464(7291): 1025-1028.

[4]李國穎,成柏松,張鵬,等. 相互依存網(wǎng)絡(luò)魯棒性研究綜述[J]. 電子科技大學(xué)學(xué)報, 2013, 42(1):23-28.

LI Guoying, Cheng Baisong, Zhang Peng, et al. Review of the interdependent networks[J]. Journal of University of Electron ic Science and Technology of China, 2013, 42(1):23-28. (in Chinese)

[5]Danziger M M, Bashan A, Berezin Y, et al. An introduction to interdependent networks[C]//Proceedings of the 22nd International Conference on Nonlinear Dynamics of Electronic Systems, 2014, 438: 189-202.

[6]D′Agostino G, Scala A. Networks of networks: the last frontier of complexity[M]. Germany: Springer, 2014.

[7]Martín-Hernández J, Wang H, Van Mieghem P, et al. Algebraic connectivity of interdependent networks [J]. Physica A: Statistical Mechanics and its Applications, 2014, 404: 92-105.

[8]劉潤然, 賈春曉, 章劍林, 等. 相依網(wǎng)絡(luò)在不同攻擊策略下的魯棒性[J],上海理工大學(xué)學(xué)報, 2012, 34(3): 235-239.

LIU Runran, JIA Chunxiao, ZHANG Jianlin, et al. Robustness of interdependent networks under several intentional attack strategies[J]. Journal of University of Shanghai for Science and Technology, 2012, 34(3): 235-239. (in Chinese)

[9]董高高. 遭受攻擊的耦合相依網(wǎng)絡(luò)的魯棒性研究[D]. 鎮(zhèn)江：江蘇大學(xué), 2013.

DONG Gaogao. Study on robustness of coupled interdependent networks under attacks[D]. Zhenjiang:Jiangsu University, 2013. (in Chinese)

[10]Gao J X, Buldyrev S V, Stanley H E, et al. Networks formed from interdependent networks[J]. Nature Physics, 2011, 8(1): 40-48.

[11]Bashan A, Havlin S. The combined effect of connectivity and dependency links on percolation of networks[J]. Journal of Statistical Physics, 2011, 145(3): 686-695.

[12]Zhang Q, Li D, Kang R, et al. Reliability analysis of interdependent networks using percolation theory[C]//Proceedings of International Conference on Signal-Image Technology & Internet Based Systems, 2013:626-629.

[13]Fu G H, Dawson R, Khoury M, et al. Interdependent networks: vulnerability analysis and strategies to limit cascading failure[J]. The European Physical Journal B, 2014, 87(7): 148.

[14]Buldyrev S V, Shere N W, Cwilich G A. Interdependent networks with identical degrees of mutually dependent nodes[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2011, 83(1):1-8.

[15]Zhang P, Cheng B S, Zhao Z, et al. The robustness of interdependent transportation networks under targeted attack[J]. Europhysics Letters, 2013, 103(6):68005.

[16]Cheng Z S, Cao J D, Hayat T. Cascade of failures in interdependent networks with different average degree[J]. International Journal of Modern Physic C, 2014, 25(5):1440006.

[17]Hu Y, Zhou D, Zhang R, et al. Percolation of interdependent networks with inter-similarity[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2013, 88(5): 052805.

[18]Parshani R, Rozenblat C, Ietri D, et al. Inter-similarity between coupled networks[J]. Europhysics Letters, 2010, 92(6): 68002.

[19]Bashan A, Parshani R, Havlin S. Percolation in networks composed of connectivity and dependency links[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2011, 83(5): 051127.

[20]Shao J, Buldyrev S V, Havlin S, et al. Cascade of failures in coupled network systems with multiple support-dependence relations[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2011, 83(3): 036116.

[21]Leicht E A, D′Souza R M. Percolation on interacting networks[J]. arXiv preprint arXiv:0907.0894, 2009.

[22]Hu Y, Ksherim B, Cohen R, et al. Percolation in interdependent and interconnected networks: Abrupt change from second-to first-order transitions[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2011, 84(6): 066116.

[23]Zhou D, Bashan A, Cohen R, et al. Simultaneous first-and second-order percolation transitions in interdependent networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2014, 90(1): 012803.

[24]Parshani R, Buldyrev S V, Havlin S. Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition[J]. Physical Review Letters, 2010, 105(4): 048701.

[25]Zhang P, Cheng B S, Zhao Z, et al. The robustness of interdependent transportation networks under targeted attack[J]. Europhysics Letters, 2013, 103(6): 68005.

[26]Zhou D, Gao J, Stanley H E, et al. Percolation of partially interdependent scale-free networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2013, 87(5): 052812.

[27]Gao J, Buldyrev S V, Havlin S, et al. Robustness of a network of networks[J]. Physical Review Letters, 2011, 107(19): 195701.

[28]Gao J, Buldyrev S V, Havlin S, et al. Robustness of a network formed by n interdependent networks with a one-to-one correspondence of dependent nodes[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2012, 85(6): 066134.

[29]Dong G, Gao J, Du R, et al. Robustness of network of networks under targeted attack[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2013, 87(5): 052804.

[30]Dong G, Tian L, Zhou D, et al. Robustness of n interdependent networks with partial support-dependence relationship[J]. Europhysics Letters, 2013, 102(6): 68004.

[31]Dong G, Tian L , Du R, et al. Robustness of network of networks with interdependent and interconnected links[J].Physica A: Statistical Mechanics and its Applications, 2013, 424:11-18.

[32]Gao J, Buldyrev S V, Havlin S, et al. Robustness of a tree-like network of interdependent networks[J]. arXiv preprint arXiv:1108.5515, 2011.

[33]Gao J, Buldyrev S, Stanley H E, et al. Percolation of a general network of networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2013, 88(6): 062816.

[34]Zhou D, Stanley H E, D’Agostino G, et al. Assortativity decreases the robustness of interdependent networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2012, 86(6): 066103.

[35]Parandehgheibi M, Modiano E. Robustness of interdependent networks: the case of communication networks and the power grid[C]//Proceedings of IEEE Global Communications Conference, 2013:2164-2169 .

[36]Zio E, Sansavini G. Modeling interdependent network systems for identifying cascade-safe operating margins[J]. IEEE Transactions on Reliability, 2011, 60(1): 94-101.

[37]Rosato V, Bologna S, Meloni S, et al. Interdependency effects measured on complex interdependent networks[C]//Proceedings of Complexity in Engineering，2010: 27-32.

[38]Schneider C M, Yazdani N, Araújo N A M, et al. Towards designing robust coupled networks[J]. Scientific reports, 2013, 3:1969.

[39]Son S W, Bizhani G, Christensen C, et al. Percolation theory on interdependent networks based on epidemic spreading[J]. Europhysics Letters, 2012, 97(1): 16006.

[40]Shin D H, Qian D, Zhang J. Cascading effects in interdependent networks[J]. IEEE Network,2014,28(4):82-87.

[41]Qiu Y. The effect of clustering-based and degree-based weighting on robustness in symmetrically coupled heterogeneous interdependent networks[C] //Proceedings of IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2013: 3984-3988.

[42]Qiu Y. Optimal weighting scheme and the role of coupling strength against load failures in degree-based weighted interdependent networks[J]. Physica A: Statistical Mechanics and its Applications, 2013, 392(8): 1920-1924.

[43]Qiu Y. Cascading dynamics with local weighted flow redistribution in interdependent networks[J]. The European Physical Journal B, 2013, 86(7): 1-9.

[44]Podobnik B, Horvatic D, Dickison M, et al. Preferential attachment in the interaction between dynamically generated interdependent networks[J]. Europhysics Letters, 2012, 100(5): 50004.

[45]Bashan A, Berezin Y, Buldyrev S V, et al. The extreme vulnerability of interdependent spatially embedded networks[J]. Nature Physics, 2013, 9(10): 667-672.

Review of the interdependent networks

LAOSongyang,WANGJunde,BAILiang

(Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073, China)

Abstract：In recent years, the network dependency and interdependent networks have become a research hotspot in the field of complex network, but literature about the overview of related research progress is still very rare. Based on the systematic research of domestic and overseas literatures, the percolation theory of the interdependent networks was briefly introduced, and the cascading failure process of the interdependent networks was described. Then the related progress was summarized from three aspects that can affect the robustness of interdependent networks: characteristics of sub network, type of dependency edge, the combination of sub networks. Finally, the future development direction of interdependent networks was prospected in both theoretical and practical aspects.

Key words：interdependent networks; cascading failures; percolation theory; robustness; overview

中圖分類號：O231;O157.5

文獻標(biāo)志碼：A

文章編號：1001-2486(2016)01-122-07

作者簡介：老松楊(1968—)，男，廣東佛山人，教授，博士，博士生導(dǎo)師，E-mail：laosongyang@vip.sina.com

基金項目：國家自然科學(xué)基金資助項目(60902094)

*收稿日期：2015-01-30

doi:10.11887/j.cn.201601020

http://journal.nudt.edu.cn