加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)病毒傳播和局部免疫策略研究①

劉瑞軍

(武夷學(xué)院 實(shí)驗(yàn)室管理中心, 武夷山 354300)

加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)病毒傳播和局部免疫策略研究①

劉瑞軍

(武夷學(xué)院 實(shí)驗(yàn)室管理中心, 武夷山 354300)

為了進(jìn)一步描述現(xiàn)實(shí)生活中復(fù)雜網(wǎng)絡(luò)的病毒傳播問(wèn)題, 改進(jìn)加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型的傳統(tǒng)構(gòu)造方法, 考慮流量帶寬和個(gè)體抵抗力兩個(gè)重要因子, 利用平均場(chǎng)理論模擬仿真病毒傳播過(guò)程, 對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析, 驗(yàn)證該模型的有效性. 現(xiàn)實(shí)生活中往往只能了解復(fù)雜網(wǎng)絡(luò)的局部拓?fù)湫畔?，傳統(tǒng)病毒免疫策略大多基于全局拓?fù)湫畔? 在僅了解局部信息的前提下, 提出加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)中基于局部最優(yōu)的病毒免疫策略, 通過(guò)動(dòng)態(tài)模擬病毒傳播的免疫仿真實(shí)驗(yàn), 與隨機(jī)免疫策略和目標(biāo)免疫策略對(duì)病毒傳播影響進(jìn)行比較, 驗(yàn)證局部最優(yōu)免疫策略的有效性.

加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò); 病毒傳播; 流量帶寬; 個(gè)體抵抗力; 局部最優(yōu)

1 引言

近年來(lái), 隨著互聯(lián)網(wǎng)的日益普及, 改善了人們的生活環(huán)境, 同時(shí)也為計(jì)算機(jī)病毒的生存和發(fā)展提供了有利條件. 在社會(huì)高速發(fā)展過(guò)程中, 人類(lèi)曾多次遭遇毀滅性的計(jì)算機(jī)病毒攻擊, 造成嚴(yán)重的經(jīng)濟(jì)損失. 同時(shí), 計(jì)算機(jī)病毒安全問(wèn)題甚至關(guān)系到一個(gè)國(guó)家的安定穩(wěn)定,一種微不足道的新型病毒很可能使整個(gè)國(guó)家甚至大半個(gè)世界的網(wǎng)絡(luò)陷入癱瘓, 不但給生活帶來(lái)不便, 甚至給國(guó)防帶來(lái)危機(jī). 為了讓人類(lèi)生活在安全的互聯(lián)網(wǎng)環(huán)境中, 從計(jì)算機(jī)病毒第一次出現(xiàn)后, 許多科學(xué)家就開(kāi)始模擬病毒傳播, 希望能預(yù)測(cè)計(jì)算機(jī)病毒的傳播過(guò)程并有效的遏制病毒的泛濫.

1999年Faloutsos等人[1]發(fā)現(xiàn), 互聯(lián)網(wǎng)表現(xiàn)出很強(qiáng)的冪律分布特點(diǎn), 節(jié)點(diǎn)的度有很大的波動(dòng)性[1,2]. 目前為止主要從兩種不同的角度來(lái)描繪互聯(lián)網(wǎng)的結(jié)構(gòu)[1,3]. 盡管隨著時(shí)間的推移, 系統(tǒng)中的節(jié)點(diǎn)和邊在不斷增加, 但網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特性卻不會(huì)發(fā)生很大的變化[4]. 大量研究表明網(wǎng)絡(luò)上的病毒傳播與網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)有著密切的聯(lián)系[5-8], 在BA無(wú)標(biāo)度網(wǎng)絡(luò)中, 當(dāng)節(jié)點(diǎn)數(shù)近似無(wú)窮時(shí), 病毒的有效傳播率閾值近似于0. 1998年, Steve White提出了五個(gè)關(guān)于計(jì)算機(jī)病毒研究問(wèn)題[9], 其中最具爭(zhēng)議性的問(wèn)題是理論上的計(jì)算機(jī)病毒傳播速率遠(yuǎn)超于現(xiàn)實(shí). 現(xiàn)實(shí)中感染30萬(wàn)臺(tái)主機(jī)需24小時(shí)左右[10], 然后理論上計(jì)算機(jī)病毒感染100萬(wàn)臺(tái)主機(jī)所需時(shí)間還不到1秒[11].

