朱曉軍, 張 寧

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

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

朱曉軍, 張 寧

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

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

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

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

近年來,科研工作者已經(jīng)研究了許多種模型,從數(shù)學(xué)形式上描述疾病傳播的過程,與此同時,各種免疫策略也相繼被提出來應(yīng)對不同的疾病傳播.Pastor-Satorras和Vespignani等用平均場的理論[3-4]研究了小世界網(wǎng)絡(luò)和無標(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ò)中存在這樣一種情況,單個易感個體可能多次再度被染病節(jié)點所感染[6].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 算法設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真分析

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

圖2描述了小世界網(wǎng)絡(luò)上感染密度ρ隨著疾病感染周期τ的變化而變化的過程.從上到下3條曲線分別時在τ=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ò)上感染周期τ對感染密度p的影響示意圖Fig.2 Relation between stationary infected density p and infection lifetimeτin small world network

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

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

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

4 結(jié)束語

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

國家自然科學(xué)基金資助項目(70971089);上海市重點學(xué)科建設(shè)資助項目(S30501)

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