網絡傳播動力學模擬方法評述

王 偉，舒盼盼，唐 明，高 輝

?

網絡傳播動力學模擬方法評述

王 偉，舒盼盼，唐 明，高 輝

(電子科技大學互聯網科學中心 成都 611731)

借助計算機實驗模擬方法是預警和控制流行病傳播的一個重要研究手段。該文以SIS和SIR兩種經典傳播模型為例，詳細地介紹了利用同步更新方法和異步更新方法模擬流行病的傳播過程，并比較了兩種模擬方法的時空復雜度、聯系及差異性。理清兩種不同的計算機模擬方法不僅有助于加深對傳播動力學的認識，還有助于提出和發展新的理論框架。

異步更新; 復雜網絡; 流行病傳; 播同步更新

14世紀的黑死病到SARS、H1N1，以及最近的埃博拉病毒(Ebola)，流行病的傳播時刻威脅著人類的生命安全，同時也給社會發展帶來了巨大的經濟損失[1-4]。一直以來，來至各個領域的專家和學者都致力于研究流行病傳播機制、預警和防控[5-8]。其中，及時準確地預警流行病傳播是控制流行病大規模爆發的關鍵。針對流行病的特有傳播途徑、傳播速率、潛伏期和行為響應等性質建立恰當的傳播模型是預警流行病傳播的第一步。如易感態-感染態(SI)模型可以描述艾滋病和埃博拉病毒這類爆發突然且尚缺有效治療手段的流行病，易感態-感染態-恢復態(SIR)模型用以描述水痘和麻疹這類患者能完全康復并獲得終身免疫力的流行病，易感態-感染態-易感態(SIS)模型則可以描述感冒和淋病這類康復患者可能再次被感染的傳染病[9]。[10-12]。[12-15]。

在現代流行傳播研究中，大多數學者采用理論分析和計算機模擬相結合的方法揭示流行病傳播機制、預警及其控制。他們從網絡的宏觀結構(如網絡結構異質性)[10-12,17-20]、(如社區結構)[21-23](如節點度、邊權大小)[24-27]出發分析不同結構特性對流行病傳播速度[24,28]、傳播可預測性[29-30]、傳播范圍[17,25]和爆發閾值[31-34][35-39]，進一步還原流行病傳播路徑，尋找流行病傳播源[40-41][42]發現全球流行病傳播到達時間并不是取決于兩地的實際距離，而關鍵在于兩地之間的有效距離長度。在流行病的控制研究中，學者們從網絡的全局和局域結構出發設計有效的流行病免疫策略[43]。[44]，[45][46-48]

[10]。這些基本假設將直接導致理論預測與實際傳播過程之間存在一定的差異，甚至得到截然不同的結論。面對錯綜復雜的流行病傳播過程，這些基本假設極大地制約了理論方法的廣泛運用。因此，經典的理論方法很難描述真實的流行病傳播，進而阻礙了人們對真實流行病傳播的認識。幸運的是，計算機模擬方法很大程度上能夠彌補理論分析過程中的這些不足。一方面，在利用計算機模擬流行病傳播時無需做出多余的假設，從而保證了流行病傳播過程的準確性；另一方面，計算機模擬可以更適用于結構復雜、規模龐大的社會系統，并能夠綜合考慮實際社會因素對流行病傳播的影響。正是由于這些優點，計算機模擬方法已成為研究流行病傳播不可替代的手段。

(synchronous updating method)和異步更新(asynchronous updating method)是動力學研究中兩種最為常用的計算機模擬方法。然而，對于同一動力學過程，這兩種模擬方法在更新節點狀態時的差異性可能會導致動力學過程在定量和定性上的差異[49-51]。[52]發現運用同步方法來更新元胞自動機囚徒困境博弈模型會導致網格中的合作與背叛交替出現，但采用異步更新方法則不會出現合作個體?，F有研究中，已有許多文獻致力于介紹如何利用各種理論方法來分析流行病傳播動力學[16,53-55]，對于計算機模擬流行病傳播過程卻甚少提及，使得人們對如何準確地模擬流行病傳播缺乏必要的認識和理解。鑒于此，本文將首先基于SIS和SIR傳播模型詳細介紹同步更新方法和異步更新方法的具體實現步驟，繼而討論兩種更新方法對流行病傳播動力學的影響，并對兩種方法之間的區別與聯系進行分析。最后，對本文進行總結和展望。

