多網(wǎng)系綜魯棒性解析計算

韓 劍， 蔣 奎， 齊 勇

(1. 裝甲兵工程學院裝備指揮與管理系， 北京 100072;2. 河北軌道運輸職業(yè)技術(shù)學院， 河北 石家莊 050022； 3. 空軍工程大學校務(wù)部， 陜西 西安 710051)

多網(wǎng)系綜魯棒性解析計算

韓 劍1， 蔣 奎2， 齊 勇3

(1. 裝甲兵工程學院裝備指揮與管理系， 北京 100072;2. 河北軌道運輸職業(yè)技術(shù)學院， 河北 石家莊 050022； 3. 空軍工程大學校務(wù)部， 陜西 西安 710051)

多網(wǎng)系綜； 滲流； 解析計算方法

網(wǎng)絡(luò)(因特網(wǎng)、航路網(wǎng)和電力網(wǎng))功效的發(fā)揮顯著依賴于網(wǎng)絡(luò)之間的連接關(guān)系。隨著網(wǎng)絡(luò)間的依賴性增強，對網(wǎng)絡(luò)的魯棒性提出了更高要求。目前,復雜網(wǎng)絡(luò)的研究主要針對單個孤立網(wǎng)絡(luò)，較少考慮網(wǎng)絡(luò)之間的依賴關(guān)系;但由于現(xiàn)實中的網(wǎng)絡(luò)已變得越來越相互依賴，有關(guān)相互依賴的耦合網(wǎng)系(依賴網(wǎng)絡(luò))的研究也取得了一定進展。依賴網(wǎng)絡(luò)具有如下基本特點：當一個網(wǎng)絡(luò)中的若干節(jié)點失效時，可引起其他網(wǎng)絡(luò)中的依賴節(jié)點也發(fā)生失效，從而導致更進一步地損毀，甚至造成全局范圍的級聯(lián)失效。Buldyrev等[1]通過級聯(lián)失效現(xiàn)象，對2個交互網(wǎng)絡(luò)的魯棒性進行了分析，發(fā)現(xiàn)面對隨機失效時，依賴網(wǎng)絡(luò)比獨立網(wǎng)絡(luò)更加脆弱。Erdos等[2]對2個部分依賴的網(wǎng)絡(luò)所構(gòu)成的網(wǎng)系進行了研究，發(fā)現(xiàn)部分節(jié)點功能的發(fā)揮并不直接依賴于其他網(wǎng)絡(luò)中的節(jié)點，且稱這類節(jié)點為完全自治節(jié)點。

現(xiàn)實網(wǎng)絡(luò)系統(tǒng)通常包括2個以上的彼此相互依賴的網(wǎng)絡(luò)，由多個相互依賴的網(wǎng)絡(luò)構(gòu)成的網(wǎng)絡(luò)系綜簡稱“網(wǎng)系”，如由通信、油料、金融事務(wù)、能源站構(gòu)成的基礎(chǔ)設(shè)施網(wǎng)絡(luò)。因此對現(xiàn)實系統(tǒng)進行建模時，必須考慮各網(wǎng)絡(luò)之間的相互依賴性對網(wǎng)系魯棒性的影響。

網(wǎng)系魯棒性研究主要應用滲流理論，筆者基于滲流理論提出了一種針對網(wǎng)系魯棒性的解析計算方法，該方法也適用于文獻[1]中n=1,2的情況。當n=1時，滲流變換為二階變換；當n>1時，發(fā)生級聯(lián)失效并引起一級變換。

1 多網(wǎng)系綜的圖形化表示

網(wǎng)系圖形化表示形式如圖1所示。圖中：圓圈為網(wǎng)絡(luò)，箭頭指向為網(wǎng)絡(luò)之間的依賴關(guān)系；qi1為網(wǎng)絡(luò)1中依賴于網(wǎng)絡(luò)i的節(jié)點比例，且qi1∈[0,1]，當完全依賴時，qi1=1。可見：網(wǎng)系拓撲圖中每個節(jié)點都是一個網(wǎng)絡(luò)，每條邊都為一對網(wǎng)絡(luò)之間的依賴關(guān)系。

圖1 網(wǎng)系圖形化表示形式

