基于再度感染的SIS傳播模型研究

朱曉軍, 張 寧

(上海理工大學(xué)管理學(xué)院,上海 200093)

基于再度感染的SIS傳播模型研究

朱曉軍, 張 寧

(上海理工大學(xué)管理學(xué)院,上海 200093)

提出了復(fù)雜網(wǎng)絡(luò)上一種基于再度感染的SIS傳播模型.在具有樹狀分支結(jié)構(gòu)的網(wǎng)絡(luò)中,針對(duì)某個(gè)染病節(jié)點(diǎn),在考慮其感染子節(jié)點(diǎn)的同時(shí),也考查其再次感染祖先節(jié)點(diǎn)的情況.分別在小世界網(wǎng)絡(luò)和無(wú)標(biāo)度網(wǎng)絡(luò)上進(jìn)行仿真分析,結(jié)果表明,對(duì)于小世界網(wǎng)絡(luò),基于再度感染的SIS傳播模型的穩(wěn)態(tài)感染密度比傳統(tǒng)的SIS傳播模型的要大,而且感染周期越短,穩(wěn)態(tài)感染密度越大;而對(duì)于無(wú)標(biāo)度網(wǎng)絡(luò),雖然基于再度感染的SIS傳播模型的穩(wěn)態(tài)感染密度也比傳統(tǒng)的SIS傳播模型的要大,但是,感染周期對(duì)于穩(wěn)態(tài)感染密度的影響微乎其微,甚至可以忽略.

復(fù)雜網(wǎng)絡(luò);疾病傳播;再度感染;祖先節(jié)點(diǎn)

根據(jù)經(jīng)典的疾病傳播理論,疾病之所以能夠在人群中傳播,是因?yàn)楦腥緜€(gè)體將疾病傳播給了與其存在接觸的其他個(gè)體.目前研究中所用的兩類特別重要的傳播模型是SIR(susceptible-infected-recov-ered)和 SIS(susceptible-infected-susceptible)模型[1-2].在SIR模型中,單個(gè)個(gè)體被劃分為3種類型.第一類是易感人群(S),這類人群不會(huì)感染其他的個(gè)體,但是,有可能被感染;第二類是染病人群(I),這類人群已經(jīng)患病,具有傳染性;第三類是移除人群或者康復(fù)人群(R),這類人群是被治愈獲得免疫能力的個(gè)體或者死亡的個(gè)體,他們不再具有傳染性,也不會(huì)被再次感染.

近年來(lái),科研工作者已經(jīng)研究了許多種模型,從數(shù)學(xué)形式上描述疾病傳播的過程,與此同時(shí),各種免疫策略也相繼被提出來(lái)應(yīng)對(duì)不同的疾病傳播.Pastor-Satorras和Vespignani等用平均場(chǎng)的理論[3-4]研究了小世界網(wǎng)絡(luò)和無(wú)標(biāo)度網(wǎng)絡(luò)上的SIS模型,得到這兩種網(wǎng)絡(luò)上疾病傳播的閾值.Bogu?á和Pastor-Satorras等[5]考察了關(guān)聯(lián)網(wǎng)絡(luò)(correlated networks)上SIS模型的傳播閾值.

SIS模型與SIR模型較類似,不同的是在SIS模型中,染病人群一旦被治愈康復(fù)就立刻變成易感人群,從而使得網(wǎng)絡(luò)中存在這樣一種情況,單個(gè)易感個(gè)體可能多次再度被染病節(jié)點(diǎn)所感染[6].

1 基于再度感染的SIS傳播模型

疾病傳播研究的一個(gè)基礎(chǔ)性問題是:一類疾病是在人群中普遍傳播成為流行病,還是逐漸消亡穩(wěn)定為地方病狀態(tài).大量的研究表明,解答此問題的關(guān)鍵在于傳播率和康復(fù)率的取值大小,還有個(gè)體之間接觸(連接)的方式(屬性).對(duì)于SIR模型,有關(guān)傳播閾值的研究已經(jīng)很透徹;而對(duì)于SIS模型,關(guān)于傳播閾值的分析還需考慮同一個(gè)節(jié)點(diǎn)多次被感染的情形,這也是本文研究的重點(diǎn).

