可變負載無標度網絡魯棒性分析

徐 野，李 青

(沈陽理工大學 信息科學與工程學院，遼寧 沈陽 110159)

相繼故障[1]是與網絡上的傳播行為有很多相似之處的一種現象，普遍發(fā)生在各種關鍵生命線系統(tǒng)網絡中，如供水網、供氣網、交通網、Internet、通信網等。這些網絡有一個共同點：存在大量的負載，并且負載都是動態(tài)變化的，而且節(jié)點承受負載的能力是有限的。相繼故障[2]是指復雜網絡中的一些節(jié)點或者邊由于負責過大崩潰后，會通過節(jié)點或者邊之間的耦合(連接)關系，造成“流”在節(jié)點或者邊上重新分布，進而引發(fā)其他節(jié)點或者邊發(fā)生故障，產生連鎖反應，最終導致相當一部分節(jié)點甚至整個網絡的崩潰。因此，節(jié)點或者邊的崩潰會在整個網絡上傳播開，造成對網絡的嚴重破壞。

復雜網絡研究無論在理論上還是實際應用中都有著重要的意義。從理論上講，復雜網絡具有三個主要特征：小世界效應、無標度特性和高集聚性[3]。無標度網絡具有較小的最短路徑且分布呈冪率分布。已有研究結果表明，小的最短路徑能夠使系統(tǒng)低層次的因素之間的局部交互作用更加密集頻繁，從而在系統(tǒng)層次上會涌現出更多的性質。這對于網絡的同步行為和疾病傳播行為都有顯著的影響，而無標度網絡的異構性使得疾病傳播幾乎沒有閾值，因此控制流行病就不僅僅是提高醫(yī)療水平的問題，而是如何切斷網絡中的關鍵連接的問題。從應用上講，Internet上發(fā)生數據擁塞、交通網絡中的堵塞等不僅與設計的控制管理協議有關，與整個網絡的布局也密切相關。

1999年10月，美國圣母大學物理系的Barabasi教授及其博士生Albert在“Science”雜志上發(fā)表了一篇題為《隨機網絡中標度的涌現》的論文，這篇論文揭示了復雜網絡的無標度特性，建立了無標度模型[4]。Barabasi和Albert指出了現實中的網絡有兩個方面在以前的網絡模型中未包含進去。首先，沒有考慮現實網絡的增長性，相對而言，大部分現實網絡是開放的，即他們是由不斷加進系統(tǒng)中的新節(jié)點組成，因此節(jié)點數目N的增長伴隨網絡的終生。其次，沒有考慮網絡的優(yōu)先連接，大部分現實網絡展現出擇優(yōu)連接的性質。

本文基于BA無標度網絡模型，通過對BA無標度網絡的節(jié)點引入相關性描述，通過模擬，得到BA無標度網絡在受到攻擊時的魯棒性性能變化。通過仿真發(fā)現，提高網絡魯棒性的方法不需要對網絡中的所有節(jié)點進行，而只需對其中最為關鍵的幾個中心節(jié)點進行改善可以得到滿意的效果。

1 BA無標度模型

1999年，Barabasi和Albert[4]在Science上發(fā)表文章指出，許多現實世界的復雜網絡并非是規(guī)則網絡和隨機網絡，而是屬于無標度(scale-free)網絡，并對這樣一類網絡的特征量進行了一些研究，指出了決定互聯網、萬維網和科學家合作研究網絡等具有無標度特性的兩個基本性質：節(jié)點增長與優(yōu)先連接。BA無標度網絡模型不同于隨機網絡模型，隨機網絡模型不考慮新增節(jié)點的優(yōu)先連接性，從而得到的度分布是指數分布。

BA無標度網絡的生成算法主要包括下面兩個部分[5-15]：

1)增長：假設網絡最初有m0個節(jié)點。每次加入一個新的節(jié)點，每次加入的新節(jié)點通過m(m≤m0)條新加入的連接邊與網絡中已有的m個節(jié)點相連。

2)優(yōu)先連接：當挑選哪些節(jié)點與新加入的節(jié)點相連接時，假設與節(jié)點i相連接的概率∏(ki)都正比于節(jié)點i的度ki，

(1)

根據上述步驟重復t次后生成得到一個有N=t+m0個節(jié)點和mt條邊的網絡，圖1舉例說明了當m=m0=2時，初始網絡為孤立節(jié)點的BA無標度網絡的演化及過程。初始網絡有兩個節(jié)點，每次新增加的一個節(jié)點按優(yōu)先連接機制與網絡中已經存在的兩個節(jié)點相連。

其度分布即節(jié)點具有度為k的概率為P(k)～2m2k-γ,γ=γBA=3,這種度分布成為無標度的冪率分布，并且標度指數γ與算法中僅有的參數m無關。

圖1 BA無標度網絡的演示示例

2 魯棒性

衡量網絡的魯棒性一般有兩個參數：級聯失效過程中的最大連通子圖大小以及滲流閾值，第一個參量的值越大，則網絡的魯棒性就越好。本文使用網絡的最大連通子圖規(guī)模來測量網絡被攻擊后的性能。

在網絡A=(V，{Edge})中[16]，e和v都是網絡的節(jié)點，若存在交替的頂點和邊的序列，則e和v是連通的。如果網絡A的每兩點間都是連通，那么A就是一個連通圖。若A不是連通圖時，整個網絡被分為若干個連通子圖，而包含節(jié)點最多的子圖就是最大連通子圖。最大連通子圖也被稱為“巨組件(giant component)”，巨組件越大，則網絡的連通性就越好，所以其規(guī)模也可以度量網絡的性能。G表示網絡的魯棒性，定義為相繼故障之后和之前，網絡中最大連通子圖的大小比值，即：

