復(fù)雜網(wǎng)絡(luò)上疾病傳播與免疫及動(dòng)力學(xué)資料

1、復(fù)雜(fz)網(wǎng)絡(luò)的傳播機(jī)理與動(dòng)力學(xué)分析張玉林2010.11.28共九十二頁(yè)復(fù)雜(fz)網(wǎng)絡(luò)中疾病傳播與免疫復(fù)雜網(wǎng)絡(luò)的傳播臨界值理論復(fù)雜網(wǎng)絡(luò)的免疫策略與技術(shù)共九十二頁(yè)主要內(nèi)容(nirng):1. 疾病傳播的基本知識(shí)2. SIS和SIR傳播模型3. 均勻網(wǎng)絡(luò)中的SIS模型, WS模型為例進(jìn)行解析4.無(wú)標(biāo)度網(wǎng)絡(luò)中的SIS模型, BA模型為例進(jìn)行解析復(fù)雜(fz)網(wǎng)絡(luò)的傳播臨界值理論共九十二頁(yè)1. 疾病(jbng)傳播I. 傳染病：數(shù)理學(xué)家在研究傳播行為時(shí)，往往并不區(qū)別研究對(duì)象，他們把可以在網(wǎng)絡(luò)中傳播開(kāi)來(lái)的東西叫做傳染病。II. 在傳播過(guò)程中，個(gè)體處于三個(gè)基本狀態(tài)：(1) S(susceptible)易

2、感狀態(tài)：不會(huì)傳染他人，可能被傳染（也就是健康狀態(tài)）(2) I(infected) 感染狀態(tài)：已患病(hun bn)，具有傳染性(3) R(removed) 免疫狀態(tài)：被治愈，具有免疫能力，不具有傳染能力，不會(huì)再次被感染（移除狀態(tài)）共九十二頁(yè). 傳染病模型 科學(xué)家通過(guò)用基本狀態(tài)之間的相互轉(zhuǎn)換來(lái)建立不同的傳播模型： SIS模型：易染個(gè)體被感染后，可以被治愈但無(wú)免疫力（還可以再被感染）（感冒等）SIR模型：易染個(gè)體被感染后，可以被治愈且有免疫力（不會(huì)被感染，也不會(huì)感染其它節(jié)點(diǎn)，相當(dāng)于已經(jīng)從傳播網(wǎng)絡(luò)(wnglu)中被清除了）（天花等）SI模型：易染個(gè)體被感染后，不能被治愈（艾滋病等） SIRS模型：易

3、染個(gè)體被感染后，可以被治愈且有免疫力，但免疫期是有限的，還會(huì)再次回到易染狀態(tài)。（乙肝？）共九十二頁(yè) 疾病傳播模型(mxng)的描述. 模型(mxng)的傳播規(guī)則： 初始時(shí)隨機(jī)選擇網(wǎng)絡(luò)中一個(gè)或若干節(jié)點(diǎn)為染病節(jié)點(diǎn)（I），其余為健康節(jié)點(diǎn)（S） 在每一個(gè)時(shí)間步t： 如果一個(gè)健康節(jié)點(diǎn)具有染病鄰居，則它依某個(gè)事先設(shè)定的概率變成染病節(jié)點(diǎn)，這一概率叫做染病概率（）；同時(shí)每一個(gè)染病節(jié)點(diǎn)都依某個(gè)事先設(shè)定的痊愈概率（）變成健康節(jié)點(diǎn)。 在每個(gè)時(shí)間步，這些演化規(guī)則在整個(gè)網(wǎng)絡(luò)中被并行地執(zhí)行。染病概率越大，痊愈概率越小，疾病就越有可能感染更多的人，因此，定義染病概率和痊愈概率的比值為有效傳播率 并用這個(gè)參數(shù)綜合地衡量疾病自

4、身特征。共九十二頁(yè) 感染(gnrn)密度（感染水平或者波及范圍）(t) (t)：傳播過(guò)程中,感染節(jié)點(diǎn)總數(shù)占總節(jié)點(diǎn)數(shù)的比例。：傳播到穩(wěn)態(tài)時(shí)（ ）感染密度的值,稱(chēng)為穩(wěn)態(tài)感染密度。 有效傳播率(=/) 非常?。ê苄?，很大），傳播達(dá)穩(wěn)態(tài)時(shí)，所有節(jié)點(diǎn)都會(huì)變成健康節(jié)點(diǎn)，這種情況下就認(rèn)為疾病沒(méi)有在網(wǎng)絡(luò)上傳播開(kāi)來(lái)，并記該疾病的穩(wěn)態(tài)感染密度 =0。 反之，當(dāng)足夠大時(shí)，疾病將一直在網(wǎng)絡(luò)中存在而不會(huì)完全消失，只是染病節(jié)點(diǎn)的數(shù)目有時(shí)多有時(shí)少，這時(shí)穩(wěn)態(tài)感染水平（波及范圍） 0。把穩(wěn)態(tài)感染密度從零向正實(shí)數(shù)變化的那個(gè)點(diǎn)所對(duì)應(yīng)的有效傳播率稱(chēng)作傳播閾值（臨界值） c。它是衡量網(wǎng)絡(luò)上的傳播行為最重要的參量之一。. 傳播模型研究(

5、ynji)的主要參量共九十二頁(yè) SIS模型傳播方程設(shè)s,i分別表示群體中S,I個(gè)體所占的比例，則SIS傳播的微分方程組為： SIR模型傳播方程 設(shè)s,i,r分別表示群體中S,I,R個(gè)體所占的比例，則疾病傳播的動(dòng)力(dngl)微分方程組為：注: (1) 傳播網(wǎng)絡(luò)是完全圖，但實(shí)際網(wǎng)絡(luò)中，只有接觸才能被感染 (2) 并不是對(duì)每個(gè)節(jié)點(diǎn)都一致，而是服從分布 ， Newman對(duì)其進(jìn)行了研究。 . 模型傳播(chunb)動(dòng)力學(xué)方程共九十二頁(yè)3. 均勻(jnyn)網(wǎng)絡(luò)中的SIS模型. 均勻網(wǎng)絡(luò)： . 解析模型三個(gè)假設(shè)： 均勻混合假設(shè)：感染強(qiáng)度和感染個(gè)體密度 成比例。即： 和為常數(shù)（均勻混合）。不失一般性，可假

