網(wǎng)絡(luò)傳播動(dòng)力學(xué)模擬方法評(píng)述

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

?

網(wǎng)絡(luò)傳播動(dòng)力學(xué)模擬方法評(píng)述

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

(電子科技大學(xué)互聯(lián)網(wǎng)科學(xué)中心 成都 611731)

借助計(jì)算機(jī)實(shí)驗(yàn)?zāi)M方法是預(yù)警和控制流行病傳播的一個(gè)重要研究手段。該文以SIS和SIR兩種經(jīng)典傳播模型為例，詳細(xì)地介紹了利用同步更新方法和異步更新方法模擬流行病的傳播過程，并比較了兩種模擬方法的時(shí)空復(fù)雜度、聯(lián)系及差異性。理清兩種不同的計(jì)算機(jī)模擬方法不僅有助于加深對(duì)傳播動(dòng)力學(xué)的認(rèn)識(shí)，還有助于提出和發(fā)展新的理論框架。

異步更新; 復(fù)雜網(wǎng)絡(luò); 流行病傳; 播同步更新

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

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

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

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

1 計(jì)算機(jī)模擬方法

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

對(duì)于SIS流行病傳播模型，節(jié)點(diǎn)在每個(gè)時(shí)刻只能處于易感態(tài)(S)或感染態(tài)(I)。易感態(tài)節(jié)點(diǎn)表示未被流行病感染的個(gè)體，且可能被感染；感染態(tài)節(jié)點(diǎn)表示已經(jīng)被流行病感染且具有傳播能力。每一時(shí)間步內(nèi)，每個(gè)感染態(tài)節(jié)點(diǎn)以概率嘗試感染它的所有易感態(tài)鄰居節(jié)點(diǎn)，然后以概率恢復(fù)成易感態(tài)。

對(duì)于SIR流行病傳播模型，任意時(shí)刻節(jié)點(diǎn)只能處于易感態(tài)(S)或感染態(tài)(I)或恢復(fù)態(tài)(R)。易感態(tài)節(jié)點(diǎn)表示未被流行病感染的個(gè)體，且可能被感染；感染態(tài)節(jié)點(diǎn)表示已經(jīng)被流行病感染且具有傳播能力；恢復(fù)態(tài)節(jié)點(diǎn)則表示曾感染流行病且完全康復(fù)。與SIS模型類似，每一時(shí)間步內(nèi)，每個(gè)感染態(tài)節(jié)點(diǎn)以概率嘗試感染它的鄰居易感態(tài)節(jié)點(diǎn)，并以概率變?yōu)榛謴?fù)態(tài)。

1.1 同步更新方法

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

1) 遍歷隊(duì)列中的感染態(tài)節(jié)點(diǎn)，每個(gè)感染態(tài)節(jié)點(diǎn)以概率嘗試感染它的所有易感態(tài)鄰居節(jié)點(diǎn)。若成功感染它的易感態(tài)鄰居，則將新感染的易感態(tài)節(jié)點(diǎn)存放到隊(duì)列中；

SIR傳播模型同步更新方法與SIS完全類似，更新過程終止的條件是系統(tǒng)中不再有感染態(tài)節(jié)點(diǎn)。

1.2 異步更新方法

在異步更新方法的實(shí)現(xiàn)過程中，節(jié)點(diǎn)獨(dú)立地更新其狀態(tài)，并且它的鄰居節(jié)點(diǎn)在其更新狀態(tài)時(shí)能觀察到它的新狀態(tài)[53]。異步更新方法廣泛地運(yùn)用于各種動(dòng)力學(xué)模擬，包括投票模型、博弈、閾值模型和傳播模型等。Gillespie算法是異步更新方法中典型的代表方法，模擬了生物化學(xué)中的有效反應(yīng)過程，以及馬爾科夫動(dòng)力學(xué)過程和泊松過程[56-58]。在實(shí)現(xiàn)Gillespie算法的過程中，最為重要的就是如何給每個(gè)時(shí)間步賦予發(fā)生過程和時(shí)間更新步長(zhǎng)。假設(shè)系統(tǒng)中有個(gè)獨(dú)立的隨機(jī)離散過程，每個(gè)過程發(fā)生的概率為，。對(duì)于泊松過程，在時(shí)刻發(fā)生事件的概率為：

有很強(qiáng)的普適性和實(shí)用性，它不僅僅可以用于模擬反應(yīng)過程，還適用于非平衡動(dòng)力學(xué)的模擬[59]。

本文以經(jīng)典的SIS傳播動(dòng)力學(xué)為例，具體介紹Gillespie算法。首先，指定隊(duì)列和隊(duì)列。隊(duì)列用于存放所有感染態(tài)節(jié)點(diǎn)，隊(duì)列用于存放活躍邊?；钴S邊是指感染態(tài)節(jié)點(diǎn)與易感態(tài)節(jié)點(diǎn)相連的邊。然后，在每一時(shí)刻按照以下步驟模擬SIS傳播過程。

SIR模型的異步更新方法也是類似地進(jìn)行，模擬結(jié)束條件是網(wǎng)絡(luò)中不再有感染態(tài)節(jié)點(diǎn)。

1.3 參數(shù)設(shè)置

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