針對(duì)互聯(lián)網(wǎng)上病毒傳播速度現(xiàn)實(shí)與理論的巨大差異以及現(xiàn)實(shí)互聯(lián)網(wǎng)絡(luò)的增長(zhǎng)模式, 本文建立了引入邊權(quán)值表示流量帶寬節(jié)點(diǎn)值表示個(gè)體抵抗力的改進(jìn)加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型. 根據(jù)模型, 分別觀察了初始感染節(jié)點(diǎn)的選擇、個(gè)體抵抗力差異、流量帶寬限制等對(duì)病毒傳播的影響. 以往的病毒免疫策略[12]研究, 大多基于對(duì)網(wǎng)絡(luò)全局拓?fù)湫畔⒍龀龅? 現(xiàn)實(shí)生活中, 大部分復(fù)雜網(wǎng)絡(luò)[13]僅僅局限于了解其局部拓?fù)湫畔? 針對(duì)現(xiàn)實(shí)情況,本文提出了加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)中基于局部最優(yōu)信息的病毒免疫策略, 通過(guò)與隨機(jī)免疫策略和目標(biāo)免疫策略的比較, 觀察其是否有效.

2 模型及理論分析

2.1 加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型

傳統(tǒng)加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型中, 邊權(quán)值wi,j通常表示節(jié)點(diǎn)i, j間的熟悉程度,, 病毒的有效傳播率正 比于越大, 表示i, j節(jié)點(diǎn)之間越熟悉, 相似度越大, 當(dāng)其中一個(gè)節(jié)點(diǎn)感染病毒時(shí), 另一個(gè)節(jié)點(diǎn)感染病毒的概率也越大; 反之, 表示i, j節(jié)點(diǎn)之間越陌生, 相似度越小, 當(dāng)其中一個(gè)節(jié)點(diǎn)感染病毒時(shí), 另一個(gè)節(jié)點(diǎn)感染病毒的概率也越小.

模型的構(gòu)造算法[5]如下:

Step1. 增長(zhǎng): 從一個(gè)具有m0個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)開(kāi)始, m0個(gè)節(jié)點(diǎn)相互連接, 每次引入一個(gè)新的節(jié)點(diǎn)i, 并且分別連到m個(gè)已存在的節(jié)點(diǎn)上, 假設(shè)與節(jié)點(diǎn)j相連, 則i, j之間的邊權(quán)值為, 這里

Step2. 優(yōu)先連接: 一個(gè)新的節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連接的概率與節(jié)點(diǎn)i的度, 節(jié)點(diǎn)j的度之間滿足公式(1)關(guān)系:

經(jīng)過(guò)理論和實(shí)驗(yàn)證明, 無(wú)標(biāo)度網(wǎng)絡(luò)的度分布滿足冪律關(guān)系, 度分布函數(shù)[5], 其中k為節(jié)點(diǎn)的度,r通常取2～3[14]之間的值.

2.2 改進(jìn)后的加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型