6、設(shè)=1，因?yàn)檫@只影響疾病傳播(chunb)的時(shí)間尺度； 均勻性假設(shè)：均勻網(wǎng)絡(luò)中，每個(gè)節(jié)點(diǎn)的度都等于網(wǎng)絡(luò)的平均度； 規(guī)模不變假設(shè)：假設(shè)病毒的時(shí)間尺度遠(yuǎn)小于個(gè)體的生命周期，即不考慮個(gè)體的出生和自然死亡 共九十二頁(yè)運(yùn)用(ynyng)平均場(chǎng)的方法可得：被感染個(gè)體密度(t)的變化率 被感染節(jié)點(diǎn)以單位速率恢復(fù)健康單個(gè)感染節(jié)點(diǎn)產(chǎn)生的新感染節(jié)點(diǎn)的平均密度，它與有效傳播率、節(jié)點(diǎn)的平均度k，健康節(jié)點(diǎn)相連概率1-(t)成比例，（其他的高階校正項(xiàng)忽略了）。共九十二頁(yè)當(dāng)傳播達(dá)到(d do)穩(wěn)態(tài)時(shí)，變化率為0，所以令上式右端為0； 即：-+1-=0 （1-+）=0； （- ）=0；當(dāng) 時(shí)，- 必大于0，所以=0；當(dāng) 時(shí)，

7、= ；所以， 即為臨界傳播值，記 = 。共九十二頁(yè)結(jié)論：在均勻網(wǎng)絡(luò)中存在一個(gè)有限的正的傳播臨界值c。如果有效傳播率 c，則病毒可以在網(wǎng)絡(luò)中傳播開(kāi)來(lái)，并最終穩(wěn)定于 ,此時(shí)稱(chēng)網(wǎng)絡(luò)處于激活相態(tài)；如果有效傳播率0時(shí)，有結(jié)論： BA無(wú)標(biāo)度網(wǎng)絡(luò)在SIS模型(mxng)下的 只要有效傳播率0，病毒就能傳播開(kāi)來(lái)，并將達(dá)到一個(gè)穩(wěn)定感染水平 ，這反映了無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)抵抗病毒的脆弱性共九十二頁(yè)BA網(wǎng)絡(luò)中，疾病傳播(chunb)的時(shí)間演化 N=106，從下至上從0.05到0.065共九十二頁(yè)WS網(wǎng)絡(luò)(wnglu)與BA網(wǎng)絡(luò)的比較共九十二頁(yè)總結(jié)(zngji)1. SIS模型在均勻網(wǎng)絡(luò)中，存在一個(gè)傳播臨界值 。當(dāng)時(shí)，疾病在

8、時(shí)間(shjin)演化過(guò)程中逐漸衰減，最終被滅；當(dāng)時(shí)，疾病在時(shí)間演化過(guò)程中傳播開(kāi)來(lái)，并穩(wěn)定于某一值（穩(wěn)態(tài)感染密度）： 2. SIS模型在SF網(wǎng)絡(luò)中，傳播臨界值：只要有效傳播率0，病毒就能傳播開(kāi)來(lái)，并將達(dá)到一穩(wěn)定感染水平 值： ，這反映了無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)抵抗病毒的脆弱性。共九十二頁(yè)復(fù)雜網(wǎng)絡(luò)的傳播臨界值理論(lln)復(fù)雜網(wǎng)絡(luò)的免疫策略與技術(shù)報(bào)告(bogo)內(nèi)容共九十二頁(yè)主要內(nèi)容1. 隨機(jī)免疫與集中接種2.目標(biāo)(mbio)免疫與優(yōu)先免疫3. 熟人免疫與環(huán)狀接種免疫(miny)策略與技術(shù)共九十二頁(yè)隨機(jī)免疫與集中接種：將所有可能感染的種群集中起來(lái)，按照某種概率隨機(jī)選擇種群中的個(gè)體進(jìn)行(jnxng)接種。 （

9、度大節(jié)點(diǎn)和度小節(jié)點(diǎn)是平等對(duì)待）1992年，Anderson和May人類(lèi)傳染病， Oxford University Press SIS傳播方式說(shuō)明隨機(jī)免疫1. 隨機(jī)(su j)免疫（均勻免疫）共九十二頁(yè)引入免疫參數(shù)g：初始網(wǎng)絡(luò)中免疫節(jié)點(diǎn)數(shù)占節(jié)點(diǎn)總數(shù)的比例在平均場(chǎng)理論下可以通系數(shù)（1-g）來(lái)影響有效傳播率，即用（1-g）來(lái)替換代入前面的變換率方程(fngchng)中 （均勻網(wǎng)絡(luò)，WS） （SF網(wǎng)絡(luò)，BA）共九十二頁(yè)均勻(jnyn)網(wǎng)絡(luò)（以WS為例）令上式為0，得：共九十二頁(yè) 即：我們需要的免役臨界值 顯然(xinrn) ，才有意義。 情況下，如果不加免疫，疾病將傳播開(kāi)來(lái)，并穩(wěn)定于某一值(0)；如

10、果加免疫后，只要免疫值 滿(mǎn)足：疾病將不能傳播開(kāi)來(lái)，即達(dá)到穩(wěn)態(tài)時(shí)，0。. SF網(wǎng)絡(luò)(wnglu)（以BA為例） SF網(wǎng)絡(luò)的免疫臨界值可由公式 給出，即：共九十二頁(yè)結(jié)論： 在均勻網(wǎng)絡(luò)中：只要 ，就可保證疾病不在網(wǎng)絡(luò)中傳播開(kāi)來(lái)；SF網(wǎng)絡(luò)中：免疫臨界值約為，即任給定一值，都需要對(duì)網(wǎng)絡(luò)中的所有個(gè)體進(jìn)行免疫才能使疾病不傳播開(kāi)來(lái)。說(shuō)明隨機(jī)免疫只對(duì)均勻網(wǎng)絡(luò)有效（有較小的),而對(duì)SF網(wǎng)絡(luò)效果很差（ =1）。原因： 這是由于SF網(wǎng)絡(luò)是異質(zhì)網(wǎng)絡(luò)，節(jié)點(diǎn)度呈兩極分化，采用隨機(jī)免疫，哪些最容易傳播病毒的節(jié)點(diǎn)（度大的節(jié)點(diǎn)）不一定獲得免疫。所以，如果對(duì)SF網(wǎng)絡(luò)采取隨機(jī)免疫的策略，需要對(duì)網(wǎng)絡(luò)中幾乎所有的節(jié)點(diǎn)都實(shí)施免疫才能保證最