(2)

這里N和N′分別為相繼故障發(fā)生前后的網絡中最大連通子圖的節(jié)點數。若G≈1,則表示網絡保持完整。若G≈0，則表示受攻擊后網絡變?yōu)楣铝⒐?jié)點。

3 魯棒性與負載和攻擊標度的關系

實驗環(huán)境：CPU為Intel Core Duo，內存2G，操作系統(tǒng)為Windows XP，仿真軟件為Matlab。其中整體算法如圖2所示。

圖2 程序的整體算法流程

下面研究網絡負載w和攻擊標度tao對網絡魯棒性的影響。先生成一個節(jié)點N=100，m0=5,m=2的BA無標度經典網絡，見圖3。

圖3 節(jié)點N=100，m0=5,m=2的BA無標度經典網絡

分別設置網絡負載w=0(網絡零負載)和w=1(網絡滿負載)，對多次結果進行平均統(tǒng)計得到圖4a和圖4b，從圖4a可以看出對于tao=1(隨機攻擊)，G的值遠遠高于tao=0(蓄意攻擊)的G值；從圖4b可以看出對于不管隨機攻擊還是蓄意攻擊，G值很快變?yōu)?。

圖4 w=0和w=1時摧毀點與G關系

生成一個初始節(jié)點m0=10，m=2，網絡節(jié)點數N=200，直到G小于0.1，程序結束運行。把攻擊標度tao分別設為0和1，并對多次結果進行平均統(tǒng)計，得到圖5a和圖5b。從圖5a可以看出對于蓄意攻擊，網絡滿負載相對網絡零負載的最大連通子圖下降的較緩慢，但是被摧毀的節(jié)點數也很少降為0。從圖5b可以看出隨機攻擊，網絡滿負載比網絡零負載的最大連通子圖下降快很多。

圖5 tao=0和tao=1時摧毀點與G關系

綜上所述，可以得到結論：(1)BA無標度網絡受網絡攻擊標度影響較大，隨著攻擊標度大小的增加，網絡的魯棒性增加，當網絡受到隨機攻擊時網絡表現出很強的魯棒性，而受到蓄意攻擊時，網絡的脆弱性很強；(2)BA無標度網絡受網絡負載影響相對網絡攻擊標度來的小。隨著網絡負載的增加，網絡魯棒性下降，當網絡負載大于0.6時，網絡魯棒性很快下降，表明系統(tǒng)已經分裂為許多孤立的部分而無法正常工作，可以用控制網絡負載變化時的網絡拓撲結構的變化來分析相繼故障的發(fā)生過程[17]。

4 結束語

以BA無標度網絡為研究對象，給出了BA無標度網絡的構造算法。用受攻擊前后的最大連通子圖的大小比值G作為衡量標準，研究了BA無標度網絡在遭遇隨機攻擊和蓄意攻擊后網絡負載對G的影響。仿真結果證明了無標度網絡對隨機破壞有很高的抗毀性，而對蓄意攻擊網絡則顯得十分脆弱。

[1] 王建偉，榮莉莉.超負荷邊帶有崩潰概率的相繼故障模型上襲擊策略研究[J].中國管理科學，2009，27(6)：247-156.

[2] 王建偉，榮莉莉，王鐸.基于節(jié)點局域特征的復雜網絡上相繼故障模型[J].管理科學學報，2010，13(8)：42-50.

[3] 郭世譯.復雜網絡基礎理論[M].北京：科學出版社，2012：37-38.

[4] Barabasi AL,Albert R.Emergence of scaling in random network[J].Nature,1999,393(6684):440-442.

[5] 潘灶烽.加權復雜網絡的建模研究[D].上海：上海交通大學，2005.

[6] 彭剛.因特網拓撲結構復雜性研究[D].武漢：華中師范大學，2006.

[7] 何士產.復雜網絡的耗散結構特征與矩陣表示研究[D].武漢：武漢理工大學，2007.

[8] 冷延東.Ad Hoc互連網絡小世界特性的研究[D].南京：南京郵電大學，2008.

[9] 彭俊.復雜網絡的拓撲結構及傳播模型的研究[D].西安：西安電子科技大學，2009.

[10]劉自然.加反饋機制的復雜網絡動力學[D].湖南：湖南師范大學，2007.

[11]田蓓蓓.復雜網絡傳播行為的元胞自動機模擬研究[D].上海：上海大學，2008.

[12]周杰.復雜系統(tǒng)中的信息傳播研究[D].武漢：華中師范大學，2008.

[13]吳楠.復雜網絡理論在貴州輸配電網中的應用基礎研究[D].貴州：貴州大學，2008.

[14]王茹.復雜網絡Opinion動力學研究[D].武漢：華中師范大學，2009.

[15]黃丹.考慮代價的無標度網絡攻擊性研究[D].武漢：中南民族大學，2011.

[16]Moreno Y,Gomez J B,Pacheco A F.Instability of scale-free networks under node-breaking avalanches[J].Europhys.Lett.,2002,58(4):630-636.

[17]汪小帆，李翔，陳關榮.復雜網絡理論及其應用[M].北京：清華大學出版社，2006:102.