摘 要：本文對復雜網絡魯棒性研究及其常用指標做一定的系統(tǒng)梳理，簡介復雜網絡魯棒性研究進展，分析探討復雜網絡魯棒性研究的一些研究成果，討論提出進一步相關深入研究方向。

關鍵詞：復雜網絡 魯棒性 隨機故障 蓄意攻擊

中圖分類號：TP39 文獻標識碼：A 文章編號：1672-3791（2012）11（b）-0006-01

復雜網絡具自組織、自相似、吸引子、小世界、無標度中部分或全部性質。網絡魯棒性指在網絡中的節(jié)點（邊）發(fā)生隨機故障或遭受蓄意攻擊的條件下，網絡維持其功能的能力。為深入展開相關研究，有必要進行相應基礎準備工作，本文對復雜網絡魯棒性研究及其常用指標做一定的系統(tǒng)梳理，簡介復雜網絡魯棒性研究進展，分析探討復雜網絡魯棒性研究的一些研究成果，討論提出進一步相關深入研究方向。

1 復雜網絡魯棒性相關研究術語與指標

大多數(shù)容錯性高的系統(tǒng)有一共同特點：其功能通過高度互聯(lián)的復雜網絡保證。復雜網絡的拓撲結構與魯棒性與功能性緊密相關，在系統(tǒng)的可靠性分析設計中具重要意義。為進一步深入展開復雜網絡魯棒性研究，分析研究不同復雜網絡的結構特征、共性與特性的基礎與工具的相關常用術語與測度指標有：節(jié)點數(shù)N、節(jié)點的度K、平均度、度分布、網絡的平均距離與網絡平均路徑長度L、聚類系數(shù)、介數(shù)、小世界效應、無標度特性、混合模式特性，度相關特性，超小世界性質、若移走少量節(jié)點后網絡中的絕大部分節(jié)點仍是連通的則稱該網絡的連通性對節(jié)點故障具有魯棒性、隨機故障與蓄意攻擊、最大連通子圖的相對大小S、網絡的度一度關聯(lián)性、網絡的富人俱樂部效應、網絡的最大連通分量、網絡受攻擊前后的平均最短路徑長度之比與聚類系數(shù)之比等。

2 復雜網絡的魯棒但又脆弱性研究

Albert與Barabasi等分別把ER隨機網絡和無標度網絡置于隨機故障與蓄意攻擊下，比較了兩類網絡的連通性對考慮兩類節(jié)點去除策略的魯棒性[1]：完全隨機去除網絡中的一部分節(jié)點模擬隨機故障；按節(jié)點連接度從大到小順序從去除網絡中度最高的節(jié)點開始，有意識去除網絡中一部分度最高的節(jié)點模擬蓄意攻擊。假設去除的節(jié)點數(shù)占原始網絡總節(jié)點數(shù)的比例為f，則可用最大連通子圖的相對大小S和平均路徑長度L與f的關系來度量網絡的魯棒性。相關仿真表明ER和BA無標度網絡之間存在顯著差異。無標度網絡對隨機節(jié)點故障具有極高的魯棒性：與隨機圖相比，最大連通子圖的相對大小S在相對高得多的f值時才下降到零而其平均路徑長度L的增長則要緩慢得多。無標度網絡相對隨機網絡的這種對隨機故障的高度魯棒性、穩(wěn)健性、抗毀性源于無標度網絡節(jié)點連接度大小的多樣性、網絡度分布的非均勻性的特點：內部存在中心節(jié)點，這些高度連通的節(jié)點使網絡能連成一體。絕大多數(shù)節(jié)點的度相對很小而只有少量節(jié)點的度相對很大。隨機故障并不區(qū)分普通節(jié)點和中心節(jié)點，所有節(jié)點發(fā)生故障的概率相同，因小節(jié)點數(shù)量多，更多隨機故障影響小節(jié)點。無尺度網絡不怕隨機故障，當f較小時，隨機選取的節(jié)點都是度很小的節(jié)點，即使隨機去除這些大量節(jié)點無標度網絡仍可保持基本連通性。而正是這種生存能力、容錯性與非均勻性使無標度網絡比隨機網絡對蓄意攻擊具天生的高度脆弱性：無需刪除一無尺度網絡的大量節(jié)點，只要蓄意去除網絡中極少量度最大的連通性最強的中心節(jié)點就會對整個網絡的連通性產生大的影響，就能到達臨界點，網絡很快分裂成相互無法通訊的孤島而立即癱瘓。而因隨機網絡節(jié)點連接度大小的同質性，隨機去除同樣多的節(jié)點則可使同樣規(guī)模的隨機網絡分成多個孤立的子網。