11、終(zu zhn)消滅病毒傳染。 因此對(duì)SF網(wǎng)絡(luò)這樣的異質(zhì)網(wǎng)絡(luò)，普遍認(rèn)為：隨機(jī)免疫策略對(duì)于無(wú)標(biāo)度網(wǎng)絡(luò)是無(wú)效的！共九十二頁(yè)目標(biāo)免疫：選取少量度最大的節(jié)點(diǎn)進(jìn)行免疫。（而一旦這些節(jié)點(diǎn)被免疫后，就意味著他們所連的邊可以從網(wǎng)絡(luò)中去除，使得病毒傳播的可能途徑大大減少。）假設(shè)(jish)對(duì)度kkt的節(jié)點(diǎn)進(jìn)行免疫，即有： 引入定義（免疫平均度，免疫二階矩）：p(g)：任給一條邊，該邊指向一個(gè)免疫節(jié)點(diǎn)的概率。且有： （免疫節(jié)點(diǎn)的平均度） （平均度） 2.目標(biāo)(mbio)免疫（選擇免疫）共九十二頁(yè)將比例為g的免疫節(jié)點(diǎn)看作已從網(wǎng)絡(luò)(wnglu)中移除，且從這些節(jié)點(diǎn)出發(fā)的邊也被刪除了。則新的度分布： （指向非免疫節(jié)點(diǎn)

12、的概率）共九十二頁(yè)在SF網(wǎng)絡(luò)(wnglu)中，有：特別地，在BA網(wǎng)絡(luò)(wnglu)情況下：共九十二頁(yè)同樣，將 代入t及t 得：將、代入 式中。對(duì)代入后的方程求得一個(gè)近似解： 上式表明：即使有效傳播率在很大的范圍內(nèi)取值，都可以得到較小的免疫臨界值 (對(duì)少量的節(jié)點(diǎn)進(jìn)行免疫,即可消除(xioch)病毒擴(kuò)散)。共九十二頁(yè)環(huán)狀接種：隔離或免疫染病個(gè)體的所有(距離為k)鄰居禽流感等熟人免疫：從群體中以比例p隨機(jī)(su j)選擇個(gè)體,再隨機(jī)選擇該個(gè)體的一個(gè)相鄰個(gè)體進(jìn)行免疫接觸追蹤：對(duì)與有傳染性個(gè)體的接觸者進(jìn)行跟蹤，然后以一定的概率進(jìn)行免疫 非典病等 例子 (Huerta和TSimring) T：被監(jiān)控態(tài) T

13、：被追蹤的強(qiáng)度 r：被檢查的強(qiáng)度 3. 其他(qt)免疫共九十二頁(yè)現(xiàn)實(shí)(xinsh)中計(jì)算機(jī)病毒免疫的例子以Internet為例，用戶(hù)不斷地安裝一些更新的反病毒軟件，但計(jì)算機(jī)病毒的生命期還是很長(zhǎng)。原因就在于反病毒軟件的更新過(guò)程實(shí)際上是一種隨機(jī)免疫過(guò)程。從個(gè)體來(lái)看，這種措施是有效的；但是從全局范圍看，由Internet的無(wú)標(biāo)度特性，就算隨機(jī)選取大量節(jié)點(diǎn)進(jìn)行(jnxng)免疫，也不能根除計(jì)算機(jī)病毒的傳播。顯示了SIS模型在一部分Internet映像中隨機(jī)免疫（大圖）和目標(biāo)免疫（小圖）的情況。（0.25）共九十二頁(yè)復(fù)雜網(wǎng)絡(luò)的傳播動(dòng)力學(xué)1.d維NW小世界網(wǎng)絡(luò)的線(xiàn)性傳播方程(fngchng)2.小世界網(wǎng)

14、絡(luò)傳播動(dòng)力方程的分形、混沌和分岔3.小世界網(wǎng)絡(luò)的廣義傳播動(dòng)力方程及其分岔4.復(fù)雜網(wǎng)絡(luò)傳染動(dòng)力方程的分岔與震蕩5.復(fù)雜網(wǎng)絡(luò)中的其他傳播現(xiàn)象共九十二頁(yè)在一個(gè)有著少量長(zhǎng)程連接(捷徑)的小世界模型網(wǎng)絡(luò)中研究了傳播和最短路徑。類(lèi)似的傳播比如森林火災(zāi)和傳染病。用很簡(jiǎn)單的規(guī)則：每一步，從已經(jīng)被感染的節(jié)點(diǎn)(ji din)向所有鄰接的未被感染的節(jié)點(diǎn)傳播。關(guān)注于通過(guò)隨機(jī)長(zhǎng)程連接的直接反應(yīng)，在系統(tǒng)中并沒(méi)有考慮到時(shí)滯因素。Newman,Moukarzel提出的模型是，隨機(jī)的添加長(zhǎng)程連接，而不破壞原來(lái)的連接，觀察小的概率值P對(duì)于小世界網(wǎng)絡(luò)特性的影響。并將每個(gè)特性的分析結(jié)果與仿真結(jié)果進(jìn)行比較。共九十二頁(yè)如下圖所示，假設(shè)從

