劉潤然， 賈春曉， 章劍林， 汪秉宏

（1.杭州師范大學阿里巴巴商學院，杭州 310036；2.中國科學技術大學物理學院，合肥 230026；3.上海理工大學復雜系統(tǒng)科學研究中心，上海 200093）

1 相依網(wǎng)絡的魯棒性研究進展

隨著科學與技術的迅猛發(fā)展，各類基礎設施之間的耦合和依賴變得越來越強烈，如城市的供水系統(tǒng)、電力系統(tǒng)、燃氣系統(tǒng)、交通系統(tǒng)，以及通信系統(tǒng)之間都有著非常強的依賴關系［1－2］.具體的例子有：電力系統(tǒng)與通信系統(tǒng)之間的相互依賴關系，電力系統(tǒng)需要電信系統(tǒng)進行通信和調度，而通信系統(tǒng)又需要電力系統(tǒng)提供電力支持；類似的情況還有電力系統(tǒng)和鐵路交通系統(tǒng)，鐵路交通系統(tǒng)需要電力系統(tǒng)提供電力支持，而一些火電廠又需要鐵路交通系統(tǒng)輸送能源與物資.一個系統(tǒng)受到一點點的擾動，可能會觸發(fā)其它系統(tǒng)的失效，進而又會影響到自身，從而會給整個社會帶來災難性的后果.例如，2003年9月23日的意大利大停電事件，就是由一個電力站的失效導致很多電力節(jié)點與整個電網(wǎng)的脫離，接著又導致很多互聯(lián)網(wǎng)節(jié)點的失效，最終導致調度系統(tǒng)無法對整個電力網(wǎng)絡進行有效的調控，從而誘發(fā)了更大規(guī)模的電力節(jié)點的失效［1］.另外一個國內實例是在2008年春季，中國南方的雪災導致電力網(wǎng)絡的失效，從而誘發(fā)了鐵路交通網(wǎng)絡的不暢，而鐵路運輸?shù)牟粫秤謱е铝瞬糠蛛姀S無法得到能源的補給，從而使電力系統(tǒng)和鐵路交通系統(tǒng)都難以恢復暢通，最終給華南的廣大地區(qū)帶來了非常嚴重的災害.因此，對這類相依系統(tǒng)魯棒性的研究有著非常強的現(xiàn)實意義［1－5］.

復雜網(wǎng)絡是研究復雜系統(tǒng)的有力工具之一，研究復雜網(wǎng)絡的魯棒性不但對于理解復雜系統(tǒng)的組織形式與功能之間的關系有著深刻的科學意義，而且為網(wǎng)絡的攻擊和保護提供了有效的理論依據(jù)［5－7］.目前有關復雜網(wǎng)絡魯棒性的工作包括：基于滲流理論研究網(wǎng)絡在刪除部分節(jié)點后的連通性［8－11］；基于過載節(jié)點失效過程的網(wǎng)絡上的動力學與網(wǎng)絡結構的耦合［12－19］.然而，這些工作主要是關于單一網(wǎng)絡的，有關相依網(wǎng)絡魯棒性的研究還比較少.2010年，Buldyrev等［1］在《Nature》雜志上首次發(fā)表了研究相依網(wǎng)絡魯棒性的著名論文，受到了極為廣泛的關注.該文提出了一個簡單的相依網(wǎng)絡級聯(lián)失效的模型，不但刻畫了相依網(wǎng)絡級聯(lián)失效的過程，而且發(fā)現(xiàn)相依網(wǎng)絡從連通態(tài)（有序）到破碎態(tài)（無序）是一個非連續(xù)相變過程，這與通常的復雜網(wǎng)絡座逾滲模型的連續(xù)相變有著很大不同.隨后的研究還發(fā)現(xiàn)降低相依網(wǎng)絡之間耦合還可以使相變現(xiàn)象從一級相變變成二級相變，這類似于水在發(fā)生氣液相變時的臨界現(xiàn)象［3］.Huang等［4］研究了相依網(wǎng)絡在單側節(jié)點受到蓄意攻擊下的魯棒性，而董高高［20］研究了雙側節(jié)點受到蓄意攻擊下的魯棒性.然而，當前有關同時考慮相依節(jié)點對權重的攻擊策略的研究還相對較少.本文研究了相依網(wǎng)絡在幾種攻擊策略下的魯棒性，并找出了最有效的攻擊策略，從而發(fā)現(xiàn)了相依網(wǎng)絡中最為脆弱的節(jié)點.

2 相依網(wǎng)絡的蓄意攻擊策略以及魯棒性

2.1 相依網(wǎng)絡的級聯(lián)失效過程