首先,將SIS和SIR傳播模型的定義更加細(xì)化一點(diǎn):初始時(shí)刻,除了隨機(jī)選取的一個(gè)染病節(jié)點(diǎn)外,網(wǎng)絡(luò)中的其他N-1個(gè)節(jié)點(diǎn)都是易感染類型的.每個(gè)時(shí)間步,感染節(jié)點(diǎn)以概率β將疾病感染給其鄰接節(jié)點(diǎn).節(jié)點(diǎn)一旦被感染后,保持感染狀態(tài)達(dá)τ時(shí)間步之久,之后以概率γ或者變成康復(fù)狀態(tài)(SIR)或者變成易感狀態(tài)(SIS),定義有效傳播率λ=β/γ,不失一般性,可令γ=1.

其次,網(wǎng)絡(luò)中的滲流理論[7-8]指出,網(wǎng)絡(luò)中的邊會(huì)逐漸被移除直到網(wǎng)絡(luò)中剩余節(jié)點(diǎn)個(gè)數(shù)所占初始節(jié)點(diǎn)個(gè)數(shù)的比例為p′時(shí)為止,這時(shí)存在一個(gè)滲流閾值p′c,當(dāng)p′＞p′c時(shí),一個(gè)巨集團(tuán)會(huì)跨越整個(gè)網(wǎng)絡(luò);當(dāng)p′＜p′c時(shí),網(wǎng)絡(luò)由孤立的小集團(tuán)組成.疾病傳播的過程可以看成是滲流過程的相反過程[9],亦即疾病傳播開始于一個(gè)給定的節(jié)點(diǎn),之后不斷以概率在這個(gè)增長(zhǎng)網(wǎng)絡(luò)中添加連邊.這時(shí),疾病在網(wǎng)絡(luò)傳播的關(guān)鍵感染率就等同于滲流過程中出現(xiàn)巨集團(tuán)時(shí)的滲流閾值.為了研究方便,定義一個(gè)節(jié)點(diǎn)感染其鄰接節(jié)點(diǎn)的概率為p,注意這里的p不同于上面提到的β,這是因?yàn)樵讦訒r(shí)間步內(nèi),只要染病節(jié)點(diǎn)還處于感染狀態(tài),它就有可能一直感染其鄰接節(jié)點(diǎn).因而,得到p的數(shù)學(xué)表達(dá)式為[10]

定義n i為染病節(jié)點(diǎn)i所感染節(jié)點(diǎn)的平均數(shù)量,如果n i＞1,那么疾病會(huì)一直傳播下去,直到達(dá)到穩(wěn)定狀態(tài).在SIR模型中,只需考慮子節(jié)點(diǎn)(descendants)被感染的情況;而在SIS模型中,在考慮子節(jié)點(diǎn)被感染的同時(shí),也需考查祖先節(jié)點(diǎn)(ancestors)再次被感染的可能.如圖1所示,節(jié)點(diǎn)b1一旦被感染后,不僅能夠?qū)⒓膊魅窘o它的子節(jié)點(diǎn)c1,c2,…,c k-1,而且可能會(huì)傳染給其祖先節(jié)點(diǎn)i.

圖1 樹狀結(jié)構(gòu)中基于再度感染的傳播示意圖Fig.1 Epidemic spreading based on reinfection in the network that has a tree like sturcture

根據(jù)圖論知識(shí),一個(gè)節(jié)點(diǎn)度為k(入度為1,出度為k-1)的概率為kp(k)/.假設(shè)SIR模型擁有圖1所示的樹狀結(jié)構(gòu),并且忽略環(huán)狀回路[8],那么可以得到節(jié)點(diǎn)i所感染節(jié)點(diǎn)的平均數(shù)量為[11]

根據(jù)式(1)和式(2),由臨界條件n i(SIR)=1,可得傳播閾值為

對(duì)于SIS模型,在計(jì)算n i的過程中還需考慮節(jié)點(diǎn)再次被感染的情況,如圖1所示.但是,節(jié)點(diǎn)b1再度感染其祖先節(jié)點(diǎn)i的概率與感染其子節(jié)點(diǎn)c1,c2,…,c k-1的概率是不一樣的.這是因?yàn)橄鄬?duì)于子節(jié)點(diǎn),節(jié)點(diǎn)i處于易感狀態(tài)的時(shí)間是不同的.兩方面的因素造成了這種結(jié)果:首先,節(jié)點(diǎn)i在感染節(jié)點(diǎn)b1之前必須是處于感染狀態(tài)的,b1也必須在節(jié)點(diǎn)i康復(fù)后再變成易感狀態(tài)才能再次感染節(jié)點(diǎn)i(時(shí)間因素);其次,除了節(jié)點(diǎn)b1,節(jié)點(diǎn)i的其他子節(jié)點(diǎn)b2,…,b k-1也可能在b1之前再次感染節(jié)點(diǎn)i(兄弟節(jié)點(diǎn)因素).

