復雜網絡生存性評估方法研究

摘要:該文針對復雜網絡的特點，首先給出了復雜網絡生存性的一個新測度——容忍度。在此基礎之上，給出了生存性測度的新定義，針對復雜網絡無標度性的特點，給出了復雜網絡生存性評估的新方法，并以互聯網抽樣數據為例進行了網絡生存性分析。最后對復雜網絡生存性研究的思路進行了探討，指出從網絡拓撲結構出發，研究拓撲結構的各種屬性對網絡生存性的影響，將是復雜網絡生存性研究的一個有效而新穎的思路。

關鍵詞:復雜網絡;生存性;無標度性

中圖分類號:TP311 文獻標識碼:A 文章編號:1009-3044(2010)01-241-03

The Research of Complex Network Survivability Assessment Method

XIAO Wei， TAN Min-sheng， DING Lin

(School of Computer Science Technology， University of South China， Hengyang 421001， China)

Abstract: In this paper， a new measure of complex network survivability is Indicated. Basing on this measure， a new definition of survivability is proposed， a noval evaluating method of survivability are proposed for the scarefree characteristic of complex network and the example of sampling data from the Internet is given. At last， it is indicated that it is a new and effective way to research the influence of topology parameters of complex network to its survivability.

Key words: complex networks; survivability; scale-free networks

在人類生活的真實世界當中，有許多系統諸如電力網、交通網、Internet 、萬維網都可以看成復雜網絡[1-4]。雖然這些大型復雜網絡在現代生活中占有舉足輕重的地位，但是它們的生存性卻不容樂觀。特別是互聯網，它以異乎尋常的速度自由發展，沒有整體規劃，沒有節制，像一棵巨大的蔓藤植物一樣四處蔓延，釣魚網站、偷偷安裝的木馬、危險的病毒，互聯網上的危險也開始隨之增加，最終將無處不在。上個世紀末，Albert和Barabasi等人在對互聯網的結點的度分布研究中發現復雜網絡的無標度特性，即無標度網絡(scalefree networks)。[5]他們發現極少數的節點擁有極大量的連接，而絕大多數節點的連接數只是寥寥幾個。那些連接數量大的極少數節點，就是互聯網的樞紐。實質上整個互聯網的性能，只依賴于這極少數的節點。哪怕只有少數關鍵節點隨機失效，網絡的性能立刻就會大幅下滑，如果這些關鍵節點同時失效的話，互聯網將會瞬間崩潰，斷裂成一個一個的信息孤島。因此，必須衡量網絡在發生隨機失效后能夠繼續提供一定服務的能力，衡量網絡這種能力的性質就是網絡的生存性。隨著人類社會的日益發展和人們生活水平的提高，復雜網絡生存性研究的重大理論意義和應用價值已經凸現，成為復雜網絡研究領域的熱點之一。

1 復雜網絡生存性研究現狀

1.1 復雜網絡生存性定義及測度

一般認為“生存性”是指在網絡發生故障后能盡快利用網絡中空閑資源為受影響的業務

一個可以接受的業務水平的能力。它主要是指通信網絡在隨機破壞作用下仍可繼續提供服務

重新選路，使業務繼續進行，以減少因故障而造成的社會影響和經濟上的損失，使網絡維持的能力，包括期望生存性、最壞情況下的生存性、r-百分比生存性、零生存概率等。復雜網絡生存性測度也有很多，主要有平均路徑長度、聚類系數、度與度分布、介數與介數分布等等。

1)平均路徑長度

在有N個節點的復雜網絡中，節點i與節點j的最短路徑定義為所有連通i到j的通路中，所經過的其它節點最少的路徑的長度，記為dij。網絡中任意兩個節點之間的最短路徑的平均值，稱為平均路徑長度，記為L，即:

2)聚類系數

