基于復(fù)雜網(wǎng)絡(luò)病毒傳播模型的免疫策略研究

關(guān)風(fēng)嬌，陳新一

(西北民族大學(xué)中國(guó)民族信息技術(shù)研究院，甘肅蘭州730030)

基于復(fù)雜網(wǎng)絡(luò)病毒傳播模型的免疫策略研究

關(guān)風(fēng)嬌，陳新一

(西北民族大學(xué)中國(guó)民族信息技術(shù)研究院，甘肅蘭州730030)

復(fù)雜網(wǎng)絡(luò)理論促進(jìn)了病毒傳播的進(jìn)一步認(rèn)識(shí)，文章基于復(fù)雜網(wǎng)絡(luò)中免疫策略理論提出了改進(jìn)的免疫方法——三階雙免疫策略.它是對(duì)網(wǎng)絡(luò)中任意抽得的節(jié)點(diǎn)中最大度節(jié)點(diǎn)及其三階鄰居節(jié)點(diǎn)一起實(shí)施免疫策略，是對(duì)雙免疫策略的進(jìn)一步改進(jìn).研究發(fā)現(xiàn)，與傳統(tǒng)的隨機(jī)免疫、經(jīng)典的熟人免疫策略、二階雙免疫策略相比，文章提出的三階免疫獲得了較好的免疫效果.

復(fù)雜網(wǎng)絡(luò)；免疫策略；三階雙免疫；無標(biāo)度網(wǎng)絡(luò)

0 引言

病毒的傳播處處可見，在生物界和計(jì)算機(jī)等眾多領(lǐng)域得到了廣泛關(guān)注，在復(fù)雜網(wǎng)絡(luò)中個(gè)體被抽象為節(jié)點(diǎn)，它們的鏈接被視為邊，這些理論知識(shí)增加了學(xué)者對(duì)病毒傳播的認(rèn)識(shí)，推動(dòng)了免疫策略研究的進(jìn)程.復(fù)雜網(wǎng)絡(luò)是一個(gè)包含大量個(gè)體及其個(gè)體間相互作用的復(fù)雜系統(tǒng)[1]，把復(fù)雜網(wǎng)絡(luò)理論應(yīng)用于病毒傳播模型的研究，進(jìn)而繼續(xù)用該知識(shí)建立免疫策略，為控制病毒傳播做貢獻(xiàn)就顯得非常有價(jià)值.

下文在敘述復(fù)雜網(wǎng)絡(luò)病毒模型的種類和復(fù)雜網(wǎng)絡(luò)中比較經(jīng)典的傳統(tǒng)免疫策略后，提出改進(jìn)的三階雙免疫思想，并重點(diǎn)論述依據(jù)該算法思想進(jìn)行的仿真實(shí)驗(yàn)及其與經(jīng)典的熟人免疫[2]、雙免疫[3]、二階雙免疫策略[4]進(jìn)行免疫效果的對(duì)比分析.

1 復(fù)雜網(wǎng)絡(luò)上的病毒傳播模型

經(jīng)典的病毒傳播模型中個(gè)體狀態(tài)通常有：S(susceptible)——易染狀態(tài)(通常稱為健康狀態(tài))[5]；I(infected)——感染狀態(tài)；R(removed)——免疫狀態(tài)(也稱作被移除狀態(tài))[2].依據(jù)種群個(gè)體感染病毒后的情況，經(jīng)典病毒傳播模型有SI模型、SIS模型、SIR模型、SIRS模型、SEIR模型[6,7].

1.1 SI模型

定義t時(shí)刻網(wǎng)絡(luò)節(jié)點(diǎn)中易被感染節(jié)點(diǎn)數(shù)為S(t)，感染節(jié)點(diǎn)數(shù)為I(t)，網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)用N表示，定義單位時(shí)間節(jié)點(diǎn)從易染狀態(tài)染上病毒處在感染狀態(tài)的幾率為α，則描述SI模型的微分方程為[6,7,8]：

1.2 SIS模型

1.3 SIR模型

1.4 SIRS模型[6,7]

1.5 SEIR模型[6,7]

2 復(fù)雜網(wǎng)絡(luò)經(jīng)典免疫策略

無標(biāo)度網(wǎng)絡(luò)特性——度數(shù)小的節(jié)點(diǎn)約占整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的78%,大于等于4度的節(jié)點(diǎn)約占22%[10].現(xiàn)實(shí)中許多網(wǎng)絡(luò)都遵循此特性，從此特性不難得出與小度節(jié)點(diǎn)相比大度節(jié)點(diǎn)感染后，更能造成大范圍的傳播，基于此特性的網(wǎng)絡(luò)的經(jīng)典免疫策略主要有：隨機(jī)免疫、目標(biāo)免疫、熟人免疫等[2].

2.1 隨機(jī)免疫