問(wèn)題1. 計(jì)算機(jī)病毒在互聯(lián)網(wǎng)上的傳播速率遠(yuǎn)低于理論值, 現(xiàn)實(shí)考慮病毒傳播速率緩慢的原因?yàn)椴《靖叻迤跁r(shí)由于傳輸路徑本身容量的限制而發(fā)生擁塞現(xiàn)象和個(gè)體本身的不同防護(hù)措施使其不容易被病毒感染,某些節(jié)點(diǎn)如果度相對(duì)較大, 說(shuō)明比較重要, 它就會(huì)相對(duì)與其他節(jié)點(diǎn)具有更強(qiáng)的病毒抵御能力, 而且通過(guò)它的傳輸路徑容量也相對(duì)較大. 為此引入了流量帶寬和個(gè)體抵抗力因子. 其中, 用節(jié)點(diǎn)本身的權(quán)值vi表示每個(gè)不同個(gè)體之間擁有的不同抵抗力, vi越大, 個(gè)體抵抗力越強(qiáng), 被病毒感染的幾率越低; 用節(jié)點(diǎn)之間的邊權(quán)值wi,j表示節(jié)點(diǎn)i, j之間的流量帶寬,越大, 表示該條路徑的容量越大, 發(fā)生擁塞的可能性越低, 病毒在該條路徑上傳播得越順暢, 個(gè)體抵抗力在這條路徑上發(fā)揮的作用相對(duì)就比較微弱. 反之, 病毒在該路徑上的傳播速度將受到相應(yīng)的抑制.

問(wèn)題2. 傳統(tǒng)加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型構(gòu)造方法存在以下弊端: Step1中網(wǎng)絡(luò)每增加一個(gè)節(jié)點(diǎn), 均產(chǎn)生m條邊,節(jié)點(diǎn)和邊的增長(zhǎng)都很規(guī)律, 但現(xiàn)實(shí)互聯(lián)網(wǎng)節(jié)點(diǎn)與邊的增長(zhǎng)并不是特別規(guī)律.

根據(jù)問(wèn)題1和問(wèn)題2, 本文對(duì)傳統(tǒng)加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造方法進(jìn)行改進(jìn), 具體構(gòu)造算法如下:

Step1. 增長(zhǎng): 從一個(gè)只有1個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)開(kāi)始, 該節(jié)點(diǎn)擁有抵抗力值v1, 每次引入一個(gè)新的節(jié)點(diǎn)j, 并且按概率pi分別與所有存在的節(jié)點(diǎn)相連, 假設(shè)與節(jié)點(diǎn)i相連, 則i, j之間的邊權(quán)值為wi,j, 抵抗力vi的值更新為v’i, 如公式(2):

θ是增量因子, 根據(jù)節(jié)點(diǎn)i當(dāng)前度的大小ki進(jìn)行調(diào)節(jié).表示節(jié)點(diǎn)i的當(dāng)前總帶寬流量wi, 由公式(3)可知抵抗力增量與節(jié)點(diǎn)自身抵抗力呈負(fù)相關(guān), 與節(jié)點(diǎn)帶寬總流量呈正相關(guān), 重要的節(jié)點(diǎn)抵抗力增加的速度高于一般節(jié)點(diǎn), 特別是相對(duì)重要的節(jié)點(diǎn)本身抵抗力較弱時(shí), 人們就會(huì)對(duì)其重點(diǎn)保護(hù), 大幅度提高其抵抗能力, 這與現(xiàn)實(shí)中的問(wèn)題1相符.

Step2. 優(yōu)先連接: 一個(gè)新的節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連接的概率pi與節(jié)點(diǎn)i的邊權(quán)和wi, 節(jié)點(diǎn)j的邊權(quán)和wj之間的關(guān)系如公式(4):

新增的節(jié)點(diǎn)偏向與網(wǎng)絡(luò)中的重要節(jié)點(diǎn)相連, 但也存在與微弱節(jié)點(diǎn)相連的可能.

Step3. 若新增加的節(jié)點(diǎn)經(jīng)過(guò)Step1和Step2后仍是個(gè)孤立點(diǎn), 則使其與網(wǎng)絡(luò)中相對(duì)序號(hào)最小的度最大節(jié)點(diǎn)相連.