相依網(wǎng)絡可以形象地描述為相互依賴的系統(tǒng)，由兩個網(wǎng)絡A和B組成.每個網(wǎng)絡內部的節(jié)點由連接邊（connectivity links）連在一起，表示網(wǎng)絡內部節(jié)點的連接關系.跨網(wǎng)絡的節(jié)點由相依邊（dependency links）連在一起，表示網(wǎng)絡之間節(jié)點的相依關系［1，21］.當相依網(wǎng)絡中A或B網(wǎng)絡的節(jié)點受到攻擊而失效的時候，網(wǎng)絡A或B會破碎成幾個碎片.該模型假定只有屬于網(wǎng)絡A或網(wǎng)絡B極大簇（giant component）的節(jié)點能夠保持功能，而屬于其它碎片的節(jié)點會失去功能.假定網(wǎng)絡A中部分節(jié)點受到初始攻擊而失效，網(wǎng)絡A會破碎為若干碎片，不屬于A網(wǎng)絡極大簇的節(jié)點也會失效.A網(wǎng)絡中的失效節(jié)點也會導致B網(wǎng)絡中相應的節(jié)點失效，從而導致網(wǎng)絡B的破碎，不屬于網(wǎng)絡B極大簇的節(jié)點也因此失效.再進一步，B網(wǎng)絡中的失效節(jié)點也會導致A網(wǎng)絡中相應的節(jié)點失效，從而導致網(wǎng)絡A再次發(fā)生破碎.如此反復進行下去，經歷一定步數(shù)的迭代后（NOI），系統(tǒng)會達到穩(wěn)定.當系統(tǒng)達到穩(wěn)定時，只有屬于互聯(lián)極大簇（網(wǎng)絡A中極大簇的節(jié)點和網(wǎng)絡B中極大簇的節(jié)點完全是由相依邊連在一起的）的節(jié)點才能保持功能.整個級聯(lián)失效的過程，如圖1所示［1］.圖中，aij，bij（i，j＝1，2，…，n）分別表示網(wǎng)絡A，B的節(jié)點.在初始的情況下，A網(wǎng)絡的一個節(jié)點因受到攻擊而失效；在階段1，與該失效節(jié)點相連的邊被刪去，同時與之相依的B網(wǎng)絡中的節(jié)點也因此失效，與之相連的邊也被刪除，不屬于A網(wǎng)絡極大簇的節(jié)點a11，a12失效；在階段2，b21，b22因與失效節(jié)點a11，a12相依而失效，不屬于B網(wǎng)絡極大簇的節(jié)點b23失效；在階段3，B網(wǎng)絡中失效的節(jié)點b23又導致了A網(wǎng)絡的a33節(jié)點失效，整個系統(tǒng)達到穩(wěn)態(tài).

圖1 相依網(wǎng)絡級聯(lián)失效的迭代過程Fig.1 Iterative process of a cascade of failures

相依網(wǎng)絡中互聯(lián)極大簇是衡量相依網(wǎng)絡在受到攻擊后維持自身功能的重要指標，類似于滲流理論中的序參量極大簇，本文將互聯(lián)極大簇標記為S.在接下來的部分，將重點研究相依隨機網(wǎng)絡在不同攻擊策略下互聯(lián)極大簇隨著攻擊強度的變化而變化的規(guī)律.

2.2 相依網(wǎng)絡的蓄意攻擊策略

相依網(wǎng)絡在隨機攻擊策略下的魯棒性已經有較為深入的理論研究，然而在相依網(wǎng)絡中，一個節(jié)點的失效會導致與之相依節(jié)點的失效.因此，一個節(jié)點對于維持整個網(wǎng)絡連通性的能力不僅與自身有關，而且與它相依的節(jié)點有關.本文對相依網(wǎng)絡中相依節(jié)點對進行加權，這里的權重假定就是這對節(jié)點對于維持相依網(wǎng)絡功能的重要性，然后依據(jù)它們的權重大小進行攻擊.

攻擊策略I：對A網(wǎng)絡中節(jié)點度進行降序排列，攻擊排序靠前的比例為1－p的節(jié)點，因此剩下比例為p的節(jié)點保留了下來.該策略僅僅考慮了單側節(jié)點的度.

攻擊策略Ⅱ：對網(wǎng)絡A，B中相依邊兩端的相依節(jié)點對進行加權，第n對節(jié)點的權重是：Wn＝其中表示A網(wǎng)絡中第n個節(jié)點的度表示B網(wǎng)絡中第n個節(jié)點的度.然后依據(jù)權重對這些節(jié)點對進行排序，攻擊排序靠前且比例為1－p的節(jié)點，保留比例為p的部分節(jié)點.該策略同時考慮了相依節(jié)點度的特性.