隨機(jī)免疫是最簡(jiǎn)單的免疫策略，該技術(shù)是任意抽得一些節(jié)點(diǎn)進(jìn)行免疫，又稱為均勻免疫，意思為所有節(jié)點(diǎn)被選取進(jìn)行免疫的幾率相同，由此也可想而知,此免疫效率不高，若想徹底使全部節(jié)點(diǎn)處在移除免疫狀態(tài)，則必須把此策略實(shí)施到全部節(jié)點(diǎn).

2.2 目標(biāo)免疫

目標(biāo)免疫[11]采取抓大策略，即對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)度數(shù)排序，選取最大度節(jié)點(diǎn)實(shí)施免疫策略.但現(xiàn)實(shí)中的網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目巨多，網(wǎng)絡(luò)連接關(guān)系實(shí)時(shí)動(dòng)態(tài)變化，因此可以說這種策略屬于理想化方法，實(shí)現(xiàn)的可能性較小.

2.3 熟人免疫

熟人免疫策略[12]其免疫效果優(yōu)于隨機(jī)免疫，該方法主要指先按照一定百分比任意選取節(jié)點(diǎn)，然后對(duì)這些節(jié)點(diǎn)的任意鄰居實(shí)施免疫策略.此種免疫策略不必獲取該網(wǎng)絡(luò)所有節(jié)點(diǎn)度的全局概況，彌補(bǔ)了目標(biāo)免疫的缺點(diǎn).

此外，還有雙免疫策略[3]：按照一定百分比隨機(jī)選取節(jié)點(diǎn)，對(duì)被選節(jié)點(diǎn)本身及其最大度[8]鄰居進(jìn)行免疫的技術(shù).

二階雙免疫策略是對(duì)任意抽得節(jié)點(diǎn)的度最大的節(jié)點(diǎn)和二階鄰居節(jié)點(diǎn)實(shí)施免疫的策略[4]，由于選取的最大度節(jié)點(diǎn)數(shù)目增多，涉及相連的鄰居節(jié)點(diǎn)數(shù)目增多，所以免疫效果要優(yōu)于雙免疫策略.

3 三階免疫算法的提出

三階免疫算法思想是在研究無標(biāo)度網(wǎng)絡(luò)特性和二階雙免疫策略思想基礎(chǔ)上提出的.該算法的思想為：從節(jié)點(diǎn)總數(shù)為N的無標(biāo)度網(wǎng)絡(luò)模型中，按照百分比d任意抽得一些實(shí)驗(yàn)節(jié)點(diǎn)并求出度，得到最大節(jié)點(diǎn)的一階鄰居最大度節(jié)點(diǎn)、二階鄰居最大度節(jié)點(diǎn)和三階鄰居最大度節(jié)點(diǎn)，同時(shí)對(duì)這些實(shí)驗(yàn)中的最大度節(jié)點(diǎn)和三階鄰居最大度節(jié)點(diǎn)進(jìn)行免疫.

選擇這樣的矩陣表示節(jié)點(diǎn)是否有鏈接的數(shù)組，該矩陣主對(duì)角線數(shù)字代表節(jié)點(diǎn)度數(shù)，其他位置數(shù)字含義為：若兩節(jié)點(diǎn)ai、aj有鏈接關(guān)系,則aij=aji=1，否則aij=aji=0[4].三階免疫策略實(shí)施過程為：

1) 構(gòu)建無標(biāo)度網(wǎng)絡(luò)模型，設(shè)定網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)N為1 000.

2) 按照任意設(shè)定的百分比d，以任意抽得的n=Nd個(gè)節(jié)點(diǎn)作為數(shù)組元素.

3) 進(jìn)行三階免疫技術(shù)方法的仿真實(shí)驗(yàn)：①根據(jù)對(duì)角線數(shù)字找出n個(gè)節(jié)點(diǎn)中度最大的節(jié)點(diǎn)，及其一階、二階、三階最大鄰居節(jié)點(diǎn)，把該最大度節(jié)點(diǎn)及其一階、二階、三階最大鄰居節(jié)點(diǎn)所在矩陣中的行和列非零元素全部設(shè)置為零，設(shè)置后得到新的數(shù)組.②重復(fù)上述過程直到數(shù)組中所有元素都實(shí)施了三階免疫策略.

4) 構(gòu)建新的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).

4 仿真實(shí)驗(yàn)與對(duì)比分析

仿真實(shí)驗(yàn)流程圖為：

圖1 仿真實(shí)驗(yàn)流程圖

圖2 起始節(jié)點(diǎn)為最大度、平均度、最小度時(shí)感染程度 圖3 起始節(jié)點(diǎn)三種不同度在第五個(gè)時(shí)間步實(shí)施三階雙免疫效果

4.1 三階雙免疫策略在初始感染節(jié)點(diǎn)為最大度、平均度、最小度的免疫比較