按上述算法構(gòu)造出節(jié)點(diǎn)數(shù)目為5000個(gè)的改進(jìn)后加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型(具體參數(shù)設(shè)置請(qǐng)參見(jiàn)第五章節(jié)實(shí)驗(yàn)結(jié)果與分析), 其度分布如圖2, 排除干擾點(diǎn), 取其中的七組坐標(biāo)數(shù)據(jù)進(jìn)行計(jì)算, 坐標(biāo)數(shù)據(jù)如表1, 計(jì)算結(jié)果的r值約為0.73, 即, 雖然與經(jīng)典的r值在2～3之間有一定差距, 但由度分布圖可知改進(jìn)的構(gòu)造方式符合無(wú)標(biāo)度網(wǎng)絡(luò)選擇增長(zhǎng)和優(yōu)先連接的特性, 具有現(xiàn)實(shí)網(wǎng)絡(luò)可參照性.

表1 度分布測(cè)試數(shù)據(jù)

3 動(dòng)態(tài)模擬病毒傳播過(guò)程

通過(guò)研究無(wú)標(biāo)度網(wǎng)絡(luò)上的SIS[15]和SIR[16]病毒傳播過(guò)程, 本文結(jié)合當(dāng)前建立的改進(jìn)后加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)模型, 分析病毒在該模型上的SIS(R)傳播過(guò)程, 過(guò)程如圖1所示.

圖1 SIS(R)傳播模型

個(gè)體被劃分為三種不同的類(lèi)型: 易感種群類(lèi)(S), 他們不會(huì)感染其他個(gè)體, 但有可能被其他感染個(gè)體感染;感染種群類(lèi)(I), 他們已經(jīng)被感染, 而且會(huì)感染易感個(gè)體,具有傳染性; 免疫種群類(lèi)(R), 他們是經(jīng)過(guò)人為免疫策略而使其達(dá)到免疫狀態(tài), 不會(huì)感染其他個(gè)體, 也不會(huì)被其他個(gè)體感染. 在圖2中, 若易感節(jié)點(diǎn)與感染節(jié)點(diǎn)接觸,它就有α概率的可能變成感狀節(jié)點(diǎn); 感染節(jié)點(diǎn)本身有β概率的可能恢復(fù)到易感節(jié)點(diǎn)狀態(tài). 無(wú)論是易感還是感染節(jié)點(diǎn), 經(jīng)過(guò)人為干預(yù), 都有π概率的可能變成免疫節(jié)點(diǎn). 研究中, 我們定義:

自我恢復(fù)率β與個(gè)體抵抗力vi相關(guān), 如果被感染節(jié)點(diǎn)的個(gè)體抵抗力越強(qiáng), 其恢復(fù)成易感節(jié)點(diǎn)的概率越高;被感染率α與該節(jié)點(diǎn)的邊權(quán)總和以及個(gè)體抵抗力相關(guān),如果易感節(jié)點(diǎn)邊權(quán)和很大, 且其抵抗力相對(duì)較弱, 則其極易受感染; 免疫率非0即1, 如果對(duì)某點(diǎn)采取免疫措施,則其變?yōu)槊庖郀顟B(tài), 如果未采取任何免疫策略, 則其為原易感或感染狀態(tài). 若不存在人為的免疫策略, 則SIS(R)模型退化為SIS模型.

利用平均場(chǎng)理論, 假設(shè)網(wǎng)絡(luò)中度值為k的節(jié)點(diǎn)中易感個(gè)體比例為, 感染個(gè)體比例為ρk(t), 免疫個(gè)體比例為, 其中Sk(t)+ρk(t)+Rk(t)=1, k=1, 2, ……, n. 建立公式(7)病毒傳播動(dòng)力學(xué)方程如下:

其中, n為節(jié)點(diǎn)的最大度值, P(k)表示度值為k的節(jié)點(diǎn)占所有節(jié)點(diǎn)的比例;