15、最初的感染節(jié)點(diǎn)A開(kāi)始，病毒以常速v=1開(kāi)始傳播(chunb)。NW小世界網(wǎng)絡(luò)中捷徑端點(diǎn)的密度為 ，這里p是小世界網(wǎng)絡(luò)模型中添加新捷徑的概率參數(shù)。不妨假設(shè)這個(gè)傳播過(guò)程是連續(xù)的。因此網(wǎng)絡(luò)中節(jié)點(diǎn)的感染量V(t)是一個(gè)從A開(kāi)始的以t為半徑的球體 ， 這里 是d維小世界網(wǎng)絡(luò)中的超球體常數(shù)。感染源在傳播過(guò)程中碰到捷徑端點(diǎn)的概率為 ，并因此而產(chǎn)生新的感染球體為 。共九十二頁(yè)共九十二頁(yè)平均的總感染量V(t)由下面形式的積分方程得到：對(duì)上式做標(biāo)度(bio d)變換 化為對(duì)所得方程微分得共九十二頁(yè)顯然，這個(gè)方程(fngchng)的解是隨著時(shí)間t的增大而發(fā)散的。共九十二頁(yè)對(duì)先前模型(mxng)的改進(jìn)Yang認(rèn)為NW

16、小世界網(wǎng)絡(luò)的感染量V(t)中，由于現(xiàn)實(shí)中存在的等待時(shí)間，新引發(fā)的病毒感染或者火災(zāi)發(fā)生相比而言都有一個(gè)時(shí)滯（遠(yuǎn)程連接而言），因此，相應(yīng)的線(xiàn)性時(shí)滯傳播(chunb)方程為：解為：共九十二頁(yè)計(jì)算(j sun)分形維數(shù)D本模型是對(duì)先前模型的一個(gè)擴(kuò)展，去探求有時(shí)滯的小世界模型的分形維數(shù)和一些其他網(wǎng)絡(luò)特性，因?yàn)榍蟪霾罘址匠痰慕獠⒉皇呛苋菀祝院苡斜匾鰯?shù)字模擬，主要關(guān)注一維和二維網(wǎng)絡(luò)。這里利用(lyng)解析方法，然后和數(shù)字模擬的結(jié)果進(jìn)行比較。計(jì)算分形維數(shù)D，從圖中可以看出分析結(jié)果和實(shí)際數(shù)據(jù)擬合還是不錯(cuò)的。時(shí)滯參數(shù)對(duì)于分形維數(shù)D和其他諸如速度等的特性影響是很大。結(jié)論：如果足夠的時(shí)滯引入的話(huà)，一個(gè)小世界網(wǎng)

17、絡(luò)可以變的更大，另一方面，要使一個(gè)大世界網(wǎng)絡(luò)轉(zhuǎn)變?yōu)樾∈澜缇W(wǎng)絡(luò)，需要一個(gè)稍微大的長(zhǎng)程連接概率P。共九十二頁(yè)按式： 計(jì)算上式的分形維數(shù)D后發(fā)現(xiàn)(fxin) 決定著NW小世界網(wǎng)絡(luò)的分形維數(shù)。共九十二頁(yè)進(jìn)一步講，在病毒、火災(zāi)以及Internet和通信網(wǎng)絡(luò)中信息流的傳播和擴(kuò)散(kusn)過(guò)程中存在的非線(xiàn)性摩擦等障礙因素，都會(huì)對(duì)傳播過(guò)程產(chǎn)生不可忽視的影響。因此還應(yīng)加入非線(xiàn)性摩擦項(xiàng)。從而有：經(jīng)過(guò)標(biāo)度代換和微分d次后得到如下的非線(xiàn)性傳播方程：其中：共九十二頁(yè)如果將上式寫(xiě)成離散形式，令d=1，則一維離散小世界網(wǎng)絡(luò)(wnglu)的傳播方程為： 變量代換得到共九十二頁(yè)當(dāng) 時(shí)，系統(tǒng)(xtng)出現(xiàn)混沌； 當(dāng) 時(shí)，系統(tǒng)

18、趨于穩(wěn)定的不動(dòng)點(diǎn)；當(dāng) 時(shí)，系統(tǒng)出現(xiàn)倍周期分岔的傳播過(guò)。共九十二頁(yè)對(duì)于非線(xiàn)性傳播方程式，只考慮d=1的一維情形(qng xing)，即：以為分岔參數(shù)，如果，那么上述方程在處出現(xiàn)Hopf分岔。Li C G,Chen G.Local stability and Hopf bifurcation in small-world delayed networks.Chaos,Solitons and Fractals,2004,20:353-361.共九十二頁(yè)3 小世界網(wǎng)絡(luò)(wnglu)的廣義傳播動(dòng)力方程及其分岔前面的NW小世界網(wǎng)絡(luò)傳播方程都是經(jīng)過(guò)一系列標(biāo)度和時(shí)間變換得到的，這些變換都與NW小世界網(wǎng)絡(luò)模型

19、的概率參數(shù)p有關(guān)，因此，當(dāng)p變化時(shí)所帶來(lái)的網(wǎng)絡(luò)結(jié)構(gòu)演化，在傳播方程中被標(biāo)度變換式掩蓋而無(wú)法顯現(xiàn)出來(lái)。此外，p=0時(shí)的最近鄰網(wǎng)絡(luò)是NW小世界網(wǎng)絡(luò)的一個(gè)特例，然而上述方程卻不能包含這一特定的網(wǎng)絡(luò)結(jié)構(gòu)，因?yàn)閜=0時(shí)，方程沒(méi)有意義。本文提出一個(gè)非線(xiàn)性病毒傳播模型，來(lái)描述增加新連接概率P在NW小世界網(wǎng)絡(luò)模型中的拓?fù)滢D(zhuǎn)化中的影響。在所有(suyu)類(lèi)型的病毒傳播中都純?cè)贖opf分岔。P不僅決定了NW小世界網(wǎng)絡(luò)模型的拓?fù)滢D(zhuǎn)變，在網(wǎng)絡(luò)的穩(wěn)定性方面也主導(dǎo)作用。Li X,Chen G,Li C G.Stability and bifurcation of disease spreading in complex