3 基于其他指標及滲流理論與隨機圖理論等對網絡魯棒性的研究

現(xiàn)實世界中許多復雜系統(tǒng)都很魯棒，對故障呈現(xiàn)出很大程度的抗毀能力。Albert等的研究激起了眾多學者對復雜網絡及其魯棒性、健壯性、抗毀性、可靠性、穩(wěn)健性等的研究興趣與相關系統(tǒng)研究，結果幾乎都與Albert等的發(fā)現(xiàn)一致[2～3]，為各種復雜系統(tǒng)的設計保護提供了寶貴啟示。研究結論： 隨著增加BA網絡容錯性增加，節(jié)點數(shù)N對網絡容錯性無影響；當較小時BA網絡表現(xiàn)出較好的抗攻擊性，但較大時網絡的抗攻擊性明顯變差；隨著節(jié)點數(shù)N的增加網絡的抗攻擊性下降?；跐B流與隨機圖理論等對網絡魯棒性的理論分析也有不少研究。隨機圖理論研究的一個重要發(fā)現(xiàn)是ER網絡當連邊概率p值不超過臨界概率pc（滲流閾值）時，只可能存在少數(shù)邊，網絡只可能由產生少數(shù)孤立的節(jié)點相連接的小集群組成；但當超過pc時，ER隨機圖的性質發(fā)生突變，出現(xiàn)利用邊互相連接的節(jié)點的滲流（無限）集群，巨大節(jié)點集群將擴展到整個網絡。這一現(xiàn)象與數(shù)理中研究較多的滲流轉變理論相似。相關研究對完全一般度分布的隨機圖上的站點與連接滲流等及模型進行了討論[2]。

4 結語

基于上述指標參數(shù)或衡量標準，已有一些相關研究成果初步揭示復雜網絡魯棒性的基本原則，理解了復雜網絡對于保障承受力所起的作用，拓展了對網絡魯棒性的認識，相關研究日益吸引了更多研究者的注意，但相關研究面寬泛而不夠深入、原創(chuàng)性工作較少，未形成完整理論體系。盡管這些特性對理解網絡魯棒性有重要幫助，但網絡上的流量及成本也不可忽視，網絡中那些負載著流量的鏈節(jié)及其被使用程度對分析網絡魯棒性有明顯作用，網絡不僅是錯綜復雜的骨架，不應僅局限于網絡結構范疇，應著眼于網絡鏈節(jié)上發(fā)生的變化（流量）過程，在一些經典基礎網絡中，成本估計會影響行為從而影響網絡流量分布，且會影響網絡魯棒性評估，故要研究網絡魯棒性這些因素均應考慮，而上述因素卻往往被忽略?？紤]節(jié)點負載容量有限、節(jié)點負載與網絡拓撲及相應人為策略選擇調整的關聯(lián)動態(tài)變化的網絡攻擊時的最優(yōu)應急策略措施等也少有研究。如何規(guī)劃國家基礎設施網絡，使其在面臨自然災害時也能正常工作；如何在網絡發(fā)生故障時采取合理應急預案，避免造成整個網絡的級聯(lián)崩潰；如何通過魯棒性分析識別網絡中的薄弱環(huán)節(jié)或關鍵單元，以采取保護或優(yōu)化措施提高網絡魯棒性；如何結合網絡魯棒性于網絡傳播研究；如何轉化為應用技術等方向均有待深入研究。

參考文獻

[1]Albert，R.，Jeong，H.，Barabasi A.L.Attack and error tolerance of complex networks[J].Nature，2000，406：387-482.

[2]Callway D S， Newman M E J， Strogatz S H， Watts D J. Network robustness and fragility： Percolation on random graphs [J].Phys.Rev.Lett.，2000，85（25）：5468-5471.

[3]Bollobas B， Riodan O. Robustness and vulnerability of scale-free random graphs[J].Internet Math.，2003，1：1-35.