現(xiàn)計(jì)算SIS模型中,節(jié)點(diǎn)b1再次感染節(jié)點(diǎn)i的概率π(簡(jiǎn)稱再度感染率).為了討論方便,只考慮上面提到的第一種因素,忽略第二種因素.假定疾病的感染周期為τ時(shí)間步,節(jié)點(diǎn)i在感染節(jié)點(diǎn)b1之前有s時(shí)間步處于感染狀態(tài),那么節(jié)點(diǎn)i在感染節(jié)點(diǎn)b1之后就有τ-s時(shí)間步處于感染狀態(tài),從而節(jié)點(diǎn)b1就有τ-(τ-s)=s時(shí)間步反過來(lái)再次感染節(jié)點(diǎn)i.根據(jù)上述思想,得到再度感染率為

式中,(1-β)s-1β/(1-(1-β)τ)表示在時(shí)間步s時(shí)刻節(jié)點(diǎn)i感染節(jié)點(diǎn)b1的概率,并假設(shè)節(jié)點(diǎn)b1完全被感染;1-(1-β)s表示節(jié)點(diǎn)b1在s時(shí)間步內(nèi)感染節(jié)點(diǎn)i的概率.

結(jié)合式(2)和式(4),不難得出基于再度感染的SIS模型中節(jié)點(diǎn)i所感染節(jié)點(diǎn)的平均數(shù)量為

根據(jù)式(1)和式(5),由臨界條件n i(SIS)=1,可得傳播閾值為

不難看出,相對(duì)于傳統(tǒng)的SIS模型,基于再度感染的SIS模型中的傳播閾值不僅與網(wǎng)絡(luò)的平均度有關(guān),還與疾病的傳播率β和疾病的感染周期τ有關(guān).

所以,在SIS模型中總的被感染節(jié)點(diǎn)數(shù)量可以表示為

2 算法設(shè)計(jì)

根據(jù)上述理論分析的結(jié)果,設(shè)計(jì)出如下算法:

a.輸入網(wǎng)絡(luò)的鄰接矩陣.鄰接矩陣是一個(gè)對(duì)稱的N階方陣,N表示網(wǎng)絡(luò)中節(jié)點(diǎn)的總個(gè)數(shù).由于鄰接矩陣一般是稀疏矩陣,本文使用sparse函數(shù)壓縮矩陣的存儲(chǔ)空間.

b.設(shè)置傳播過程中的參數(shù).定義傳播率為p,康復(fù)率為γ,疾病的感染周期為τ時(shí)間步,程序運(yùn)行時(shí)間為T.

c.設(shè)定網(wǎng)絡(luò)中節(jié)點(diǎn)的狀態(tài).假設(shè)網(wǎng)絡(luò)中全部節(jié)點(diǎn)的初始狀態(tài)都是易感染的.用一個(gè)N維行向量node_state=1+zeros(1,N)來(lái)表示每個(gè)節(jié)點(diǎn)的狀態(tài).分量值若為1,則表示該節(jié)點(diǎn)為易感狀態(tài);分量值若為2,則表示該節(jié)點(diǎn)為染病狀態(tài).所以,在網(wǎng)絡(luò)中統(tǒng)計(jì)染病節(jié)點(diǎn)密度時(shí)只需統(tǒng)計(jì)分量值為2的節(jié)點(diǎn)個(gè)數(shù)就可以了.

d.采用去尾法,隨機(jī)地從N個(gè)節(jié)點(diǎn)中選取一個(gè)作為染病節(jié)點(diǎn),這個(gè)節(jié)點(diǎn)的狀態(tài)值從1變成2.

e.第1時(shí)間步的節(jié)點(diǎn)傳染模擬.如果node_state(1)≠2,則跳過節(jié)點(diǎn)1,再分析節(jié)點(diǎn)2;如果node_state(1)=2,則節(jié)點(diǎn)1為染病節(jié)點(diǎn),查找鄰接矩陣中第1行值為1的所有元素所在列,即為節(jié)點(diǎn)1的鄰接節(jié)點(diǎn);若鄰接節(jié)點(diǎn)的狀態(tài)為1,則以概率p被感染,否則保持原狀態(tài),同時(shí)將被感染的鄰接節(jié)點(diǎn)狀態(tài)值標(biāo)記為4,其目的是為了避免在該時(shí)間步將疾病傳染給其他易感節(jié)點(diǎn).對(duì)節(jié)點(diǎn)1的所有鄰接節(jié)點(diǎn)重復(fù)上述步驟.對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行上述操作.