在依據(jù)無標(biāo)度網(wǎng)絡(luò)特性生成的網(wǎng)路模型中，設(shè)定0.4為傳播率[3]，從病毒傳播時(shí)刻開始計(jì)時(shí)，初始感染節(jié)點(diǎn)為最大度、平均度、最小度時(shí)感染程度如圖2所示，圖中橫軸為時(shí)間步，縱軸為感染節(jié)點(diǎn)數(shù).從圖中不難看出，度最大的節(jié)點(diǎn)染上病毒并傳播的速度比度最小的節(jié)點(diǎn)、臨近平均度的節(jié)點(diǎn)傳播的都快.

在病毒傳播的第五個(gè)時(shí)間步實(shí)施三階雙免疫策略，效果如圖3所示.從圖3中可以看出，三種不同度節(jié)點(diǎn)實(shí)施三階免疫策略達(dá)到穩(wěn)定狀態(tài)的時(shí)間幾乎一致.

4.2 三階雙免疫策略與熟人免疫策略、雙免疫策略、二階雙免疫策略的效果比較

此次仿真實(shí)驗(yàn)傳播率和無標(biāo)度網(wǎng)路同上，在病毒傳播達(dá)到平衡狀態(tài)時(shí)分別采用免疫策略得出效果如圖4所示，橫軸為十個(gè)時(shí)間步，縱軸為前文提到的感染節(jié)點(diǎn)數(shù)，從圖4容易看出，三階免疫策略優(yōu)于熟人免疫和雙免疫策略.

圖4 三階免疫策略與二階雙免疫、雙免疫、熟人免疫策略的效果比較

5 結(jié)論

無標(biāo)度網(wǎng)絡(luò)特性是非均勻網(wǎng)絡(luò)，許多網(wǎng)絡(luò)具有這個(gè)性質(zhì)，它們的度分布均符合冪律分布.此研究已經(jīng)表明無標(biāo)度網(wǎng)絡(luò)抗病能力差.本文提出的三階免疫策略綜合了經(jīng)典的熟人免疫和雙免疫[3]的優(yōu)點(diǎn)，它是對(duì)網(wǎng)絡(luò)中任意抽得的節(jié)點(diǎn)中最大度節(jié)點(diǎn)及其三階鄰居節(jié)點(diǎn)一起實(shí)施免疫策略，是對(duì)二階雙免疫策略[4]的進(jìn)一步改進(jìn).研究表明,本文提出的免疫策略優(yōu)于熟人免疫、二階雙免疫，理論上對(duì)控制病毒傳播具有有效的指導(dǎo)作用，也對(duì)此類研究具有一定的參考價(jià)值.

[1] 陳端兵，黃晟，尚明生.復(fù)雜網(wǎng)絡(luò)模型及其在疫情傳播和控制中的應(yīng)用研究[J].計(jì)算機(jī)科學(xué)，2011，38(6)：118-121.

[2] 汪小帆，李翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京：清華大學(xué)出版社，2006.

[3] 江靜，陳新一.復(fù)雜網(wǎng)絡(luò)上的免疫策略的研究[J].西北民族大學(xué)學(xué)報(bào)，2013，34(4)：30-34.

[4] 劉運(yùn)節(jié)，牟安，陳新一.復(fù)雜網(wǎng)絡(luò)上免疫技術(shù)的研究[J].網(wǎng)絡(luò)天地，2014，17.

[5] 孫婷婷. 復(fù)雜網(wǎng)絡(luò)的病毒傳播模型及其免疫策略研究[D].安徽大學(xué)，2013.

[6] 何大韌，劉宗華，汪秉宏.復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)[M]. 北京：高等教育出版社，2009.

[7] 金偉新. 體系對(duì)抗復(fù)雜網(wǎng)絡(luò)建模與仿真[M].北京：電子工業(yè)出版社，2010.

[8] 江靜. 基于藏文Web的網(wǎng)路模型與免疫策略研究[D]. 西北民族大學(xué)，2014.

[9] 徐國(guó)鋒，劉家保，陸一南，陳中華.復(fù)雜網(wǎng)絡(luò)上的病毒免疫策略研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012,42(16)：127-131.

[10] Zhou S,Mondragon R J.Accurately modeling the Internet topology[J].Phys.Rev.E,2004,70:066108.

[11] Pastor-Satorras R，Vespignani A． Immunization of complex networks[J].Phys． Rev． E，2001，65: 036134．

[12] Cohen R，Havlin S，Ben-Avraham D． Efficient immunization strategies for computer networks and populations[J].Phys．Rev．Lett．，2003，91: 247901．

2015-05-20

西北民族大學(xué)研究生實(shí)踐創(chuàng)新項(xiàng)目(Yxm2014041).

關(guān)風(fēng)嬌(1988——)，女，山東濟(jì)寧人，碩士研究生，主要從事復(fù)雜網(wǎng)絡(luò)方面的研究.

TP393.08；O157

A

1009-2102(2015)02-0036-04