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

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

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

1 相依網(wǎng)絡(luò)的魯棒性研究進(jìn)展

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié) 論

本文比較了相依網(wǎng)絡(luò)在幾種攻擊策略下的魯棒性，發(fā)現(xiàn)了考慮相依節(jié)點(diǎn)對度特性的攻擊策略比考慮單側(cè)節(jié)點(diǎn)度特性的攻擊策略更有效.這項(xiàng)工作對于理解相依網(wǎng)絡(luò)級聯(lián)失效的過程有著重要的作用，為找到相依網(wǎng)絡(luò)的弱點(diǎn)并進(jìn)行有效的保護(hù)和攻擊提供了有益的提示.但是，本文僅僅研究了相依隨機(jī)網(wǎng)絡(luò)的魯棒性，其它復(fù)雜網(wǎng)絡(luò)如無標(biāo)度網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)的魯棒性還有待進(jìn)一步研究［5－7］.此外，目前研究的是相依節(jié)點(diǎn)度不相關(guān)的網(wǎng)絡(luò)，今后還將研究相依網(wǎng)絡(luò)度相關(guān)網(wǎng)絡(luò)的魯棒性［24］.對于正相關(guān)的網(wǎng)絡(luò)，度大的節(jié)點(diǎn)往往與度大的節(jié)點(diǎn)相依.在隨機(jī)攻擊下，這樣的網(wǎng)絡(luò)會更加穩(wěn)?。?5］；在蓄意攻擊下，這樣的網(wǎng)絡(luò)顯然會更加脆弱.對于負(fù)相關(guān)的網(wǎng)絡(luò)，相依節(jié)點(diǎn)對的度之和會變得更加均勻，這樣導(dǎo)致在蓄意攻擊下網(wǎng)絡(luò)是更加脆弱還是更加穩(wěn)健，這是一個值得研究的問題.還有需要注意的是，這里僅僅依據(jù)節(jié)點(diǎn)的度進(jìn)行加權(quán)，是否有其它加權(quán)方法可以找到更加有效的攻擊手段，如節(jié)點(diǎn)的介數(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］ 汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京：清華大學(xué)出版社，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］ 何大韌，劉宗華，汪秉宏.復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)［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)絡(luò)度分布理論［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.