在計(jì)算網(wǎng)絡(luò)中穩(wěn)態(tài)感染節(jié)點(diǎn)平均比例只統(tǒng)計(jì)那些存活的模擬過程[59]，即系統(tǒng)沒有到達(dá)吸收態(tài)。隨著時(shí)間增加，系統(tǒng)處于活躍的概率也就越小，意味著需要更多的模擬實(shí)驗(yàn)實(shí)現(xiàn)次數(shù)。尤其在臨界點(diǎn)附近，系統(tǒng)處于活躍的概率更小。如何防止系統(tǒng)頻繁地陷入吸收態(tài)，只用少量的實(shí)驗(yàn)?zāi)M便能得到比較準(zhǔn)確的穩(wěn)態(tài)值呢？這一難題在亞穩(wěn)態(tài)方法(quasistationary state)中[60,68]得到了很好的解決。亞穩(wěn)態(tài)方法的主要思想是讓系統(tǒng)一直處于活躍態(tài)，利用它曾經(jīng)經(jīng)歷的狀態(tài)替換當(dāng)前狀態(tài)。值得注意的是，更新節(jié)點(diǎn)狀態(tài)時(shí)既可以運(yùn)用同步更新方法也可以運(yùn)用異步更新方法。在實(shí)現(xiàn)過程中需要用隊(duì)列保存?zhèn)€活躍的演化過程。在某一個(gè)時(shí)間步，若系統(tǒng)轉(zhuǎn)變?yōu)槲諔B(tài)，則從隊(duì)列中隨機(jī)選擇一個(gè)活躍過程替換當(dāng)前過程。此外，還需要以概率更新隊(duì)列中的過程。經(jīng)歷弛豫時(shí)間后，在個(gè)時(shí)間步內(nèi)求均值得到系統(tǒng)中有個(gè)感染態(tài)節(jié)點(diǎn)的概率。進(jìn)一

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

2 兩種更新方法之間的聯(lián)系與區(qū)別

在計(jì)算機(jī)模擬過程中，節(jié)點(diǎn)狀態(tài)更新都是離散時(shí)間步驟。在模擬過程中，若每一時(shí)間步選擇比例的節(jié)點(diǎn)更新其狀態(tài)，，同步更新方法和異步更新方法便對(duì)應(yīng)于兩種極端的情形[53,76]。若，即每個(gè)時(shí)間步更新所有節(jié)點(diǎn)的狀態(tài)，則與同步更新過程相同。若，即每個(gè)時(shí)間步平均隨機(jī)更新一個(gè)節(jié)點(diǎn)的狀態(tài)，則與異步更新過程相同。

從表1不難看出，同步更新方法的時(shí)空復(fù)雜度都比異步更新方法更低。同步更新方法的優(yōu)勢(shì)在于能快速模擬動(dòng)力學(xué)過程(即每個(gè)時(shí)間步同時(shí)改變所有節(jié)點(diǎn)狀態(tài))，且易于編寫程序；異步更新方法需要逐個(gè)更新系統(tǒng)中節(jié)點(diǎn)的狀態(tài)(即每個(gè)時(shí)間步只有一個(gè)節(jié)點(diǎn)改變其狀態(tài))，程序?qū)崿F(xiàn)較復(fù)雜。對(duì)現(xiàn)有文獻(xiàn)進(jìn)行不完全統(tǒng)計(jì)，發(fā)現(xiàn)若研究只關(guān)注于穩(wěn)態(tài)時(shí)的感染密度，往往選擇快速、簡(jiǎn)單的同步更新方法；若研究關(guān)注于動(dòng)力學(xué)演化過程(如局域現(xiàn)象)，往往選擇系統(tǒng)狀態(tài)改變緩慢的異步更新方法更為合適[16]。

表1 單位時(shí)間步內(nèi)，同步更新和異步更新方法的時(shí)空復(fù)雜度

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

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

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

兩種方法在模擬過程中的細(xì)微差異對(duì)流行病最終傳播范圍和爆發(fā)閾值會(huì)造成定量上的影響。更值得深思的問題是，對(duì)于同一流行病傳播模型，不同的模擬方法是否會(huì)對(duì)臨界值、臨界指數(shù)和局域現(xiàn)象等一系列問題有定性或者定量的影響？-度關(guān)聯(lián)、社區(qū)等，也包括退火網(wǎng)絡(luò)和時(shí)序網(wǎng)絡(luò)等是否會(huì)增加或減小兩種模擬方法定量上的差異？亟待更為系統(tǒng)地探究這兩種模擬方法對(duì)動(dòng)力學(xué)過程所帶來的影響，尤其是對(duì)非平衡動(dòng)力學(xué)過程所帶來的影響。

本文研究工作得到電子科技大學(xué)優(yōu)秀博士生學(xué)術(shù)支持計(jì)劃(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] 馬知恩, 周義倉(cāng), 王穩(wěn)地, 等. 傳染病動(dòng)力學(xué)的數(shù)學(xué)建模與研究[M]. 北京: 科學(xué)出版社, 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] 周濤, 傅忠謙, 牛永偉, 等. 復(fù)雜網(wǎng)絡(luò)上傳播動(dòng)力學(xué)研究綜述[J]. 自然科學(xué)進(jìn)展, 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] 李翔, 劉宗華, 汪秉宏. 網(wǎng)絡(luò)傳播動(dòng)力學(xué)[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)

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] 王偉, 楊慧, 龔凱, 等. 復(fù)雜網(wǎng)絡(luò)上的局域免疫研究[J]. 電子科技大學(xué)學(xué)報(bào)，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

國(guó)家自然科學(xué)基金(11105025,91324002)

王偉(1988 - )，男，博士生，主要從事復(fù)雜網(wǎng)絡(luò)傳播動(dòng)力學(xué)方面的研究.