f.第1時(shí)間步的節(jié)點(diǎn)康復(fù)模擬.如果node_state(1)≠2,則跳過節(jié)點(diǎn)1再分析節(jié)點(diǎn)2;如果node_state(1)=2,則節(jié)點(diǎn)1以概率γ自動(dòng)康復(fù)并迅速變成易感狀態(tài),同時(shí)將康復(fù)的節(jié)點(diǎn)狀態(tài)標(biāo)記為3.

g.第1時(shí)間步的節(jié)點(diǎn)狀態(tài)重新標(biāo)記.狀態(tài)值若為4則變成2,狀態(tài)值若為3則變成1.

h.重復(fù)步驟e-g,直到τ時(shí)間步.

i.第τ+1時(shí)間步的節(jié)點(diǎn)傳染模擬.從此時(shí)間步開始需考慮再度感染的情況.此時(shí)網(wǎng)絡(luò)中所有易感節(jié)點(diǎn)數(shù)目為:第1時(shí)間步狀態(tài)值為1的感染節(jié)點(diǎn)(此刻已變?yōu)橐赘泄?jié)點(diǎn))個(gè)數(shù)加上第τ時(shí)間步統(tǒng)計(jì)出的易感節(jié)點(diǎn)個(gè)數(shù).前者以概率π被感染,后者以概率p被感染.

j.第τ+1時(shí)間步的節(jié)點(diǎn)康復(fù)模擬.同步驟f.

k.第τ+1時(shí)間步的節(jié)點(diǎn)狀態(tài)重新標(biāo)記.同步驟g.

l.重復(fù)步驟i-k,直到T時(shí)間步,程序運(yùn)行結(jié)束.

3 仿真分析

根據(jù)本文所提算法,使用計(jì)算機(jī)模擬疾病的傳播過程,通過仿真得到的結(jié)果來(lái)分析上述方法的合理性.為了使程序簡(jiǎn)單易懂,使用Matlab7.5編寫基于再度感染的SIS模型的代碼.分別在WS小世界網(wǎng)絡(luò)和BA無(wú)標(biāo)度網(wǎng)絡(luò)上仿真疾病傳播的過程.取網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N=10 000,WS網(wǎng)絡(luò)中平均度=6,BA網(wǎng)絡(luò)中初始參數(shù)m0=m=3,所有的仿真結(jié)果是10次獨(dú)立的網(wǎng)絡(luò)實(shí)現(xiàn)和20次基于再度感染的SIS模型取算術(shù)平均值得到的.

圖2描述了小世界網(wǎng)絡(luò)上感染密度ρ隨著疾病感染周期τ的變化而變化的過程.從上到下3條曲線分別時(shí)在τ=2,6,10是的情形,最下方1條曲線是傳統(tǒng)的SIS模型模擬出的結(jié)果.不難看出,疾病在基于再度感染的SIS模型中傳播所達(dá)到的穩(wěn)態(tài)感染密度要比在傳統(tǒng)的SIS模型中的大,而且感染周期越短,穩(wěn)態(tài)感染密度越大.

圖2 小世界網(wǎng)絡(luò)上感染周期τ對(duì)感染密度p的影響示意圖Fig.2 Relation between stationary infected density p and infection lifetimeτin small world network

圖3反映了無(wú)標(biāo)度網(wǎng)絡(luò)上感染密度ρ隨著疾病感染周期τ的變化而變化的過程.從上到下3條曲線分別是τ=2,6,10時(shí)的情形,最下方1條曲線是傳統(tǒng)的SIS模型模擬出的結(jié)果.從圖3中可知,疾病在基于再度感染的SIS模型中傳播所達(dá)到的穩(wěn)態(tài)感染密度要比在傳統(tǒng)的SIS模型中的大,但是,感染周期對(duì)于穩(wěn)態(tài)感染密度的影響微乎其微,甚至可以忽略.

圖3 無(wú)標(biāo)度網(wǎng)絡(luò)上感染周期τ對(duì)感染密度p的影響示意圖Fig.3 Relation between stationary infected density p and infection lifetimeτin scale-free network

比較圖2和圖3可以得知,相對(duì)于小世界網(wǎng)絡(luò),疾病在無(wú)標(biāo)度網(wǎng)絡(luò)上傳播的速度較快,也就是達(dá)到穩(wěn)態(tài)感染密度所需的時(shí)間較短,這表明疾病更易于在無(wú)標(biāo)度網(wǎng)絡(luò)上傳播.

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