20、networks.Int.J.of Systems Science,2004,35:527-536共九十二頁(yè)改進(jìn)后的模型，定義新的摩擦項(xiàng)，帶入此時(shí)方程被推廣為：這樣不做任何標(biāo)度變換(binhun)而直接微分上面的方程，就得到了NW小世界網(wǎng)絡(luò)的更廣義的非線(xiàn)性傳播方程：共九十二頁(yè)定義了一些變量，經(jīng)計(jì)算可得相應(yīng)的分岔(fn ch)周期解的方向、穩(wěn)定性和周期等性質(zhì)。共九十二頁(yè)計(jì)算發(fā)現(xiàn)，在不同的時(shí)滯作用下，分岔參數(shù)表現(xiàn)出來(lái)的對(duì)小世界(shji)網(wǎng)絡(luò)模型參數(shù)P的依賴(lài)性是截然不同的。共九十二頁(yè)4 復(fù)雜網(wǎng)絡(luò)傳染動(dòng)力(dngl)方程的分岔與震蕩考察(koch)在無(wú)尺度網(wǎng)絡(luò)（由真實(shí)的電子郵件網(wǎng)絡(luò)中估計(jì)而來(lái)的）中通

21、過(guò)郵件傳播的計(jì)算機(jī)病毒的傳播動(dòng)態(tài)特性，我們認(rèn)為一個(gè)增長(zhǎng)的網(wǎng)絡(luò)，有一個(gè)新的使用者加進(jìn)來(lái)，都會(huì)導(dǎo)致從一個(gè)近乎滅絕的狀態(tài)中恢復(fù)過(guò)來(lái)。首先考慮一個(gè)無(wú)尺度網(wǎng)絡(luò)中真實(shí)的傳染病模型，為了更好的理解這種震蕩的傳染行為，分析了一個(gè)可以用確定性方程描述的簡(jiǎn)化增長(zhǎng)模型。共九十二頁(yè)簡(jiǎn)化(jinhu)模型（同質(zhì)的SIR模型）用微分或者差分方程描述的傳染過(guò)程中的不動(dòng)點(diǎn)穩(wěn)定性以及(yj)分岔等震蕩行為也受到了關(guān)注。SIRS模型的動(dòng)力方程可以用下面的微分方程表示：將上面的SIRS模型推廣得到SIRS模型的差分方程形式如下：Ramani A,Carstea A S,Willox R,Grammations B.Oscillat

22、ing epidemics:a discrete-time model.Physica A,2004,333:278-292共九十二頁(yè)確定性模型分析結(jié)果發(fā)現(xiàn)，這個(gè)SISR過(guò)程并不是簡(jiǎn)單地趨于一個(gè)穩(wěn)定的不動(dòng)點(diǎn)，它在某些相對(duì)的痊愈/感染條件下會(huì)出現(xiàn)震蕩的傳染行為。Hayashi等也利用均勻網(wǎng)絡(luò)和非均勻網(wǎng)絡(luò)的SIR模型來(lái)研究(ynji)計(jì)算機(jī)病毒的傳播過(guò)程。 (a)震蕩情形 (b)收斂情形Hayashi Y,Minoura M,Matsukubo J.Oscillatory epidemic prevalence in growing scale-free networks.Phys.Rev.E,2

23、004,69:016112共九十二頁(yè)5 計(jì)算機(jī)病毒在Internet上的傳播 4.5.1 紅色代碼蠕蟲(chóng)的隨機(jī)常數(shù)傳播模型(RCS) 4.5.2 蠕蟲(chóng)的間隔(jin g)模型 4.5.3 電子郵件病毒的傳播模型 4.5.4 電子郵件病毒傳播的仿真模擬共九十二頁(yè)5 計(jì)算機(jī)病毒在Internet上的傳播(chunb)縱觀計(jì)算機(jī)病毒的發(fā)展史，20世紀(jì)90年代初，絕大多數(shù)病毒的傳播途徑是磁盤(pán)，因而這一時(shí)期的病毒破壞力大多局限于某個(gè)局部的范圍，傳播的速度也相對(duì)較慢，隨著Internet的飛速發(fā)展，計(jì)算機(jī)病毒的傳播方式和速度也不段升級(jí)。本節(jié)，主要介紹計(jì)算機(jī)病毒在Internet上傳播的一些模型和研究結(jié)果(j

24、i gu)。通過(guò)電子郵件方式傳播病毒已成為Internet上病毒傳播的一種新的主要形式，所以本節(jié)對(duì)電子郵件病毒傳播的研究予以比較詳細(xì)的介紹。共九十二頁(yè)4.5.1 紅色代碼(di m)蠕蟲(chóng)的隨機(jī)常數(shù)傳播模型(RCS)用隨機(jī)常數(shù)傳播模型來(lái)模擬紅色代碼蠕蟲(chóng)的爆發(fā)過(guò)程。該模型作了三個(gè)近似假設(shè)：一是忽略了系統(tǒng)可能被打補(bǔ)丁、關(guān)閉或切斷連接；二是認(rèn)為易攻擊的目標(biāo)數(shù)在這一模型中是常數(shù)；三是把Internet看作一個(gè)無(wú)向完全連接圖。令K為平均初始感染率，即每輪開(kāi)始的時(shí)候，被感染主機(jī)在單位時(shí)間內(nèi)攻擊易染主機(jī)的數(shù)目。假設(shè)K為常數(shù)，N為網(wǎng)絡(luò)中的易染主機(jī)數(shù)，a為時(shí)刻t已被感染的主機(jī)的比例（設(shè)a為一常數(shù)），那么時(shí)刻t被感

25、染的主機(jī)數(shù)為Na，這些主機(jī)在單位時(shí)間內(nèi)以速率K掃描(somio)其他易染主機(jī)。Staniford S,Paxson V,Weaver N.How to own the Internet in your spare time.Proceedings of the 11th USENIX Security Symposium,August 2002,149-167共九十二頁(yè)由于比例為a的主機(jī)已經(jīng)被感染，所以每個(gè)感染主機(jī)每單位(dnwi)時(shí)間內(nèi)會(huì)使 個(gè)新的主機(jī)被感染。因此可以得到在下一時(shí)間段dt內(nèi)將被新感染的主機(jī)數(shù)n的表達(dá)式：設(shè)兩個(gè)不同的蠕蟲(chóng)在同一時(shí)刻攻擊同一目標(biāo)的可能性很小，忽略不計(jì)。在N為常數(shù)的

