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

朱曉軍, 張 寧

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

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

朱曉軍, 張 寧

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

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

復雜網絡;疾病傳播;再度感染;祖先節點

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

近年來,科研工作者已經研究了許多種模型,從數學形式上描述疾病傳播的過程,與此同時,各種免疫策略也相繼被提出來應對不同的疾病傳播.Pastor-Satorras和Vespignani等用平均場的理論[3-4]研究了小世界網絡和無標度網絡上的SIS模型,得到這兩種網絡上疾病傳播的閾值.Bogu?á和Pastor-Satorras等[5]考察了關聯網絡(correlated networks)上SIS模型的傳播閾值.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

不難看出,相對于傳統的SIS模型,基于再度感染的SIS模型中的傳播閾值不僅與網絡的平均度有關,還與疾病的傳播率β和疾病的感染周期τ有關.

所以,在SIS模型中總的被感染節點數量可以表示為

2 算法設計

根據上述理論分析的結果,設計出如下算法:

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

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

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

d.采用去尾法,隨機地從N個節點中選取一個作為染病節點,這個節點的狀態值從1變成2.

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

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

g.第1時間步的節點狀態重新標記.狀態值若為4則變成2,狀態值若為3則變成1.

h.重復步驟e-g,直到τ時間步.

i.第τ+1時間步的節點傳染模擬.從此時間步開始需考慮再度感染的情況.此時網絡中所有易感節點數目為:第1時間步狀態值為1的感染節點(此刻已變為易感節點)個數加上第τ時間步統計出的易感節點個數.前者以概率π被感染,后者以概率p被感染.

j.第τ+1時間步的節點康復模擬.同步驟f.

k.第τ+1時間步的節點狀態重新標記.同步驟g.

l.重復步驟i-k,直到T時間步,程序運行結束.

3 仿真分析

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

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

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

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

圖3 無標度網絡上感染周期τ對感染密度p的影響示意圖Fig.3 Relation between stationary infected density p and infection lifetimeτin scale-free network

比較圖2和圖3可以得知,相對于小世界網絡,疾病在無標度網絡上傳播的速度較快,也就是達到穩態感染密度所需的時間較短,這表明疾病更易于在無標度網絡上傳播.

4 結束語

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

[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

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

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