1 計算機模擬方法

[50]。SIS和SIR流行病傳播模型為例來詳細闡述同步更新和異步更新方法在流行病傳播模型中的應用。

對于SIS流行病傳播模型，節點在每個時刻只能處于易感態(S)或感染態(I)。易感態節點表示未被流行病感染的個體，且可能被感染；感染態節點表示已經被流行病感染且具有傳播能力。每一時間步內，每個感染態節點以概率嘗試感染它的所有易感態鄰居節點，然后以概率恢復成易感態。

對于SIR流行病傳播模型，任意時刻節點只能處于易感態(S)或感染態(I)或恢復態(R)。易感態節點表示未被流行病感染的個體，且可能被感染；感染態節點表示已經被流行病感染且具有傳播能力；恢復態節點則表示曾感染流行病且完全康復。與SIS模型類似，每一時間步內，每個感染態節點以概率嘗試感染它的鄰居易感態節點，并以概率變為恢復態。

1.1 同步更新方法

同步更新方法主要思想是：每個節點根據它們自己及其鄰居節點的上一步狀態來更新自己的當前狀態，所有節點的狀態更新過程都在單位時間內同時完成[10-12]。對于SIS流行病傳播，初始時刻隨機選擇或按照某種策略選擇比例的節點作為感染態節點，其余節點都處于易感態。用隊列存放當前步具有感染能力的節點(即上一時間步的未恢復感染節點及其感染節點)，隊列存放當前步新感染的節點。首先，將初始時刻感染的所有節點存放在隊列中。接下來，每一時間步的傳播過程按以下步驟進行：

1) 遍歷隊列中的感染態節點，每個感染態節點以概率嘗試感染它的所有易感態鄰居節點。若成功感染它的易感態鄰居，則將新感染的易感態節點存放到隊列中；

SIR傳播模型同步更新方法與SIS完全類似，更新過程終止的條件是系統中不再有感染態節點。

1.2 異步更新方法

在異步更新方法的實現過程中，節點獨立地更新其狀態，并且它的鄰居節點在其更新狀態時能觀察到它的新狀態[53]。異步更新方法廣泛地運用于各種動力學模擬，包括投票模型、博弈、閾值模型和傳播模型等。Gillespie算法是異步更新方法中典型的代表方法，模擬了生物化學中的有效反應過程，以及馬爾科夫動力學過程和泊松過程[56-58]。在實現Gillespie算法的過程中，最為重要的就是如何給每個時間步賦予發生過程和時間更新步長。假設系統中有個獨立的隨機離散過程，每個過程發生的概率為，。對于泊松過程，在時刻發生事件的概率為：

有很強的普適性和實用性，它不僅僅可以用于模擬反應過程，還適用于非平衡動力學的模擬[59]。

本文以經典的SIS傳播動力學為例，具體介紹Gillespie算法。首先，指定隊列和隊列。隊列用于存放所有感染態節點，隊列用于存放活躍邊?；钴S邊是指感染態節點與易感態節點相連的邊。然后，在每一時刻按照以下步驟模擬SIS傳播過程。

SIR模型的異步更新方法也是類似地進行，模擬結束條件是網絡中不再有感染態節點。

1.3 參數設置

對于SIS模型，同步更新方法和異步更新方法都涉及到時間參數，的設置直接影響最終的傳播結果。這是因為，SIS傳播模型存在一個臨界傳播概率。當傳播率時，感染態節點隨時間呈指數快速衰減，系統處于吸收態；當傳播概率時，系統中將一直存在感染態的節點，系統處于活躍態。然而，網絡的淬火無序結構會導致在臨界點附近感染范圍呈廣延指數或冪律衰減形式，即系統中將長時間存在感染態節點[61-65]。若設置太小，系統仍然處于弛豫態；若設置過大，系統更容易進入吸收態，導致只有少許模擬過程處于活躍態[66]。因此，在實現SIS傳播過程，設置時間至關重要。根據不同的研究需要，將最大時間設置為~不等(具體設置與和相關)在流行病傳播動力學中，國內外學者在設置采取了不同的方法如，設置1 000[67]，或設置[64]。