通過(guò)理論推導(dǎo)的公式(13)可知, 在無(wú)免疫策略前提下, 加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)的病毒傳播的最終感染率與個(gè)體抵抗能力、度分布和邊權(quán)帶寬值之間密切相關(guān).

4 病毒控制策略

4.1 傳統(tǒng)病毒控制策略

抑制病毒傳播的一種重要方法是人為干預(yù), 引入免疫策略. 目前, 主要的免疫方法有隨機(jī)免疫策略、目標(biāo)免疫策略和熟人免疫策略[17]. 本文僅討論隨機(jī)免疫和目標(biāo)免疫策略.

隨機(jī)免疫策略通過(guò)隨機(jī)的方式選取若干個(gè)節(jié)點(diǎn)進(jìn)行免疫, 不考慮節(jié)點(diǎn)中的個(gè)體差異, 每個(gè)節(jié)點(diǎn)被選到的概率都相等, 實(shí)驗(yàn)表明, 隨機(jī)免疫雖然能局部抑制病毒的傳播, 但對(duì)于要徹底消滅病毒, 需對(duì)網(wǎng)絡(luò)中的絕大多數(shù)節(jié)點(diǎn)進(jìn)行免疫, 這顯然不現(xiàn)實(shí). 目標(biāo)免疫策略?xún)?yōu)先選取網(wǎng)絡(luò)中重要的節(jié)點(diǎn)進(jìn)行免疫, 考慮節(jié)點(diǎn)間的差異, 越重要但本身越脆弱的節(jié)點(diǎn)首先被考慮進(jìn)行免疫, 實(shí)驗(yàn)表明, 僅對(duì)少量節(jié)點(diǎn)進(jìn)行免疫就可以達(dá)到徹底消滅病毒的目的.

4.2 基于局部最優(yōu)病毒控制策略

傳統(tǒng)的隨機(jī)免疫和目標(biāo)免疫均為基于網(wǎng)絡(luò)全局拓?fù)湫畔⒌拿庖卟呗? 然后現(xiàn)實(shí)生活中對(duì)一個(gè)網(wǎng)絡(luò)全局信息的掌握十分有限, 特別是對(duì)一些龐大的復(fù)雜網(wǎng)絡(luò).傳統(tǒng)的免疫實(shí)驗(yàn)大多預(yù)先對(duì)需要免疫的節(jié)點(diǎn)進(jìn)行免疫,然后再觀察病毒的傳播現(xiàn)象, 與現(xiàn)實(shí)生活中的實(shí)時(shí)免疫相悖. 因此, 針對(duì)上述問(wèn)題, 本文提出了基于局部最優(yōu)信息的動(dòng)態(tài)免疫策略. 出于現(xiàn)實(shí)考慮, 假設(shè)(1): 每次動(dòng)態(tài)地選擇N個(gè)點(diǎn)進(jìn)行免疫, 而不是一次性把該免疫的節(jié)點(diǎn)全部免疫了. 假設(shè)(2): 由于發(fā)現(xiàn)病毒的滯后性, 當(dāng)采取免疫措施時(shí)病毒已達(dá)到感染峰值. 假設(shè)(3): 由于不能全局性的發(fā)現(xiàn)病毒存在, 實(shí)驗(yàn)中每個(gè)階段僅知道部分節(jié)點(diǎn)感染病毒, 即病毒獲知率S為0～1之間的數(shù)值.該免疫策略關(guān)鍵步驟如下:

Step1. 對(duì)所獲知的被感染節(jié)點(diǎn)i, 計(jì)算與i相距l(xiāng)en(直接相連距離為1)距離以?xún)?nèi)所有臨近節(jié)點(diǎn)各自的容量和wx, x表示網(wǎng)路中以i節(jié)點(diǎn)為中心, 以len為半徑的所有節(jié)點(diǎn)集, 表示與i節(jié)點(diǎn)臨近的節(jié)點(diǎn)集各自的容量和.