本文提出了復(fù)雜網(wǎng)絡(luò)上一種基于再度感染的SIS模型.相對(duì)于SIR模型,SIS模型的不同點(diǎn)在于,染病人群一旦被治愈康復(fù)后就立刻變成易感人群,從而使得網(wǎng)絡(luò)中存在這樣一種情況:單個(gè)易感個(gè)體可能多次再度被染病節(jié)點(diǎn)所感染.在具有樹狀分支結(jié)構(gòu)的網(wǎng)絡(luò)中運(yùn)用SIS模型,針對(duì)某個(gè)染病節(jié)點(diǎn),在考慮其感染子節(jié)點(diǎn)的同時(shí),也考查其再次感染祖先節(jié)點(diǎn)的情況.分別在小世界網(wǎng)絡(luò)和無(wú)標(biāo)度網(wǎng)絡(luò)上進(jìn)行仿真分析,結(jié)果表明,對(duì)于小世界網(wǎng)絡(luò),基于再度感染的SIS模型的穩(wěn)態(tài)感染密度比傳統(tǒng)的SIS模型的要大,而且感染周期越短,穩(wěn)態(tài)感染密度越大;而對(duì)于無(wú)標(biāo)度網(wǎng)絡(luò),雖然基于再度感染的SIS模型的穩(wěn)態(tài)感染密度也比傳統(tǒng)的SIS模型的要大,但是,感染周期對(duì)于穩(wěn)態(tài)感染密度的影響微乎其微,甚至可以忽略.這是一個(gè)很有趣的現(xiàn)象,值得進(jìn)一步研究.

[1] BAILEY N T J.The Mathematical Theory of Infe-ctious Diseases and Its Applications[M].New York:Hafner Presss,1975.

[2] PASTOR-SATORRASR,VESPIGNANI A.Epidemic dynamics and endemic states in complex networks[J].Physical Review E,2001,63:066117.

[3] PASTOR-SATORRAS R,VESPIGNANI A.Epidemic spreading in scale-free networks[J].Physical Review Letters,2001,86(24):3200-3203.

[4] PASTOR-SATORRASR,VESPIGNANI A.Epidemics and Immunization in Scale-free Networks[M].Berlin:Wiley-VCH,2003.

[5] BOGU?áM,PASTOR-SATORRAS R.Epidemic spreading in correlated complex networks[J].Physical Review E,2002,66:047104.

[6] RONI PARSHANI,SHAI CARMI,SHLOMO HAVLIN.Epidemic threshold for the susceptible-infectio-us-susceptible model on random networks[J].Physical Review Letters,2010,104(25):258701.

[7] CALLAWAY DS,NEWMAN M E J,STROGATZ S H,et al.Network robustness and fragility:Percolati-on on random graphs[J].Physical Review Letters,2000,85(24):5468-5471.

[8] COHEN R,EREZ K,HAVLIN S,et al.Resilience of the internet to random breakdowns[J].Physical Review Letters,2000,85(24):4626-4628.

[9] ALEXANDROWICZ Z.Critically branched chains and percolationclusters[J].Physics Letters A,1980,80(4):284-286.

[10] NEWMAN M E J.Spread of epidemic disease on networks[J].Physical Review E,2002,66:016128.

[11] MADAR N,KALISKY T,COHEN R,et al.Immunization and epidemic dynamics in complex networks[J].European Physical Journal,2004,38(2):269-276.

SIS model based on reinfection

ZHUXiao-jun, ZHANGNing(Business School,University of Shanghai for Science and Technology,Shanghai 200093,China)

A new SIS model based on reinfection in complex networks was proposed.By using the model in the network with a tree-like sturcture,not only the infection of descendants of an infected node was considered but also the reinfection of ancestor by the infected node was taken into account.Through theoretical analysis and numerical simulation on small-world networks and scalefree networks,it is found that:for small-world networks,the stationary infected density on this new model is larger than that on the traditional SISmodel,and the shorter the infection time is,the gerater the stationary infected density will be;however for the scale-free networks,the stationary infected density on this new model is still larger than that on the traditional SISmodel,yet the effect of the infection time on the stationary infected density can be neglected.

complex network;epidemic spreading;reinfection;ancestor nodes

TP 309.5

A

1007-6735(2011)04-0367-05

2011-03-01

國(guó)家自然科學(xué)基金資助項(xiàng)目(70971089);上海市重點(diǎn)學(xué)科建設(shè)資助項(xiàng)目(S30501)

朱曉軍(1984-),男,碩士研究生.研究方向:復(fù)雜網(wǎng)絡(luò).E-mail:xifengpo126@126.com張 寧(聯(lián)系人),女,教授.研究方向:復(fù)雜網(wǎng)絡(luò).E-mail:zhangning@usst.edn.cn