在計算網絡中穩態感染節點平均比例只統計那些存活的模擬過程[59]，即系統沒有到達吸收態。隨著時間增加，系統處于活躍的概率也就越小，意味著需要更多的模擬實驗實現次數。尤其在臨界點附近，系統處于活躍的概率更小。如何防止系統頻繁地陷入吸收態，只用少量的實驗模擬便能得到比較準確的穩態值呢？這一難題在亞穩態方法(quasistationary state)中[60,68]得到了很好的解決。亞穩態方法的主要思想是讓系統一直處于活躍態，利用它曾經經歷的狀態替換當前狀態。值得注意的是，更新節點狀態時既可以運用同步更新方法也可以運用異步更新方法。在實現過程中需要用隊列保存個活躍的演化過程。在某一個時間步，若系統轉變為吸收態，則從隊列中隨機選擇一個活躍過程替換當前過程。此外，還需要以概率更新隊列中的過程。經歷弛豫時間后，在個時間步內求均值得到系統中有個感染態節點的概率。進一

文獻[69-72]在模擬過程中不允許網絡中最后一個感染態節點恢復來防止系統進入吸收態。這種簡單的處理雖然改變了SIS傳播模型，但是對系統的穩態密度影響很小[70]。利用這種簡單的模擬方法，對SIS傳播[71-72]、非馬爾科夫流行病傳播[69-70]都做了系統的研究，最近，又發現這種模擬方法改變了兩個互斥SIS傳播動力學過程(即某一時刻節點只能被兩個流行病中的一個感染)：基于單個網絡的兩個互斥SIS傳播模型中，該模擬方法會使得兩個動力學交替占主導地位[73]，而傳統模擬方法導致穩態時最多只有一個動力學存活[74-75]。由此可見，選擇合適的模擬方法對流行病傳播動力學的分析至關重要。

2 兩種更新方法之間的聯系與區別

在計算機模擬過程中，節點狀態更新都是離散時間步驟。在模擬過程中，若每一時間步選擇比例的節點更新其狀態，，同步更新方法和異步更新方法便對應于兩種極端的情形[53,76]。若，即每個時間步更新所有節點的狀態，則與同步更新過程相同。若，即每個時間步平均隨機更新一個節點的狀態，則與異步更新過程相同。

從表1不難看出，同步更新方法的時空復雜度都比異步更新方法更低。同步更新方法的優勢在于能快速模擬動力學過程(即每個時間步同時改變所有節點狀態)，且易于編寫程序；異步更新方法需要逐個更新系統中節點的狀態(即每個時間步只有一個節點改變其狀態)，程序實現較復雜。對現有文獻進行不完全統計，發現若研究只關注于穩態時的感染密度，往往選擇快速、簡單的同步更新方法；若研究關注于動力學演化過程(如局域現象)，往往選擇系統狀態改變緩慢的異步更新方法更為合適[16]。

表1 單位時間步內，同步更新和異步更新方法的時空復雜度

本文利用前面所介紹的同步更新和異步更新方法來模擬SIS和SIR流行病傳播模型，進一步分析這兩種方法對傳播所帶來的影響。在圖1和圖2中，在平均度的ER網絡中運用兩種方法模擬SIS和SIR傳播，其中，恢復概率為1。發現兩種模擬方法在更新節點狀態時的微妙差異導致傳播動力學在定性和定量上都有很大的差異。當較小時，感染密度也較小。對于同步更新，每一時間步，所有感染態節點嘗試感染其所有易感態鄰居后才可能會恢復；而對于異步更新，活躍邊發生感染和感染態節點恢復這兩種事件是按某種概率隨機出現的。這種不同導致異步更新情況下會有部分感染態節點還未嘗試感染易感態鄰居之前就已恢復，而同步更新情況下將產生更多的新感染態節點，因此具有較小的爆發閾值。當較大時，感染密度較大。對于同步更新而言，因的限制，SIS模型的感染密度會逐漸趨于0.5的上限[10]。然而對于異步更新，感染態節點的增加會產生更多的活躍邊，因而感染事件具有更大的發生概率而更可能先發生，導致新感染態節點的逐漸增加。相比于SIS模型，SIR的感染態節點恢復不會減少最終的感染規模，也不能限制同步更新中感染先發生的優勢，從而具有更大的最終爆發規模。由此可見，兩種模擬方法對流行病的爆發閾值和最終感染密度所帶來的定量影響也是不容忽視的，尤其是在發展和提出新理論方法的過程中需慎重考慮模擬方法所帶來的影響。