在有N個節點的網絡中，若第i個節點的度為ki，在由這ki個鄰居節點構成的子網中，實際存在的邊ei與這ki個節點最多能構成的邊數的比值:，稱為第i個節點的聚類系數。整個網絡的聚類系數C定義為所有節點聚類系數的平均值，即:

3)度與度分布

節點i與其它節點構成的邊的總數稱為節點i的度，記為ki。網絡中所有節點的度的平均值稱為網絡的平均度，記為。節點度分布是指隨機選定的節點的度恰好為k的概率，即任意節點有k個鄰居節點的概率，記為P(k)。

4)介數

設網絡中節點i和節點j之間最短路徑的總數為Lij，而Lij之中經過節點v的最短路徑數為Lij(v)，則節點v的介數為Bv:

1.2 復雜網絡生存性傳統評價方法

Holme等[6]提出基于最短路徑長度的生存性評估方法，即用全局效率和最大連通子圖大小來衡量復雜網絡的網絡生存性，全局效率的定義如下:

其中:N為網絡節點總數目;dij為節點i和j之間的最短路徑長度。

這種生存性評估方法考慮到了節點和鏈路的失效性，但沒有考慮時延對生存性的影響，而且基于平均路徑長度來衡量網絡生存性，計算開銷很大。

2 復雜網絡生存性分析

這里給出復雜網絡生存性分析的基本假設:

1)網絡中節點只存在失效與未失效兩種狀態，除此之外無好壞之分;

2)節點間的鏈路也只存在失效與未失效兩種狀態，因而也是等價的;

3)考慮對時延的要求，即認為節點i與節點j進行有效通信其最短路徑少于T跳。

4)假設每次只有一個節點失效，考慮最壞情況下的網絡生存性，假設每次失效的節點都是當前網絡中最重要的節點，直到網絡崩潰。

5)網絡的崩潰條件是當節點實效后剩余網絡中最大連通子圖的節點總數與初始網絡的節點總數的百分比小于5%。

首先介紹一下跳面節點的概念:對一給定網絡G(N，E)，任意節點對之間都有一定跳數的距離，將與某一節點i具有相同跳數的所有節點稱為節點i具有該跳數的跳面節點。于是節點i與其余所有節點間的路徑聯系轉化為與其余所有節點跳面間的聯系，而各層跳面之間是以串聯關系連接起來。

每個跳面節點之間的連接情況反映出迂回路由情況，跳面內節點間連接鏈路越多，則迂回路由越多;相鄰兩個跳面之間節點的互聯情況反映出兩個跳面之間的有效鏈路情況，所有迂回路由都要經過這些鏈路，因而可反映出迂回路由的效果。為此，引入第m跳面節點到第(m+1)跳面節點間鏈路數歸一化因子μm。設第m跳面上的節點數目為nm，第(m+1)跳面上的節點數目為nm+1，兩跳面的連接鏈路數為Im，則第(m+1)跳面上節點數目與除一個節點i外其余節點數目(n-1)的比值為nm+1/(n-1)，兩跳面的鏈路數Im與兩跳面間最大鏈路數nm·nm+1的比值為Im/(nm·nm+1)，故歸一化因子μm定義為:

則節點i到所有跳面的連通度之和Si可定義為:

其中T為時延限制的跳數，μ(m-1)k為k個節點失效后(m-1)跳面上的歸一化因子，而網絡中最重要的節點為連通度Si最大的節點。

將(1)式代入(2)式可得

現在可以給出容忍度的定義:設CM(k)為初始網絡去除k個節點后最大連通子圖的生存性度量，由下式給出:

其中n是最大連通子圖的節點數，KT是指使網絡崩潰所要去除的節點的數目，稱KT為容忍度。

則復雜網絡G的生存性可定義為:

3 復雜網絡生存性評估方法

基于上一節生存性分析，可以得到復雜網絡生存性的評估步驟如下:

第一步:根據文獻[7]所提供的方法對初始網絡進行抽樣，得到抽樣網絡;