Step2. 對(duì)wx中所有節(jié)點(diǎn)的容量和進(jìn)行從大到小排序, 選擇前N個(gè)節(jié)點(diǎn)進(jìn)行免疫. 若n(Wx)

Step3. 若n(Wx)=0, 結(jié)束計(jì)算, 否則轉(zhuǎn)Step1.

5 實(shí)驗(yàn)結(jié)果與分析

仿真實(shí)驗(yàn)過(guò)程, 改進(jìn)后加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)的節(jié)點(diǎn)規(guī)模為5000個(gè), 通常情況下足以體現(xiàn)現(xiàn)實(shí)復(fù)雜網(wǎng)絡(luò)模型的主要病毒傳播特征. 個(gè)體抵抗力vi取0.01～0.05之間的數(shù)值, 節(jié)點(diǎn)間的流量帶寬取0.1～0.3之間的數(shù)值,基于局部最優(yōu)免疫策略算法過(guò)程中感染病毒節(jié)點(diǎn)的獲知率S設(shè)置為0.1～0.5之間以及距離len值取1～5之間的整數(shù), 初始感染率統(tǒng)一取值為0.1, 即隨機(jī)選取網(wǎng)絡(luò)中十分之一的節(jié)點(diǎn)為被感染節(jié)點(diǎn), 其他均為易感節(jié)點(diǎn).按改進(jìn)后的加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)構(gòu)造算法構(gòu)造出網(wǎng)絡(luò)模型的度分布如圖2所示, 具體數(shù)據(jù)分析見(jiàn)表1.

圖2 改進(jìn)后加權(quán)無(wú)標(biāo)度模型的度分布

5.1 流量帶寬大小對(duì)病毒傳播的影響

現(xiàn)實(shí)的病毒傳播速度與理論存在巨大差異, 為驗(yàn)證所述流量帶寬是否為影響病毒傳播的因素之一, 本文對(duì)在僅流量帶寬變化的情況下對(duì)病毒傳播行為進(jìn)行仿真實(shí)驗(yàn). 仿真中, vi取0.02～0.03之間數(shù)值,分別取表2中的四組測(cè)試數(shù)據(jù).

表2 流量帶寬測(cè)試數(shù)據(jù)

四組數(shù)據(jù)的流量帶寬逐漸增加, 仿真結(jié)果如圖3所示.

由圖3可知, 無(wú)標(biāo)度網(wǎng)絡(luò)中隨著整體流量帶寬大小的增大, 病毒傳播速度和最終病毒感染率都隨之增加.當(dāng)流量帶寬均值在0.2以上時(shí), 病毒傳播行為基本不受太大影響, 只是在小范圍內(nèi)波動(dòng). 由此得知, 流量在一定閾值范圍內(nèi)可以抑制病毒傳播行為, 同時(shí)也驗(yàn)證了實(shí)際生活中病毒大量爆發(fā)時(shí)由于帶寬的限制而相互制約, 從而導(dǎo)致傳播速度小于理論值.

5.2 個(gè)體抵抗力強(qiáng)弱對(duì)病毒傳播的影響

每個(gè)個(gè)體對(duì)同一種病毒的抵抗力不盡相同, 當(dāng)一個(gè)個(gè)體的抵抗力強(qiáng)度較大時(shí), 不僅能較快地從感染狀態(tài)恢復(fù)到易感狀態(tài), 而且能在一定程度上遏制病毒對(duì)自身的感染. 為了進(jìn)一步了解加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)上個(gè)體抵抗力強(qiáng)弱對(duì)病毒傳播的影響, 仿真中取0.1～0.2之間數(shù)值, vi分別取值0.01～0.02、0.02～0.03、0.03～0.04和0.04～0.05四組數(shù)據(jù)進(jìn)行測(cè)試, 仿真結(jié)果如圖4所示.

圖3 流量帶寬大小差異

圖4 個(gè)體抵抗力強(qiáng)弱差異