3 結 束 語

針對不同的流行病傳播模型，設計出快速、準確的模擬方法對揭示傳播機制，以及預警和控制起著不可替代的作用。本文以SIS和SIR流行病傳播動力學為例，詳細地介紹如何運用同步更新和異步更新兩種常用方法來進行計算機模擬，分析了兩種模擬方法的時空復雜度，并闡述了兩種模擬方法之間的聯系與區別，舉例討論了它們對流行病傳播范圍和爆發閾值的影響。理清同步更新方法和異步更新方法不僅僅能加深對動力學本身的認識，還有助于提出和發展一些更加準確的理論分析方法。此外，可以將兩種更新方法可以推廣到其他流行病傳播模型(如SI，SEIR模型等)，以及其他動力學模型(如閾值模型，投票模型，博弈等)的實驗模擬。

兩種方法在模擬過程中的細微差異對流行病最終傳播范圍和爆發閾值會造成定量上的影響。更值得深思的問題是，對于同一流行病傳播模型，不同的模擬方法是否會對臨界值、臨界指數和局域現象等一系列問題有定性或者定量的影響？-度關聯、社區等，也包括退火網絡和時序網絡等是否會增加或減小兩種模擬方法定量上的差異？亟待更為系統地探究這兩種模擬方法對動力學過程所帶來的影響，尤其是對非平衡動力學過程所帶來的影響。

本文研究工作得到電子科技大學優秀博士生學術支持計劃(YXBSZC20131065)的資助，在此表示感謝。

[1] MEYERS L A, POURBOHLOUL B, NEWMAN M E J, et al. Networktheory and SARS: Predicting outbreak diversity[J]. J TheorBiol, 2005(232): 71-81.

[2] LEROY E M, ROUQUET P, FORMENTY P, et al. Multiple Ebola virustransmission events and rapid decline of central africanwildlife[J]. Science, 2004(303): 387-390.

[3] MILLER J C, DANON L, O’HAGAN J J, et al. Student behavior during a school closure caused by pandemic influenza A/H1N1[J]. PLoS ONE, 2010(5): e10425.

[4] 馬知恩, 周義倉, 王穩地, 等. 傳染病動力學的數學建模與研究[M]. 北京: 科學出版社, 2004.

MA Zhi-en, ZHOU Yi-chang, WANG Wen-di, et al. Mathematical modeling and study of infectious diseasedynamics[M]. Beijing: Science Press, 2004.

[5] KEELING M, ROHANI P. Modeling infectious diseases in humans and animals[M]. Princeton: Princeton University Press, 2007.

[6] ANDERSON R M, MAY R M. Infectious diseases in humans[M]. Oxford: Oxford University Press, 1992.

[7] ANDERSSON H, BRITTON T. Stochastic epidemic models and theirstatistical analysis, lecture notes in statistics[M]. New York: Springer, 2000.

[8] KEELING M, POHANI P. Modeling infectious diseases in humansand animals[M]. Princeton: Princetion University Press, 2007.

[9] KERMACK W O, MCKENDRICK A G. A contribution to the math-ematical theory of epidemics[J]. Proc R SocLond A, 1927(115): 700-721.

[10] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic spreading in scale-Free networks[J]. Phys Rev Lett, 2001(86): 3200-3203.

[11] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic dynamics in finite size scale-free networks[J]. Phys Rev E, 2002(65): 035108(R).

[12] PASTOR-SATORRAS R, VESPIGNANI A. Epidemic dynamics and endemic states in complex networks[J]. Phys Rev E, 2001(63): 066117.