第二步:將抽樣后的網絡數據初始化，即給每個節點標定序號，計算所有節點的度值，并按度值給節點排序，確定時延要求的跳數T，為簡化運算，這里設T=1，置零k;

第三步:計算復雜網絡G中所有節點的連通度Si以及相應的CM(k);

第四步:根據Si的值判定最重要的節點，若有多個，則取序號最小的。去除最重要的節點后，判斷剩余網絡是否崩潰，若是，轉入第五步;若否，置k=k+1，轉入第三步;

第五步:由所有CM(k)的計算得到復雜網絡的生存性指標SM(G)。

從圖1和圖2可以看出抽樣后，網絡基本上符合復雜網絡的特征，同時節點數和邊數由原來的16807和26589縮減至1219和2358。

計算得到CM(0)=(1/1219)*(4715/1218)。由Si判定節點4(節點4的度為185，是所有節點中度最大的)為最重要的節點，將其去除得到新的網絡，得到剩余網絡中最大連通子圖有154個節點和183條邊，154/1219≈12.6%，網絡還未崩潰，繼續第三步。

計算得到CM(1)=(1/154)*(366/153)。由Si判定節點129(節點129的度為112，在所有節點的度中排第2位)為最重要的節點，將其去除得到新的網絡，得到剩余網絡中最大連通子圖有69個節點和70條邊，69/1219≈5.7%，網絡還未崩潰，繼續第三步。

計算得到CM(2)=(1/69)*(140/68)。由Si判定節點261(節點261的度為44)為最重要的節點，將其去除得到新的網絡，得到剩余網絡中最大連通子圖有24個節點和23條邊，24/1219≈2.0%<5%，網絡已經崩潰，轉入第五步。

計算得到SM(G)= [CM(0)+CM(1)+CM(2)]≈0.0485

對一個網絡的生存性進行分解分析有很多方法，用本文提出的方法，由于每次僅需要移除網絡中最重要的一個節點，因此分解過程變得非常簡單，在計算網絡生存性的過程中同時確定了最重要的節點，因此節省了大量的計算時間。

該方法將節點和鏈路連通因素進行了綜合考慮，提供了計算網絡生存性的一種方法，并且對時延因素進行了考慮。計算節點和網絡生存性的過程中，均進行了歸一化處理，便于與全連通網絡進行比較。當然，因為每次都是最重要的節點被移除，也就是最壞的情況發生，所以這里給出的是網絡生存性的下限值。

4 結束語

該文對復雜網絡生存性進行了論述，提出了一種復雜網絡生存性的定量評估方法，給出了相關的生存性評價指標，但這還只屬于復雜網絡生存性理論的基礎研究，如何將這種方法與邊權、網絡花費、優先級別和硬件可靠性結合起來建立復雜網絡全面而有效的評價模型需要做進一步的研究。

參考文獻:

[1] Albert R，Albert I and Nakarado G L.Structural vulnerability of the North American power grid[J].Phys.Rev.E，2004，69:025103.

[2] 郭雷.復雜網絡[M].上海:上海科技教育出版社，2006:186.

[3] V′azquez A，Pastor-Satorras R and Vespignani A.Large-scale topological and dynamical properties of the Internet[J].Phys.Rev.E，2002，65:066130.

[4] Adamic L A and Huberman B A.Power-Law Distribution of the World-Wide Web[J].Science，2000，287:2115a.

[5] Barabási，A.L.and Albert，R.Emergence of Scaling in Random Networks[J].Science，1999，286:509-512.

[6] Holme P，Kim B J，Yoon C N，et al.Attack vulnerability of complex networks[J].Phys.Rev.E，2002，65(5):056109.

[7] Vaishnavi Krishnamurthy，Michalis Faloutsos，Marek Chrobak etc.Sampling large Internet topologies for simulation purposes[J].Computer Networks，2007，51: 4284-4302.