徐 野，李 青

(沈陽(yáng)理工大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110159)

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

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

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

本文基于BA無(wú)標(biāo)度網(wǎng)絡(luò)模型，通過對(duì)BA無(wú)標(biāo)度網(wǎng)絡(luò)的節(jié)點(diǎn)引入相關(guān)性描述，通過模擬，得到BA無(wú)標(biāo)度網(wǎng)絡(luò)在受到攻擊時(shí)的魯棒性性能變化。通過仿真發(fā)現(xiàn)，提高網(wǎng)絡(luò)魯棒性的方法不需要對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行，而只需對(duì)其中最為關(guān)鍵的幾個(gè)中心節(jié)點(diǎn)進(jìn)行改善可以得到滿意的效果。

1 BA無(wú)標(biāo)度模型

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

BA無(wú)標(biāo)度網(wǎng)絡(luò)的生成算法主要包括下面兩個(gè)部分[5-15]：

1)增長(zhǎng)：假設(shè)網(wǎng)絡(luò)最初有m0個(gè)節(jié)點(diǎn)。每次加入一個(gè)新的節(jié)點(diǎn)，每次加入的新節(jié)點(diǎn)通過m(m≤m0)條新加入的連接邊與網(wǎng)絡(luò)中已有的m個(gè)節(jié)點(diǎn)相連。

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

(1)

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

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

圖1 BA無(wú)標(biāo)度網(wǎng)絡(luò)的演示示例

2 魯棒性

衡量網(wǎng)絡(luò)的魯棒性一般有兩個(gè)參數(shù)：級(jí)聯(lián)失效過程中的最大連通子圖大小以及滲流閾值，第一個(gè)參量的值越大，則網(wǎng)絡(luò)的魯棒性就越好。本文使用網(wǎng)絡(luò)的最大連通子圖規(guī)模來(lái)測(cè)量網(wǎng)絡(luò)被攻擊后的性能。

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

(2)

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

3 魯棒性與負(fù)載和攻擊標(biāo)度的關(guān)系

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

圖2 程序的整體算法流程

下面研究網(wǎng)絡(luò)負(fù)載w和攻擊標(biāo)度tao對(duì)網(wǎng)絡(luò)魯棒性的影響。先生成一個(gè)節(jié)點(diǎn)N=100，m0=5,m=2的BA無(wú)標(biāo)度經(jīng)典網(wǎng)絡(luò)，見圖3。

圖3 節(jié)點(diǎn)N=100，m0=5,m=2的BA無(wú)標(biāo)度經(jīng)典網(wǎng)絡(luò)

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

圖4 w=0和w=1時(shí)摧毀點(diǎn)與G關(guān)系

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

圖5 tao=0和tao=1時(shí)摧毀點(diǎn)與G關(guān)系

綜上所述，可以得到結(jié)論：(1)BA無(wú)標(biāo)度網(wǎng)絡(luò)受網(wǎng)絡(luò)攻擊標(biāo)度影響較大，隨著攻擊標(biāo)度大小的增加，網(wǎng)絡(luò)的魯棒性增加，當(dāng)網(wǎng)絡(luò)受到隨機(jī)攻擊時(shí)網(wǎng)絡(luò)表現(xiàn)出很強(qiáng)的魯棒性，而受到蓄意攻擊時(shí)，網(wǎng)絡(luò)的脆弱性很強(qiáng)；(2)BA無(wú)標(biāo)度網(wǎng)絡(luò)受網(wǎng)絡(luò)負(fù)載影響相對(duì)網(wǎng)絡(luò)攻擊標(biāo)度來(lái)的小。隨著網(wǎng)絡(luò)負(fù)載的增加，網(wǎng)絡(luò)魯棒性下降，當(dāng)網(wǎng)絡(luò)負(fù)載大于0.6時(shí)，網(wǎng)絡(luò)魯棒性很快下降，表明系統(tǒng)已經(jīng)分裂為許多孤立的部分而無(wú)法正常工作，可以用控制網(wǎng)絡(luò)負(fù)載變化時(shí)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化來(lái)分析相繼故障的發(fā)生過程[17]。

4 結(jié)束語(yǔ)

以BA無(wú)標(biāo)度網(wǎng)絡(luò)為研究對(duì)象，給出了BA無(wú)標(biāo)度網(wǎng)絡(luò)的構(gòu)造算法。用受攻擊前后的最大連通子圖的大小比值G作為衡量標(biāo)準(zhǔn)，研究了BA無(wú)標(biāo)度網(wǎng)絡(luò)在遭遇隨機(jī)攻擊和蓄意攻擊后網(wǎng)絡(luò)負(fù)載對(duì)G的影響。仿真結(jié)果證明了無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)隨機(jī)破壞有很高的抗毀性，而對(duì)蓄意攻擊網(wǎng)絡(luò)則顯得十分脆弱。

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

[2] 王建偉，榮莉莉，王鐸.基于節(jié)點(diǎn)局域特征的復(fù)雜網(wǎng)絡(luò)上相繼故障模型[J].管理科學(xué)學(xué)報(bào)，2010，13(8)：42-50.

[3] 郭世譯.復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論[M].北京：科學(xué)出版社，2012：37-38.

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

[5] 潘灶烽.加權(quán)復(fù)雜網(wǎng)絡(luò)的建模研究[D].上海：上海交通大學(xué)，2005.

[6] 彭剛.因特網(wǎng)拓?fù)浣Y(jié)構(gòu)復(fù)雜性研究[D].武漢：華中師范大學(xué)，2006.

[7] 何士產(chǎn).復(fù)雜網(wǎng)絡(luò)的耗散結(jié)構(gòu)特征與矩陣表示研究[D].武漢：武漢理工大學(xué)，2007.

[8] 冷延?xùn)|.Ad Hoc互連網(wǎng)絡(luò)小世界特性的研究[D].南京：南京郵電大學(xué)，2008.

[9] 彭俊.復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)及傳播模型的研究[D].西安：西安電子科技大學(xué)，2009.

[10]劉自然.加反饋機(jī)制的復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)[D].湖南：湖南師范大學(xué)，2007.

[11]田蓓蓓.復(fù)雜網(wǎng)絡(luò)傳播行為的元胞自動(dòng)機(jī)模擬研究[D].上海：上海大學(xué)，2008.

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

[13]吳楠.復(fù)雜網(wǎng)絡(luò)理論在貴州輸配電網(wǎng)中的應(yīng)用基礎(chǔ)研究[D].貴州：貴州大學(xué)，2008.

[14]王茹.復(fù)雜網(wǎng)絡(luò)Opinion動(dòng)力學(xué)研究[D].武漢：華中師范大學(xué)，2009.

[15]黃丹.考慮代價(jià)的無(wú)標(biāo)度網(wǎng)絡(luò)攻擊性研究[D].武漢：中南民族大學(xué)，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]汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006:102.