[13] 周濤, 傅忠謙, 牛永偉, 等. 復雜網絡上傳播動力學研究綜述[J]. 自然科學進展, 2005, 15(5): 513-517.

ZHOU Tao, FU Zhong-qian, NIU Yong-wei, et al. Summary of research on propagation dynamics on complex networks[J]. Progress in Natural Science, 2005, 15(5): 513-517.

[14] 李翔, 劉宗華, 汪秉宏. 網絡傳播動力學[J]. 復雜系統與復雜性科學

LI Xiang, LIU Zong-hua, WANG Bing-hong. On spreading dynamics on networks[J]. Complex Systems and Complexity Science, 2010, 7(2): 33-37.

[15] WANG L, LI X. Spatial epidemiology of networked metapopulation: an overview[J]. Chin Sci Bull, 2014, 59(28): 3511-3522.

[16] PASTOR-SATORRAS R, CASTELLANO C, MIEGHEM P V, et al.[J]. Rev Mod Phys, 2015(87): 925-979.

[17] NEWMAN M E J. The spread of epidemic disease on networks[J]. Phys Rev E, 2002(66): 016128.

[18] YANG Z, ZHOU T. Epidemic spreading in weighted networks: an edge-based mean-field solution[J]. Phys Rev E, 2012(85): 056106.

[19] YAN G, ZHOU T, WANG J, et al. Epidemic spread in weightedscale-free networks[J]. Chin PhysLett, 2005(22): 510.

[20] SUN Y, LIU C, ZHANG C X, et al. Epidemic spreading on weighted complex networks[J]. PhysLett A, 2014, 378(7): 635-640.

[21] WANG R S, ALBERT R. Effects of community structure on the dynamics of random threshold networks[J]. Phys Rev E, 2013(87): 012810.

[22] MIN Y, JIN X, GE Y, et al. The role of community mixingstyles in shaping epidemic behaviors in weighted networks[J]. PLOS ONE, 2013, 8(2): e57100.

[23] NEWMAN M E J. Random graphs with clustering[J]. Phys Rev E, 2009(103): 058701.

[24] BARTHELEMY M, BARRAT A, PASTOR-SATORRAS R, et al. Velocity and hierarchical spread of epidemic outbreaks in scale-free networks[J]., 2004(92): 178701.

[25] WANG W, TANG M, ZHANG H F, et al. Epidemic spreading oncomplex networks with general degree and weight distributions[J]. Phys Rev E, 2014(90): 042803.

[26] XU E H W, WANG W, XU C, et al. Suppressed epidemics in multirelationalnetworks[J]. Phys Rev E, 2015(92): 022812.

[27] LI R Q, TANG M, HUI P M. Epidemic spreading on multi-relational networks[J]. ActaPhys Sin, 2013, 62(16): 168903.

[28] CUI A X, WANG W, TANG M, et al. Efficient allocation of heterogeneous response times in information spreading process[J]. Chaos, 2014(24): 033113.

[29] SHU P, TANG M, GONG K, et al. Effects of weak ties on epidemicpredictability on community networks[J]. Chaos, 2012, 22(4): 043124.

[30] ZHAO Z D, LIU Y, TANG M. Epidemic variability in hierarchicalgeographical networks with human activity patterns [J]. Chaos, 2012, 22(2): 023150.

[31] BOGUNA M, PASTOR-SATORRAS R, VESPIGNANI A. Absence of epidemic threshold in scale-free networks with degree correlations[J]. Phys Rev E, 2003(90): 028701.

[32] BOGUNA M, CASTELLANO C, PASTOR-SATORRAS R. Nature of theepidemic threshold for the susceptible- infected-susceptible dynamics in networks[J]. Phys Rev Lett, 2013, 111(6): 068701.

[33] CASTELLANO C, PASTOR-SATORRAS R. Thresholds for epidemic spreading in networks[J]. Phys Rev Lett, 2010 (105): 218701.

[34] SHU P, WANG W, TANG M. Numerical identification of epidemic thresholds for susceptible-infected-recovered model on finite-size networks[J]. Chaos, 2015(25): 063104.

[35] KITSAK M, GALLOS L K, HAVLIN S, et al. Identification of influential spreaders in complex networks[J]. Nat Phys, 2010(6): 888-893.