從圖4可以看出, 加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)中, 節(jié)點(diǎn)抵抗力強(qiáng)弱差異對(duì)病毒傳播速度的影響較小, 對(duì)病毒峰值的影響較大, 當(dāng)初始個(gè)體抵抗力強(qiáng)度達(dá)到0.05左右時(shí), 由于抵抗力隨時(shí)間不斷增大, 最終將影響最終的病毒感染比例. 個(gè)體抵抗力強(qiáng)弱將最終印象病毒的感染比例.

5.3 基于局部最優(yōu)免疫策略對(duì)病毒傳播的影響

為了驗(yàn)證加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)上基于局部最優(yōu)病毒傳播免疫策略的有效性, 對(duì)病毒傳播采取了免疫措施. 仿真中取0.1～0.2之間數(shù)值, vi取0.02～0.04之間數(shù)值,S =0.15且len分別取2, 3, 5, 觀察len在不同取值時(shí)對(duì)局部最優(yōu)免疫效果的影響, 并與隨機(jī)免疫、目標(biāo)免疫進(jìn)行了比較, 效果如圖5所示.

圖5 加權(quán)無(wú)標(biāo)度局部最優(yōu)免疫效果

由圖5可以看出局部最優(yōu)免疫策略相對(duì)于目標(biāo)免疫策略和隨機(jī)免疫策略來(lái)說(shuō)都是一種有效的免疫方法,雖然局部最優(yōu)免疫策略的效果不如目標(biāo)免疫策略, 但隨著len的增大, 局部最優(yōu)免疫策略的效果將接近目標(biāo)免疫, 當(dāng)len取值為5時(shí), 最優(yōu)免疫策略的效果已經(jīng)非常接近目標(biāo)免疫了. 現(xiàn)實(shí)世界中, 很難了解網(wǎng)絡(luò)的全局信息, 所以局部最優(yōu)免疫策略具有現(xiàn)實(shí)意義.

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

計(jì)算機(jī)病毒的日益泛濫嚴(yán)重威脅著網(wǎng)絡(luò)安全, 了解病毒在復(fù)雜網(wǎng)絡(luò)上的傳播行為及其性質(zhì)對(duì)我們采取免疫措施至關(guān)重要. 不同的網(wǎng)絡(luò)采取的免疫措施不同,同一種網(wǎng)絡(luò)采取不同的免疫措施效果也不同. 經(jīng)過(guò)仿真研究, 驗(yàn)證了加權(quán)無(wú)標(biāo)度中基于最優(yōu)免疫策略對(duì)病毒傳播抑制的有效性, 特別是在僅僅了解局部信息的前提下, 大大提高了性?xún)r(jià)比. 在現(xiàn)實(shí)工作中, 我們可結(jié)合局部最優(yōu)免疫策略對(duì)病毒采取免疫措施, 從而提高網(wǎng)絡(luò)系統(tǒng)的可靠和安全性.

本文的研究中, 僅考慮只有一種病毒存在的傳播模型及免疫策略, 然而現(xiàn)實(shí)生活中計(jì)算機(jī)往往同時(shí)存在多種病毒. 不同病毒之間在復(fù)雜網(wǎng)絡(luò)上的相互競(jìng)爭(zhēng)與合作關(guān)系值得我們進(jìn)一步深究.

1Faloutsos M, Faloutsos P, Faloutsos C. On power-law relationships of the Internet topology. ACM SIGCOMM Computer Communication Review, 1999, 29(4): 251–262.[doi: 10.1145/316194]

2Vazquez A, Pastor-Satorras R, Vespignani A. Large-scale topological and dynamical properties of Internet. http://arxiv.org/abs/cond-mat/0112400.

3Chen GR, Fan ZP, Li X. Modelling the complex Internet topology. Complex Dynamics in Communication Networks.Berlin, Springer-Verlag. 2005. 213–234.