26、假設(shè)下， ，帶入上式，得到如下的Logistic微分方程： 其解為L(zhǎng)ogistic曲線(xiàn)：共九十二頁(yè)T表示病毒傳播事件發(fā)生的固定(gdng)時(shí)點(diǎn)，即被感染數(shù)最快速增長(zhǎng)的時(shí)刻，意味著病毒開(kāi)始爆發(fā)。當(dāng)時(shí)刻t遠(yuǎn)早于時(shí)刻T時(shí)，a呈指數(shù)增長(zhǎng)；當(dāng)時(shí)刻t遠(yuǎn)晚于T時(shí)，a趨向于1，即所有的易染主機(jī)都被感染了。感染速率僅依賴(lài)于K而與主機(jī)總數(shù)無(wú)關(guān)，這說(shuō)明，像紅色代碼蠕蟲(chóng)這樣的病毒在Internet上有可能相當(dāng)迅速地感染所有易染主機(jī)。本文提出一個(gè)非常簡(jiǎn)單的模型，對(duì)紅色病毒進(jìn)行理論建模，并與實(shí)際數(shù)據(jù)進(jìn)行比較。共九十二頁(yè)下圖為紅色代碼蠕蟲(chóng)第二輪再次爆發(fā)時(shí)，美國(guó)化學(xué)文摘服務(wù)社80端口被探測(cè)(tnc)掃描的實(shí)際數(shù)據(jù)與RCS模型

27、預(yù)測(cè)的結(jié)果比較，從中可以看出RCS模型對(duì)紅色代碼蠕蟲(chóng)的預(yù)測(cè)還是相當(dāng)準(zhǔn)確的。共九十二頁(yè)4.5.2 蠕蟲(chóng)的間隔(jin g)模型Serazzi認(rèn)為可靠性強(qiáng)的病毒傳播模型是非常有用的，可以預(yù)測(cè)未來(lái)威脅，也可以用來(lái)開(kāi)發(fā)新的的防御措施。這他的文章中，分析了最常用(chn yn)的病毒傳播模型的優(yōu)點(diǎn)與不足，并提出了自己的新的模型，并與實(shí)際數(shù)據(jù)進(jìn)行比較。他認(rèn)為大多數(shù)傳統(tǒng)的計(jì)算機(jī)病毒模型不適合用來(lái)分析被稱(chēng)為“flash”等的蠕蟲(chóng)病毒。理論上而言RCS（隨機(jī)常數(shù)傳播模型）模型應(yīng)該使用于Slammer病毒，但模型數(shù)據(jù)和實(shí)際數(shù)據(jù)之間出現(xiàn)了很大差異，如下圖所示。Serazzi G,Zanero S.Computer

28、virus propagation models.2003,Available on URL:http:/www.elet.polimi.it/upload/zanero/papers/zanero-serazzi-virus.pdf共九十二頁(yè)Slammer與紅色代碼是基于不同的網(wǎng)絡(luò)協(xié)議進(jìn)行傳播的，紅色代碼是基于TCP，需要先建立連接，完成(wn chng)TCP的三次握手過(guò)程，等待應(yīng)答，這屬于時(shí)延限制。Slammer是能更否已全速傳播取決于網(wǎng)絡(luò)的帶寬，這是一種網(wǎng)絡(luò)限制。為了更好的分析這種傳播受帶寬限制的計(jì)算機(jī)病毒，Serazzi考慮了節(jié)點(diǎn)之間帶寬的因素，從而在RCS模型基礎(chǔ)上提出一種基于In

29、ternet自治層的間隔模型。共九十二頁(yè)下圖為Slammer蠕蟲(chóng)掃描增長(zhǎng)過(guò)程與RCS模型(mxng)理論估計(jì)值的對(duì)比示意圖：共九十二頁(yè)上圖顯示的是計(jì)算機(jī)病毒進(jìn)行掃描的總次數(shù)，在大約3分鐘時(shí)，蠕蟲(chóng)達(dá)到了它的最大掃描速率，每秒鐘500多萬(wàn)次。這一時(shí)刻之后，增長(zhǎng)的速率減慢。對(duì)次現(xiàn)象常見(jiàn)的解釋為：網(wǎng)絡(luò)的很大以部分無(wú)法(wf)保證蠕蟲(chóng)全速傳播時(shí)所需要的足夠帶寬。也就是說(shuō)在被感染主機(jī)數(shù)量飽和之前帶寬已經(jīng)先飽和了。由于網(wǎng)絡(luò)性能的瓶頸在于AS內(nèi)部連接。共九十二頁(yè)間隔模型是RCS模型的延伸和擴(kuò)展，正是因?yàn)榫W(wǎng)絡(luò)中的流量過(guò)載引起的Internet中的連邊無(wú)法正常傳輸數(shù)據(jù)包，這一模型較好地解釋了攻擊（掃描(somio

30、)）不斷增加，然后又突然停止的現(xiàn)象。共九十二頁(yè)4.5.3 電子郵件(din z yu jin)病毒的傳播模型Zou等人將人們相互之間的電子郵件聯(lián)系看作一種無(wú)向圖，并提出了相應(yīng)的電子郵件病毒傳播模型。模型中主要考慮到兩個(gè)(lin )對(duì)電子郵件病毒傳播有影響的人為因素：一個(gè)是電子郵件檢查時(shí)間 ，即用戶(hù)i檢查電子郵件的時(shí)間間隔。其中|V|是電子郵件用戶(hù)總數(shù)。另一個(gè)因素是附件打開(kāi)概率 ,表示用戶(hù)i打開(kāi)一個(gè)病毒附件的概率。假定各用戶(hù)之間的行為是獨(dú)立的。用戶(hù)的電子郵件檢查時(shí)間是一個(gè)隨機(jī)變量，基于平均郵件檢查時(shí)間 呈指數(shù)分布，假設(shè) 本身也是一個(gè)隨機(jī)變量，定義為T(mén)。Zou C C,Towsley D,Gong

31、 W B.Email virus propagation modeling and analysis.Technical Report TR-CSE-03-04,University of Massachusettes,Amherst 2003共九十二頁(yè)用戶(hù)i檢查任一病毒郵件時(shí)打開(kāi)病毒附件的概率為 ，再定義P為 產(chǎn)生的隨機(jī)變量，即平均概率。用戶(hù)一旦打開(kāi)帶病毒的附件就稱(chēng)為被感染。定義 為病毒傳播開(kāi)始時(shí)已被感染的用戶(hù)數(shù)，他們將向所有的鄰居發(fā)送病毒郵件。變量 定義為病毒傳播過(guò)程中t時(shí)刻被感染的用戶(hù)數(shù)。病毒郵件從發(fā)出到接收需要一定的時(shí)間，但是通常這段時(shí)間相對(duì)于用戶(hù)檢查郵件的時(shí)間來(lái)說(shuō)小得多，因此該模型中