[36] LIU Y, TANG M, ZHOU T, et al. Core-like groups resulting in invalidation of k-shell decomposition analysis[EB/OL]. (2014-09-18). http://arXiv.org/abs/1409. 5187.

[37] CHEN D B, LU L Y, SHANG M S, et al. Identifying influentialnodes in complex networks[J]. Physica A, 2002, (391): 1777-1787.

[38] LIU J G., REN Z M, GUO Q. Ranking the spreading influence incomplex networks[J]. Physica A, 2013(392): 4154-4159.

[39] PEI S, MAKSE H A. Spreading dynamics in complexnetworks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2013(13): P12002.

[40] PINTO P C, THIRAN P, VETTERLI M. Locating the sourceof diffusion in large-scale networks[J]. Phys Rev Lett, 2012,109(6): 068702.

[41] CHEN D B, XIAO R, ZENG A. Predicting the evolution of spreading oncomplex networks[J]. Sci Rep, 2014(4): 6108.

[42] BROCKMANN D, HELBING D. The hidden geometry of complex, network-driven contagion phenomena[J]. Science, 2013(342): 1337-1442.

[43] 王偉, 楊慧, 龔凱, 等. 復雜網絡上的局域免疫研究[J]. 電子科技大學學報，2013, 42(6): 817-830.

WANG Wei, YANG Hui, GONG Kai, et al. Local immunization algorithm on complex networks[J]. Journal of University of Electronic Science and Technology of China, 2013, 42(6): 817-830.

[44] PASTOR-SATORRAS R, VESPIGNANI A. Immunization of complex networks[J]. Phys Rev E, 2002(65): 036104.

[45] COHEN R, HAVLIN S, BEN-AVRAHAM D. Efficient immunization strategies for computer networks and populations[J]. Phys Rev Lett, 2003, 91(24): 247901.

[46] YANG H, TANG M, ZHANG H F. Efficient community-basedcontrol strategies in adaptive networks[J]. New J Phys, 2012(14): 123017.

[47] LIU H K, YANG H, TANG M, et al. Local transient-based quarantine strategy in adaptive networks[J]. Scientia Sinica Physica, Mechanica&Astronomica, 2013, 43(2): 1-10.

[48] WANG W, TANG M, YANG H, et al. Asymmetrically interactingspreading dynamics on complex layered networks[J]. Sci Rep, 2014(4): 5097.

[49] WU Z X, RONG Z. Boosting cooperation by involving extortion in spatial Prisoner’s dilemma[J]. Phys Rev E, 2014(90): 062102.

[50] SCHONFISCH B, DE ROOS A. Synchronous and asynchronous updating in cellular automata[J]. BioSystems, 1999(51): 123-143.

[51] WOLFRAM S. Statistical mechanics of cellular automata[M]. Rev Mod Phys, 1983(55): 601-644.

[52] HUBERMAN B A, GLANCE N S. Evolutionary games and computer simulations[J]. Proc Natl Acad Sci USA, 1993(90): 7716-7781.

[53] PORTER MA, GLEESON J P. Dynamical systems on networks: atutoria[EB/OL]. (2014-03-29). http://arXiv.org/ abs/1403.7663.

[54] VOLZ E M, MILLER J C, GALVANI A, et al. Effects of heterogeneousand clustered contact patterns on infectious disease dynamics[J]. PloS Comput Biol, 2013(7): e1002042.

[55] FU X C, SMALL M, CHEN G R. Propagation dynamics on complex networks: Models, methods and stability analysis[M]. BeiJing: High Education Press, 2014.

[56] GILLESPIE D. A general method for numerically simulating the stochastic time evolution of coupled chemical reactions[J]. Journal of Computational Physics, 1976(22): 403G.

[57] GILLESPIE D. Exact stochastic simulation of coupled chemicalreactions[J]. Journal of Physical Chemistry, 1977(81): 2340-2361.

[58] GILLESPIE D. Approximate accelerated stochastic simulation ofchemically reacting systems[J]. Journal of Chemical Physics, 2001(115): 1716-1733.

[59] MARRO J, DICKMAN R. Nonequilibrium phase transition in latticemodels[M]. London: Cambridge University Press, 1999.