假設(shè)網(wǎng)系中包含n個相互依賴的網(wǎng)絡(luò)，其中網(wǎng)絡(luò)i有Ni個節(jié)點，每個節(jié)點之間通過連接邊實現(xiàn)互聯(lián)；網(wǎng)絡(luò)i中有確定比例qji>0的節(jié)點直接依賴于網(wǎng)絡(luò)j中的節(jié)點，則網(wǎng)絡(luò)i和網(wǎng)絡(luò)j就組成了一個部分依賴的網(wǎng)絡(luò)對。網(wǎng)絡(luò)對之間的依賴關(guān)系是單向的，且由網(wǎng)絡(luò)j指向網(wǎng)絡(luò)i，若網(wǎng)絡(luò)j中的節(jié)點發(fā)生失效，依賴于該失效節(jié)點的網(wǎng)絡(luò)i中的節(jié)點也將失效，如：網(wǎng)絡(luò)i為包含各種通信設(shè)備的通信網(wǎng)，網(wǎng)絡(luò)j為指揮關(guān)系網(wǎng)，則網(wǎng)絡(luò)j中的節(jié)點要發(fā)揮指揮功能，實現(xiàn)各節(jié)點之間指揮信息的傳遞就需要得到網(wǎng)絡(luò)i中通信設(shè)備的支持；否則網(wǎng)絡(luò)j中的節(jié)點無法接收和發(fā)送指揮信息，也就不能發(fā)揮指揮功能。

2 解析計算方法

假設(shè)網(wǎng)絡(luò)遭受蓄意攻擊或隨機失效后，網(wǎng)絡(luò)i中還剩下比例為pi的節(jié)點，且只有最大連接網(wǎng)絡(luò)的節(jié)點可發(fā)揮作用，這將導致級聯(lián)失效：網(wǎng)絡(luò)i中不屬于最大連接網(wǎng)絡(luò)的失效節(jié)點將引發(fā)其他網(wǎng)絡(luò)中依賴于該節(jié)點的節(jié)點失效；而這些失效的節(jié)點又反過來導致網(wǎng)絡(luò)i在更大范圍失效。

盡管各種特定情況的級聯(lián)失效和每個網(wǎng)絡(luò)最終的最大連接子網(wǎng)可通過計算機仿真來確定，但在簡化假設(shè)條件下求出解析解非常重要，這是因為解析解可作為真實情況仿真解的參考標準。

筆者主要研究多網(wǎng)系中網(wǎng)絡(luò)之間依賴關(guān)系根據(jù)度分布Pi(k)大小隨機連接的情況。Pi(k)為網(wǎng)絡(luò)i中節(jié)點度為k的概率。為了求得解析解，作如下假設(shè)[3]：1)唯一性條件，網(wǎng)絡(luò)i中的每個節(jié)點a只依賴于網(wǎng)絡(luò)j中的節(jié)點b；2)無反饋條件，若網(wǎng)絡(luò)i中的節(jié)點a依賴于網(wǎng)絡(luò)j中的節(jié)點b，且網(wǎng)絡(luò)j中的節(jié)點b反過來又依賴于網(wǎng)絡(luò)i中的節(jié)點c，則節(jié)點c和a必須是同一個節(jié)點。于是可得到與基爾霍夫等式相類似的迭代方程P∞,i=xigi(xi)，式中：xi為在經(jīng)受初始失效和級聯(lián)效應后，不考慮網(wǎng)絡(luò)i內(nèi)部連接變化所導致的進一步失效時,網(wǎng)絡(luò)i中剩余的節(jié)點比例;gi(xi)為最大連接子網(wǎng)節(jié)點數(shù)占剩余節(jié)點數(shù)的比例。gi(xi)函數(shù)可用度分布Pi(k)的生成函數(shù)來表示，即

(1)

式中：Mi為第i個網(wǎng)絡(luò)的最大節(jié)點度。

對生成函數(shù)的導數(shù)進行歸一化處理可得：

(2)

依據(jù)單網(wǎng)滲流理論可得[4]：gi(xi)=1-Gi(1-xi(1-fi))，其中輔助函數(shù)fi=Hi(1-xi(1-fi))。

xi可表示為

(3)