4李濤, 關(guān)治洪, 吳正平. 病毒在無(wú)標(biāo)度網(wǎng)絡(luò)上的傳播及控制仿真研究. 計(jì)算機(jī)應(yīng)用研究, 2007, 24(12): 177–178. [doi:10.3969/j.issn.1001-3695.2007.12.056]

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

6WANG CX, Knight JC, Elder MC. On computer viral infection and the effect of immunization. IEEE 16th Annual Conference Computer Security Applications. New Orleans,USA. 2000. 246–256.

7Vázquez A, Pastor-Satorras R, Vespignani A. Large-scale topological and dynamical properties of the Internet. Physical Review E, 2002, (65): 066130. [doi: 10.1103/PhysRevE.65.066130]

8Li X, Chen GR, Li CG. Stability and bifurcation of disease spreading in complex networks. International Journal of Systems Science, 2004, 35(9): 527–536. [doi: 10.1080/00207720412331285869]

9White SR. Open problems in computer virus research. Proc.of Virus Bulletin Conference. Munich, Germany. 1998.

10Moore D. The spread of the code-red worm. http://www.caida.org/research/security/code-red/coderedv2_analysis.xml.

11Staniford S, Moore D, Paxson V, et al. The top speed of flash worms. Proc. of the 2004 ACM workshop on Rapid malcode.Washington DC, USA. 2004. 33–42.

12朱剛, 張寧, 馬良. 復(fù)雜網(wǎng)絡(luò)上計(jì)算機(jī)病毒傳播和控制策略研究. 計(jì)算機(jī)應(yīng)用研究, 2006, 23(9): 54–56.

13黃金源, 張寧, 肖仰華. 基于拷貝模型的復(fù)雜網(wǎng)絡(luò)魯棒性研究. 計(jì)算機(jī)應(yīng)用研究, 2010, 27(4): 1403–1406.

14Dorogovtsev SN, Mendes JFF, Samukhin AN. Structure of growing networks with preferential linking. Physical Review Letters, 2000, 85(21): 4633–4636. [doi: 10.1103/PhysRevLett.85.4633]

15Pastor-Satorras R, Vespignani A. Epidemic spreading in scale-free networks. Physical Review Letters, 2001, 86(14):3200–3203. [doi: 10.1103/PhysRevLett.86.3200]

16Zhou T, Fu ZQ, Wang BH. Epidemic dynamics on complex networks. preprint physics/0508096, 2005.

17Cohen R, Havlin S. Scale-free networks are ultrasmall.Physical Review Letters, 2003, 90(5): 058701. [doi: 10.1103/PhysRevLett.90.058701]

Research on the Local Immunization Strategy of Virus Spreading in Weighted Scale-Free Networks

LIU Rui-Jun
(Laboratory Management Center, Wuyi University, Wuyishan 354300, China)

In order to further describe the virus propagation of real-life complex networks, this paper improves the traditional construction methods of weighted scale-free networks model which considers two key factors: flow bandwidth and individual resistance. Using mean-field theory to simulate the process of the virus transmission, this article analyses the experimental data and verifies the validity of the new model. Most real-life complex networks are known to us with only the local topology information and the traditional virus immunization strategies are based on global network topology information. In condition of knowing local topology information, this paper proposes the immunization strategy of virus spreading based on the local optimum in weighted scale-free networks. Compared with the random immunization strategy and target immunization strategy about the efficiency of virus spreading in weighted scale-free networks, the local optimum immunization strategy is verified to be valid through the dynamic simulation of virus propagation.

weighted scale-free networks; virus spreading; flow bandwidth; individual resistance; local optimum

劉瑞軍.加權(quán)無(wú)標(biāo)度網(wǎng)絡(luò)病毒傳播和局部免疫策略研究.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(7):263–268. http://www.c-s-a.org.cn/1003-3254/5835.html

福建省教育廳基金(JK2012056)

2016-10-13; 收到修改稿時(shí)間: 2016-11-28