在這里，通過參數(shù)p可以調節(jié)對相依網(wǎng)絡的攻擊強度.在接下來的部分將展示網(wǎng)絡的互聯(lián)極大簇S隨參數(shù)p的變化規(guī)律.這里研究的相依網(wǎng)絡是由兩個ER隨機網(wǎng)絡random networks）組成，兩個網(wǎng)絡中節(jié)點之間的相依關系是隨機建立的，也就是說網(wǎng)絡與網(wǎng)絡之間相依節(jié)點度的相關性等于0.

2.3 相依網(wǎng)絡在不同攻擊策略下的魯棒性

相依網(wǎng)絡在隨機攻擊下，互聯(lián)極大簇隨攻擊強度1－p的變化呈現(xiàn)一級（非連續(xù)）相變的行為，這與經典隨機網(wǎng)絡的座逾滲的二級（連續(xù)）相變有著很大的不同.文中圖2～5的圖（a）展示了相依網(wǎng)絡達到穩(wěn)態(tài)時的序參量S和參數(shù)p之間的關系；圖2～5的圖（b）展示了NOI與參數(shù)p的關系，圖（b）中的插圖展示了NOI在相變點處與網(wǎng)絡規(guī)模N的關系.相依網(wǎng)絡中兩個網(wǎng)絡的平均度都為〈k〉＝4，每條曲線都來自1 000次平均的結果.從圖2（a）可以發(fā)現(xiàn)在不同的系統(tǒng)規(guī)模下，所有的曲線可以相交于一點.當系統(tǒng)的規(guī)模N趨向于無窮大的時候，可以認為互聯(lián)極大簇S可以從此點跳到0，此點可以近似于一級相變的相變點.圖2（b）展示了相依網(wǎng)絡達到穩(wěn)態(tài)時所經歷的迭代步數(shù)（NOI）.NOI在相變點附近有一個峰值，當系統(tǒng)規(guī)模達到無窮大時，NOI所對應的p值就是一級相變的相變點.另外，還可以發(fā)現(xiàn)，NOI與網(wǎng)絡規(guī)模N呈現(xiàn)冪函數(shù)的關系，也就是當N趨近于無窮大時，NOI也趨向于無窮大.對于相依的兩個隨機網(wǎng)絡，網(wǎng)絡破碎臨界值的理論結果為pc＝2.455 407／〈k〉［1，22］，因此對于平均度為4的相依網(wǎng)絡，其發(fā)生破碎的臨界點pc＝0.613 8，通過模擬可以驗證這一結果.

圖3中（見下頁），作者研究了相依網(wǎng)絡在攻擊策略I下的魯棒性，發(fā)現(xiàn)了與隨機攻擊類似的一級相變的現(xiàn)象，但是臨界點pc≈0.787，明顯超過隨機攻擊的臨界點pc＝0.613 8，這說明相依網(wǎng)絡在蓄意攻擊策略下變得更加脆弱了.

圖3 攻擊策略I下相依網(wǎng)絡的魯棒性Fig.3 Numerical simulations of interdependent networks under attack strategy I

圖4研究了相依網(wǎng)絡在攻擊策略Ⅱ下的魯棒性，同樣發(fā)現(xiàn)了一級相變的現(xiàn)象.但是，臨界點pc≈0.816，明顯超過隨機攻擊與攻擊策略I的臨界點，這說明相依網(wǎng)絡在此種攻擊策略下變得進一步脆弱了.這個結果也證明了考慮相依節(jié)點對度之和的攻擊策略比考慮單側節(jié)點度大小的攻擊策略更有效.

圖4 攻擊策略Ⅱ下相依網(wǎng)絡的魯棒性Fig.4 Numerical simulations of interdependent networks under attack strategyⅡ

圖5研究了相依網(wǎng)絡在攻擊策略Ⅲ下的魯棒性，同樣發(fā)現(xiàn)了一級相變的現(xiàn)象，相變點pc≈0.818，與攻擊策略Ⅱ的pc≈0.816類似.這個結果進一步證明了考慮相依節(jié)點對度特性的攻擊策略比考慮單側節(jié)點度大小的攻擊策略更有效.

圖5 攻擊策略Ⅲ下相依網(wǎng)絡的魯棒性Fig.5 Numerical simulations of interdependent networks under attack strategyⅢ

3 結 論