式中：K為網(wǎng)絡(luò)i所依賴的網(wǎng)絡(luò)數(shù)量；yji為除網(wǎng)絡(luò)i外，網(wǎng)絡(luò)j所依賴的網(wǎng)絡(luò)通過依賴關(guān)系對網(wǎng)絡(luò)j進行級聯(lián)影響后，網(wǎng)絡(luò)j中剩余的節(jié)點比例。

式(3)也可表示為

(4)

經(jīng)過級聯(lián)失效后，網(wǎng)絡(luò)j中的剩余節(jié)點比例xj為確定的，即

xj=yji[qijyijgi(xi)-qij+1]，

(5)

式中：[qijyijgi(xi)-qij+1]為網(wǎng)絡(luò)i對網(wǎng)絡(luò)j產(chǎn)生級聯(lián)影響后所剩余的節(jié)點比例。則

yji=xj/[qijyijgi(xi)-qij+1]，

(6)

這是考慮無反饋條件時得出的結(jié)論。如果不考慮無反饋條件，式(6)可簡化為yji=xj。

利用式(4)、(6)可得到若干不同拓撲結(jié)構(gòu)的網(wǎng)系數(shù)值解。雖然所有的解析結(jié)果都比計算機仿真結(jié)果小，但誤差并不大，吻合度較高。本文研究的解析和仿真網(wǎng)系中，網(wǎng)絡(luò)數(shù)量n≤10，且每個網(wǎng)絡(luò)都包含106的節(jié)點數(shù)[5]。

值得一提的是：若n=2，由式(6)可得y12=p1，y21=p2，則式(4)可以簡化為

x1=p1[p2q21g2(x2)-q21+1]，

(7)

x2=p2[p1q12g1(x1)-q12+1]。

(8)

針對圖1(a)所示的無環(huán)樹型網(wǎng)系，設(shè)所有成對的連接網(wǎng)絡(luò)間都是完全依賴關(guān)系，且滿足無反饋條件，則網(wǎng)系中所有依賴網(wǎng)絡(luò)間的節(jié)點都構(gòu)成了一一對應關(guān)系。因此，隨機移除網(wǎng)系每個網(wǎng)絡(luò)中比例為1-pi個節(jié)點，就等價于從某個網(wǎng)絡(luò)中一次性隨機移除的節(jié)點比例，即

(9)

式中：p為剩余節(jié)點比例

由式(4)、(6)可得xigi(xi)=xjgj(xj)=P∞，可見樹型網(wǎng)系中所有網(wǎng)絡(luò)的最大連接子網(wǎng)大小都相等。從網(wǎng)絡(luò)中單連通節(jié)點開始依次計算yij，可得

(10)

式中:xi=P∞/gi(xi)。

3 3種典型網(wǎng)系中的應用

以完全依賴的樹型網(wǎng)系、部分依賴的星型網(wǎng)系和部分依賴的環(huán)型網(wǎng)系3種典型的網(wǎng)系為示例，進行解析分析。

3.1 完全依賴的樹型網(wǎng)系

(11)

fc=exp[(fc-1)/nfc]。

(12)

式(10)可應用Satorras等[7]提出的蘭伯特函數(shù)W(x)來描述，即fc=-[nW(-1/n)e-(1/n)]-1。

當fc已知時，即可求得

(13)

(14)

圖2 不同值下pc隨n變化的情況

(15)

圖min隨n值變化的情況

(16)

式(16)的解對所有樹型網(wǎng)系的拓撲結(jié)構(gòu)都是有效的。P∞隨p和n變化的情況如圖4所示。

圖4 P∞隨p和n值變化的情況

由圖4可知：1)當n=1時，P∞的變化遵循ER單個網(wǎng)絡(luò)的二級滲流規(guī)律[9]；2)當n>1時，P∞的變化遵循一級滲流規(guī)律，即P∞在閾值pc處表現(xiàn)出不連續(xù)性。對于由無標度網(wǎng)絡(luò)組成的完全依賴的樹型網(wǎng)系，將無標度網(wǎng)絡(luò)的生成函數(shù)代入式(10)，可得如圖5所示的數(shù)值解。

圖5 完全依賴的樹型無標度網(wǎng)系的P∞隨p和n值變化的情況

3.2 部分依賴的星型網(wǎng)系

(17)

(18)

由P∞,i、gi和fi的定義可得:

(19)