32、忽略了郵件傳送的時(shí)間。模型的不足：用戶(hù)打開(kāi)附件的概率P，對(duì)每個(gè) 用戶(hù)是固定的，而且(r qi)和時(shí)間有關(guān)。共九十二頁(yè)4.5.4 電子郵件病毒傳播的仿真(fn zhn)模擬假定網(wǎng)絡(luò)有100000個(gè)節(jié)點(diǎn)，服從冪律分布，仿真實(shí)驗(yàn)設(shè)定冪律指數(shù) =1.7。模型中其他參數(shù)設(shè)定為： 整個(gè)實(shí)驗(yàn)關(guān)注在不同的感染次數(shù)、初始感染節(jié)點(diǎn)、網(wǎng)絡(luò)拓?fù)浣Y(jié)果和電子郵件檢查時(shí)間等情形下，電子郵件病毒在t時(shí)刻感染的用戶(hù)(yngh)平均數(shù) 。 是經(jīng)過(guò)100次隨機(jī)仿真后得到的平均結(jié)果。Zou C C,Towsley D,Gong W B.Email virus propagation modeling and analysis.Tec

33、hnical Report TR-CSE-03-04,University of Massachusettes,Amherst 2003共九十二頁(yè)1、重復(fù)感染(gnrn)和非重復(fù)感染(gnrn)的對(duì)比重復(fù)感染（reinfection）是指只要用戶(hù)打開(kāi)病毒附件就會(huì)向外發(fā)出病毒郵件的副本，因此一個(gè)接受者可以重復(fù)的地接收(jishu)來(lái)自同一中毒用戶(hù)的病毒郵件。而非重復(fù)感染（non-reinfection）是指感染用戶(hù)僅向外發(fā)送一次病毒郵件副本，以后不再發(fā)送同樣的病毒郵件。下圖為平均感染的用戶(hù)數(shù)和時(shí)間t的關(guān)系圖：共九十二頁(yè) 很顯然(xinrn)，在重復(fù)傳播情況下有更多的用戶(hù)被感染。 右圖，在100次

34、模擬中的每一次都得到(d do)最大值，平均值和最小值。觀察到最初病毒傳播的狀態(tài)決定了整個(gè)的傳播速度?？v坐標(biāo)表示的是時(shí)刻t被感染的用戶(hù)數(shù)。共九十二頁(yè)2、初始(ch sh)感染度大的節(jié)點(diǎn)和度小的節(jié)點(diǎn)的對(duì)比 如圖顯示：初始感染(gnrn)節(jié)點(diǎn)的“身份”（以度的大小衡量）在稀疏的（平均度為8）網(wǎng)絡(luò)中比密集的（平均度為20）網(wǎng)絡(luò)中影響更大。共九十二頁(yè)3、拓?fù)?tu p)結(jié)構(gòu)的影響：隨機(jī)網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和無(wú)標(biāo)度網(wǎng)絡(luò)研究拓?fù)浣Y(jié)構(gòu)是如何影響病毒傳播的。分別在無(wú)尺度網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)中運(yùn)行我們的仿真(fn zhn)。這三個(gè)網(wǎng)絡(luò)具有相同的平均度8，都有100000個(gè)節(jié)點(diǎn)。下圖顯示了平均感染用戶(hù)數(shù)與時(shí)間t

35、的關(guān)系。正如圖中顯示：小世界網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)中病毒傳播非常類(lèi)似。二者具有相近的平均路徑長(zhǎng)度，但小世界網(wǎng)絡(luò)的聚集系數(shù)要比隨機(jī)網(wǎng)絡(luò)的更大。在無(wú)尺度網(wǎng)絡(luò)中病毒傳播更快，原因之一是無(wú)尺度網(wǎng)絡(luò)的平均最短路徑相對(duì)小世界和隨機(jī)圖網(wǎng)絡(luò)要更短。另一個(gè)原因是無(wú)尺度網(wǎng)絡(luò)中節(jié)點(diǎn)度相差很大，一旦病毒感染到度很大的節(jié)點(diǎn)，傳播速度就會(huì)被“放大”。共九十二頁(yè) 實(shí)驗(yàn)發(fā)現(xiàn)，小世界網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)上的傳播行為十分相似，這說(shuō)明影響郵件病毒傳播率的是平均路徑長(zhǎng)度而非聚類(lèi)系數(shù)。而對(duì)于冪律分布的無(wú)標(biāo)度網(wǎng)絡(luò)，病毒的傳播率更快。 每個(gè)節(jié)點(diǎn)被傳染的概率是和度成正比的。雖然這三個(gè)網(wǎng)絡(luò)具有相同(xin tn)平均度，但是在無(wú)尺度網(wǎng)絡(luò)中，度小的節(jié)點(diǎn)數(shù)要比

36、另兩個(gè)多，所以，無(wú)尺度網(wǎng)絡(luò)中更多的節(jié)點(diǎn)在病毒傳播的后期沒(méi)有被感染。共九十二頁(yè) 上圖中很清晰的顯示出病毒在無(wú)尺度網(wǎng)絡(luò)上傳播分兩個(gè)階段，開(kāi)始的時(shí)候病毒會(huì)感染連接(linji)最多的節(jié)點(diǎn)(most highly connected nodes)，之后就是度小一些的節(jié)點(diǎn)被感染。在小世界網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)中都沒(méi)有出現(xiàn)這種情況。共九十二頁(yè)4、 冪律指數(shù)(zhsh)的影響冪律指數(shù)越小，度分布變化幅度越大。在之前的仿真中，我們?cè)O(shè)定冪律指數(shù)為1.7，擁有100000個(gè)節(jié)點(diǎn)的無(wú)尺度網(wǎng)絡(luò)。這個(gè)網(wǎng)絡(luò)度最大度節(jié)點(diǎn)度為1833，最小的3，對(duì)應(yīng)著郵件地址簿的大小。Internet AS層冪律拓?fù)涞膬缏芍笖?shù)為1.1475，最大度