本文比較了相依網(wǎng)絡在幾種攻擊策略下的魯棒性，發(fā)現(xiàn)了考慮相依節(jié)點對度特性的攻擊策略比考慮單側節(jié)點度特性的攻擊策略更有效.這項工作對于理解相依網(wǎng)絡級聯(lián)失效的過程有著重要的作用，為找到相依網(wǎng)絡的弱點并進行有效的保護和攻擊提供了有益的提示.但是，本文僅僅研究了相依隨機網(wǎng)絡的魯棒性，其它復雜網(wǎng)絡如無標度網(wǎng)絡和小世界網(wǎng)絡的魯棒性還有待進一步研究［5－7］.此外，目前研究的是相依節(jié)點度不相關的網(wǎng)絡，今后還將研究相依網(wǎng)絡度相關網(wǎng)絡的魯棒性［24］.對于正相關的網(wǎng)絡，度大的節(jié)點往往與度大的節(jié)點相依.在隨機攻擊下，這樣的網(wǎng)絡會更加穩(wěn)健［25］；在蓄意攻擊下，這樣的網(wǎng)絡顯然會更加脆弱.對于負相關的網(wǎng)絡，相依節(jié)點對的度之和會變得更加均勻，這樣導致在蓄意攻擊下網(wǎng)絡是更加脆弱還是更加穩(wěn)健，這是一個值得研究的問題.還有需要注意的是，這里僅僅依據(jù)節(jié)點的度進行加權，是否有其它加權方法可以找到更加有效的攻擊手段，如節(jié)點的介數(shù)，這又是一個非常值得研究的問題.

［1］ Buldyrev S V，Parshani R，Paul G，et al.Catastrophic cascade of failures in interdependent networks［J］.Nature，2010，464（08932）：1025－1028.

［2］ Havlin S，Araujo N A M，Buldyrev S V，et al.Catastrophic cascade of failures in interdependent networks［DB／OL］.［2010－12－02］.http：／／arxiv.org／abs／1012.0206.

［3］ 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］.Phys Rev Lett，2010，105（4）：048701.

［4］ Huang X，Gao J，Buldyrev S V，et al.Robustness of interdependent networks under targeted attack［J］.Phys Rev E，2011，83（6）：065101.

［5］ 汪小帆，李翔，陳關榮.復雜網(wǎng)絡理論及其應用［M］.北京：清華大學出版社，2006.

［6］ Dorogovtsev S N，Goltsev A V，Mendes J F F.Critical phenomena in complex networks［J］.Rev Mod Phys，2008，80（4）：1275－1335.

［7］ 何大韌，劉宗華，汪秉宏.復雜系統(tǒng)與復雜網(wǎng)絡［M］.北京：高等教育出版社，2009.

［8］ Cohen R，Erez K，Avraham D，et al.Resilience of the internet to random breakdowns［J］.Phys Rev Lett，2000，85（21）：4626－4628.

［9］ Callaway D S，Newman M E J，Strogatz S H，et al.Network robustness and fragility：percolation on random graphs［J］.Phys Rev Lett，2000，85（25）：5468－5471.

［10］ Cohen R，Erez K，Avraham D，et al.Breakdown of the internet under intentional attack［J］.Phys Rev Lett，2001，86（16）：3682－3685.

［11］ Stauffer D，Aharony A.Introduction to percolation theory［M］.2nd ed.London：Taylor ＆Francis，1992.

［12］ Motter A E，Lai Y C.Cascade－based attacks on complex networks［J］.Phys Rev E，2002，66（6）：065102.

［13］ Zhao L，Park K，Lai Y C.Attack vulnerability of scale－free networks due to cascading breakdown［J］.Phys Rev E，2004，70（3）：035101.

［14］ Zhao L，Park K，Lai Y C，et al.Tolerance of scale－free networks against attack－induced cascades［J］.Phys Rev E，2005，72（2）：025104.

［15］ Motter A E.Cascade control and defense in complex networks［J］.Phys Rev Lett，2004，93（9）：098701.

［16］ Wang W X，Chen G.Universal robustness characteristic of weighted networks against cascading failure［J］.Phys Rev E，2008，77（2）：026101.

［17］ Yang R，Wang W X，Lai Y C，et al.Optimal weighting scheme for suppressing cascades and traffic congestion in complex networks［J］.Phys Rev E，2009，79（2）：026112.

［18］ Wang W X，Lai Y C.Abnormal cascading on complex networks［J］.Phys Rev E，2009，80（3）：036109.

［19］ Watts D J.A simple model of global cascades on random networks［J］.PNAS，2002，99（9）：5766－5771.

［20］ Dong G G，Gao J X，Tian L X，et al.Percolation of partially interdependent networks under targeted attack［J］.Phys Rev E，2012，85（1）：016112.

［21］ Parshani R，Buldyrev S V，Havlin S.Critical effect of dependency groups on the function of networks［J］.P NAS，2011，108（3）：1007－1010.

［22］ Son S W，Grassberger P，Paczuski M.Percolation transitions are not always sharpened by making networks interdependent［J］.Phys Rev Lett，2011，107（19）：195702.

［23］ Gao J，Buldyrev S V，Havlin S，et al.Robustness of a network of networks［J］.Phys Rev Lett，2011，107（19）：195701.

［24］ 史定華.網(wǎng)絡度分布理論［M］.北京：高等教育出版社，2011.

［25］ Buldyrev S V，Shere N W，Cwilich G A.Interdependent networks with identical degrees of mutually dependent nodes［J］.Phys Rev E，2011，83（1）：016112.