[60] FERREIRA S C, CASTELLANO C, PASTOR- SATORRAS R. Epidemic thresholds of the susceptible- infected-susceptible model on networks: a comparison of numerical and theoretical results[M]. Phys Rev E, 2012(86): 041125.

[61] GOLTSEV A V, DOROGOVTSEV S N, OLIVEIRA J G, et al. Localizationand spreading of diseases in complex networks[J]. Phys Rev Lett, 2012(109): 128702.

[62] VOJTA T. Rare region effects at classical, quantum and nonequilibrium phase transitions[J]. J Phys A Math Gen, 2006(39): 143-205.

[63]ODOR G. Spectral analysis and slow spreading dynamics oncomplex networks[J]. Phys Rev E, 2013, 88(3): 032109.

[64] MUNOZ M A, JUHASZ R,C, et al. Griffiths phases oncomplex networks[J]. Phys Rev Lett, 2010, 105(12): 128701.

[65] MORETTI P, A. MUNOZ M. Brain architecture, griffiths phases,and the stretching of criticality[J]. Nat Commu, 2013(4): 2521.

[66] FERREIRA R S, FERREIRA S C. Critical behavior of the contact process on small-world networks[J]. EurPhys J B, 2013(86): 462.

[67] WU Q, FU X, SMALL M, et al. The impact of awareness on epidemic spreading in networks[J]. Chaos, 2012(22): 013101.

[68] DE OLIVEIRA M M, DICKMAN R. How to simulate the quasistationary state[J]. Phys Rev E, 2005(71): 016129.

[69] MIEGHEM P V, DE BOVENKAMP R.[J]. Phys Rev Let-t, 2013(110): 108701.

[70] CATOR E, DE BOVENKAMP R, MIEGHEM P V. Susceptible-infected-susceptible epidemics on networks with general infection andcure times[J]. Phys Rev E, 2013(87): 062816.

[71] CATOR E, MIEGHEM P V. Susceptible–infected- susceptible epidemics on the complete graph and the star graph: Exact analysis[J]. Phys Rev E, 2013(87): 012811.

[72] LI C, DE BOVENKAMP R, MIEGHEM P V. Susceptible infected-susceptible model: a comparison of N-intertwined and heterogeneous mean-field approximations[J]. Phys Rev E, 2012(86): 026116.

[73] DE BOVENKAMP R, KUIPERS F, MIEGHEM P V. Domination-timedynamics in susceptible-infected- susceptible virus competitionon networks[J]. Phys Rev E, 2014(89): 042818.

[74] WANG Y, XIAO G, LIU J. Dynamics of competing ideas in complex social systems[J]. New J Phys, 2012(14): 013015.

[75] SAHNEH F D, SCOGLIO C. Competitive epidemic spreading overarbitrary multilayer networks[J]. Phys Rev E, 2014(89): 062817.

[76] HARRIS K D, DANFORTH C M, DODDS P S. Dynamical influenceprocesses on networks: General theory and applications to social contagion[J]. Phys Rev E, 2013(88): 022816.

編 輯 蔣 曉

WANG Wei, SHU Pan-pan, TANG Ming, and GAO Hui

(Web Science Center, University of Electronic Science and Technology of China Chengdu 611731)

Computer simulating method is an important analytical tool to predict and control epidemic spreading dynamics. In this recitation, taking the classical susceptible-infected-susceptible (SIS) and susceptible- infected-removed (SIR) spreading dynamics as two specific examples, we describe in detail the simulation processes of synchronous and asynchronous updating methods to simulate epidemic spreading. In addition, the time and space complexity of the two kinds of updating methods are also compared, and the correlations and differences between them are investigated. Clarifying the different simulated methods can not only help to understand the spreading dynamics but promote further development of theoretical methods.

asynchronous updating method; complex networks; spreading dynamics; synchronous updating method

O231. 5; N945.12; N94

A

10.3969/j.issn.1001-0548.2016.03.022

2015 - 02 - 04；

2015 - 05 - 09

國家自然科學基金(11105025,91324002)

王偉(1988 - )，男，博士生，主要從事復雜網絡傳播動力學方面的研究.