37、為28000，最小度為1.由于不知道真實(shí)的郵件網(wǎng)絡(luò)的冪律指數(shù)值，為了研究?jī)缏芍笖?shù)對(duì)于病毒傳播的影響，作者比較了節(jié)點(diǎn)數(shù)相同，平均度均為8，冪律指數(shù)為1.7和1.1475的兩個(gè)(lin )網(wǎng)絡(luò)。下圖為實(shí)驗(yàn)結(jié)果。共九十二頁(yè)共九十二頁(yè)對(duì)于具有冪律度分布的網(wǎng)絡(luò)，不同的冪律指數(shù)對(duì)電子郵件病毒傳播的影響也不相同。冪律指數(shù)大的網(wǎng)絡(luò)病毒傳播剛開(kāi)始較快，稍后變慢。冪律指數(shù)小的網(wǎng)絡(luò)中，少量的節(jié)點(diǎn)聚集了大量的連接。它們一旦被感染，網(wǎng)絡(luò)中就會(huì)有更多的病毒副本。這些度很大的節(jié)點(diǎn)就好像是網(wǎng)絡(luò)的“病毒放大器”。感染了度很大的節(jié)點(diǎn)之后，就到了第二個(gè)階段，主要是感染那些度小的節(jié)點(diǎn)。冪律指數(shù)大的網(wǎng)絡(luò)中，度小的節(jié)點(diǎn)數(shù)量較多，所以(s

38、uy)在第二個(gè)階段傳播更快一些。共九十二頁(yè)5、電子郵件(din z yu jin)檢查時(shí)間的波動(dòng)產(chǎn)生的影響病毒模型中，我們假設(shè)用戶(hù)檢查郵件時(shí)間是服從指數(shù)分布(fnb)的，而檢查時(shí)間有可能是服從其他分布(fnb)的。下圖比較了在電子郵件檢查時(shí)間分別服從三種不同分布(fnb)時(shí)的傳播行為。來(lái)研究郵件檢查時(shí)間對(duì)于病毒傳播的影響。這里假設(shè)三種分布具有相同的平均郵件檢查時(shí)間L。第一種分布是基于平均值L的指數(shù)分布；第二種是基于平均值L的三階Erlang分布；第三種情況是所有用戶(hù)的電子郵件檢查時(shí)間均為常數(shù)L。共九十二頁(yè) 病毒傳播的速度(sd)不僅由平均傳播時(shí)間決定，而且被傳播時(shí)間波動(dòng)影響當(dāng)郵件檢查時(shí)間波動(dòng)越

39、大的時(shí)候，病毒郵件傳播也就越快。共九十二頁(yè)4.5.5 計(jì)算機(jī)病毒傳播(chunb)對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響網(wǎng)絡(luò)的拓?fù)?tu p)結(jié)構(gòu)影響著病毒傳播行為。另一方面，當(dāng)計(jì)算機(jī)病毒在網(wǎng)絡(luò)中傳播時(shí)，網(wǎng)絡(luò)的拓?fù)?tu p)結(jié)構(gòu)也不是一成不變的。在許多情況下，網(wǎng)絡(luò)的拓?fù)?tu p)結(jié)構(gòu)取決于病毒復(fù)制的機(jī)制，即病毒利用不同的途徑和不同的方式進(jìn)行傳播，其傳播所依賴(lài)的媒介網(wǎng)絡(luò)的拓?fù)?tu p)結(jié)構(gòu)也會(huì)發(fā)生改變?？紤]以下四種網(wǎng)絡(luò)：計(jì)算機(jī)之間通過(guò)IP協(xié)議相連構(gòu)成的網(wǎng)絡(luò)；臺(tái)式機(jī)管理員帳戶(hù)共享網(wǎng)絡(luò)；電子郵件地址簿網(wǎng)絡(luò)；用戶(hù)之間傳送電子郵件的網(wǎng)絡(luò)。共九十二頁(yè)下圖為這四種網(wǎng)絡(luò)的度分布。IP網(wǎng)絡(luò)中所有的節(jié)點(diǎn)具有相同的度，所有圖中

40、對(duì)應(yīng)于一個(gè)尖峰。帳戶(hù)共享網(wǎng)絡(luò)度分布包括四個(gè)離散的尖峰，對(duì)應(yīng)于不同類(lèi)型的計(jì)算機(jī)、管理員或是管理策略。后兩種郵件網(wǎng)絡(luò)則具有更為連續(xù)的分布，右圖為它們(t men)的累積度分布。盡管這兩種網(wǎng)絡(luò)都不具有冪律度分布，但其分布都具有相當(dāng)長(zhǎng)的“尾巴”。這表明兩張電子郵件具有一定非均勻性。共九十二頁(yè) 上述四種網(wǎng)絡(luò)表明，不同的病毒復(fù)制和傳播策略有可能導(dǎo)致不同的網(wǎng)絡(luò)拓?fù)?，因此需要有一種不受網(wǎng)絡(luò)拓?fù)渥兓绊懀⑶也恍枰诓《颈l(fā)之前(zhqin)知道傳染機(jī)制的控制策略。Balthrop J,Forrest S,Newman M E J,Williamson M M.Technological networks and the spread of computer viruses.Science,2004,304:527-529.共九十二頁(yè)4.6 復(fù)雜網(wǎng)絡(luò)(wnglu)中的其他傳播現(xiàn)象 4.6.1 謠言在復(fù)雜網(wǎng)絡(luò)中的傳播 4.6.2 傳播蔓延現(xiàn)象的推廣模型與普遍行為共九十二頁(yè)4.6.1 謠言(yoyn)在復(fù)雜網(wǎng)絡(luò)中的傳播謠言在人際關(guān)系中的散布與病毒傳播和擴(kuò)散很相似。也可類(lèi)似地用SIR模型來(lái)描述。Zanette研究了謠言在小世界網(wǎng)絡(luò)中的傳播情況。把人群分為3類(lèi)： 、 和 分