通過求解式(18)，可得f1和f2，然后代入式(19)即可求得中心節(jié)點的最大連接子網(wǎng)值P∞,1和其他節(jié)點的P∞,2。

圖6 部分依賴的星型網(wǎng)系中心網(wǎng)絡(luò)P∞,1隨p和n值變化的情況

若該星型網(wǎng)系是完全依賴的，即q=1且f1=f2，則式(18)、(19)可簡化為式(16)。式(16)適用于qij=1的樹型網(wǎng)系；式(18)、(19)適用于qij<1的星型網(wǎng)系。因此與完全依賴網(wǎng)系相比，部分依賴網(wǎng)系的每種樹型拓撲所對應的解析解是不同的，其可通過式(5)、(6)得到。

3.3 部分依賴的環(huán)型網(wǎng)系

(20)

當q=1時，式(20)只有唯一解P∞=0；當q=0時，網(wǎng)絡(luò)間彼此沒有相互依賴關(guān)系，則P∞將是單個網(wǎng)絡(luò)的最大連接子網(wǎng)。圖7為q=0.2, 0.8時，部分依賴的環(huán)型網(wǎng)系P∞隨p變化的情況。

圖7 部分依賴的環(huán)型網(wǎng)系P∞隨p變化的情況

4 結(jié)論

筆者提出了一個應用于多個依賴網(wǎng)絡(luò)構(gòu)成的網(wǎng)絡(luò)系綜魯棒性的解析計算方法，該方法為研究不同拓撲結(jié)構(gòu)的網(wǎng)系滲流現(xiàn)象提供了參考。

1) 式(5)、(6)可用來研究由任一度分布網(wǎng)絡(luò)構(gòu)成的不同類型網(wǎng)系的滲流現(xiàn)象。而單個網(wǎng)絡(luò)滲流現(xiàn)象是依賴網(wǎng)絡(luò)滲流的特例。

2) 對完全依賴的樹型網(wǎng)系、部分依賴的星型網(wǎng)系和環(huán)型網(wǎng)系，分別應用魯棒性解析計算方法進行了剖析。式(16)、(19)和(20)分別為由n個相互依賴的ER網(wǎng)絡(luò)構(gòu)成的3種網(wǎng)系的解析式。

[1] Buldyrev S V, Parshani R, Stanley P G, et al. Catastrophic Cascade of Failures in Interdependent Networks[J].Nature, 2010, 4(7):1025-1028.

[2] Erdos P, Renyi A. On the Strength of Connectedness of a Random Graph[J].Mathematica, 1964, 12(1):261-267.

[4] Watts D L, Strogatz S H. Collective Dynamics of ‘Small-world’ Networks[J].Nature, 1998, 3(6):440-442.

[5] Albert R, Jeong H, Barab’asi, et al. Error and Attack Tolerance of Complex Networks[J].Nature, 2000, 4(6):378-382.

[6] Dorogovtsev S N, Mendes J F. Evolution of Networks: From Biological Nets to the Internet and WWW [J].Physics, 2003, 4(1):39-57.

[7] Satorras R P, Vespignani A. Evolution and Structure of the Internet: A Statistical Physics Approach [J].Physics, 2006, 7(8):997-1029.

[8] Newman J. Large Scale the Structure and Dynamic of Networks [J].Physics, 2006, 1(3):37-51.

[9] Caldarelli G, Vespignani A. Large Scale Structure and Dynamics of Complex Webs[J].World Scientific, 2007, 6(5):1075-1093.

[10] Barra’t A. Dynamical Processes on Complex Networks [D].Cambs:Cambridge University, 2008.

(責任編輯: 王生鳳)

Analytic Calculation Method of Multiplex Networks Robustness

HAN Jian1, JIANG Kui2, QI Yong3

(1. Department of Equipment Command and Administration, Academy of Armored Force Engineering, Beijing 100072, China;2. Heibei Vocational College of Rail Transportation, Shijiazhuang 050022, China;3. Department of Affairs, Air Force Engineering University, Xi’an 710051, China)

multiplex networks; percolation; analytical solution

1672-1497(2015)06-0102-05

2015-09-27

軍隊科研計劃項目

韓 劍(1986-)，男，博士研究生。

O189

A

10.3969/j.issn.1672-1497.2015.06.020