靳禎,羅曉峰

(1.山西大學(xué) 復(fù)雜系統(tǒng)研究所,山西 太原 030006;2.山西大學(xué) 疾病防控的數(shù)學(xué)技術(shù)與大數(shù)據(jù)分析山西省重點實驗室,山西 太原 030006;3.山西大學(xué) 計算機與信息技術(shù)學(xué)院,山西 太原 030006)

復(fù)雜網(wǎng)絡(luò)傳播動力學(xué)研究進展

靳禎1,2,羅曉峰1,3

(1.山西大學(xué) 復(fù)雜系統(tǒng)研究所,山西 太原 030006;2.山西大學(xué) 疾病防控的數(shù)學(xué)技術(shù)與大數(shù)據(jù)分析山西省重點實驗室,山西 太原 030006;3.山西大學(xué) 計算機與信息技術(shù)學(xué)院,山西 太原 030006)

網(wǎng)絡(luò)上的信息或者疾病傳播問題是復(fù)雜網(wǎng)絡(luò)研究的焦點之一,其不僅依賴于信息或者疾病自身的傳播特征,而且依賴于網(wǎng)絡(luò)的結(jié)構(gòu)與演化,是疾病傳播動力學(xué)與網(wǎng)絡(luò)演化動力學(xué)的耦合過程,會產(chǎn)生十分復(fù)雜的動力學(xué)現(xiàn)象。文章主要介紹復(fù)雜網(wǎng)絡(luò)上傳播動力學(xué)的一些基本概念、建模與研究方法,主要包括基于對關(guān)系、度、節(jié)點和滲流理論等四類網(wǎng)絡(luò)傳播動力學(xué)模型以及復(fù)雜網(wǎng)絡(luò)傳播動力學(xué)建模與分析方面的主要進展。

復(fù)雜網(wǎng)絡(luò);對逼近;鄰接矩陣;邊倉室;滲流理論

0 引言

復(fù)雜網(wǎng)絡(luò)作為一門新興的學(xué)科,在近幾十年發(fā)展迅速。自然界以及人類社會中存在的大量復(fù)雜系統(tǒng)都可以用網(wǎng)絡(luò)來描述,幾乎所有的系統(tǒng)都可以抽象成為網(wǎng)絡(luò)模型,如Internet網(wǎng)、電力網(wǎng)、航空網(wǎng)、蛋白質(zhì)網(wǎng)及生物鏈網(wǎng)等[1]。根據(jù)不同的網(wǎng)絡(luò)特性,網(wǎng)絡(luò)有不同的分類,如根據(jù)度分布,網(wǎng)絡(luò)可分為規(guī)則網(wǎng)絡(luò)(Delta度分布)、隨機網(wǎng)絡(luò)[2](泊松度分布)、無標度網(wǎng)絡(luò)[3](冪率度分布)等;根據(jù)度的差異性大小,前兩種網(wǎng)絡(luò)稱為均勻網(wǎng)絡(luò)而無標度網(wǎng)絡(luò)稱為異質(zhì)網(wǎng)絡(luò);若網(wǎng)絡(luò)結(jié)構(gòu)隨時間不變,則稱網(wǎng)絡(luò)為靜態(tài)網(wǎng)絡(luò),否則為動態(tài)網(wǎng)絡(luò)。疾病或信息在群體行中的傳播可以看成是特定網(wǎng)絡(luò)結(jié)構(gòu)上信息的傳播及演化,既依賴于網(wǎng)絡(luò)的度分布、聚類系數(shù)、相關(guān)系數(shù)、平均路徑長度等拓撲結(jié)構(gòu)又依賴于信息的傳播特征,會產(chǎn)生復(fù)雜的動力學(xué)現(xiàn)象。近年來,復(fù)雜網(wǎng)絡(luò)傳播動力學(xué)方面的研究已經(jīng)有了長足的發(fā)展,發(fā)現(xiàn)了大量與傳統(tǒng)動力學(xué)有實質(zhì)性差異的現(xiàn)象,如無標度網(wǎng)絡(luò)上無閾值等現(xiàn)象[4]。本文將主要介紹靜態(tài)網(wǎng)絡(luò)上傳播動力學(xué)方面的基本概念、建模思想、分析方法及其研究進展。下面先回顧一些基本的網(wǎng)絡(luò)拓撲特征量[1]。

考慮一個節(jié)點規(guī)模為N的復(fù)雜網(wǎng)絡(luò),可以用簡單的無向網(wǎng)絡(luò)G=(V,E)來表示,V表示G的節(jié)點集,其元素為節(jié)點;E表示G的邊集,其元素為邊。網(wǎng)路G的鄰接矩陣定義為

A=(aij)N×N,

(1)

該矩陣是一個N階方陣,第i行j列的元素定義如下

(2)

網(wǎng)絡(luò)中節(jié)點i的度ki為與節(jié)點i連接的邊(鄰居節(jié)點)的總數(shù),任選一個節(jié)點其度為k的概率pk稱為網(wǎng)絡(luò)的度分布

(3)

N表示網(wǎng)絡(luò)的節(jié)點規(guī)模,Nk表示度為k的節(jié)點規(guī)模。網(wǎng)絡(luò)的平均度為

N.

(4)

從網(wǎng)絡(luò)中任選一條邊到達節(jié)點的度為k+1的概率記為qk,

(5)

其為網(wǎng)絡(luò)的余度分布,即任選一條邊到達節(jié)點的余度為k的概率[5-6]。生成函數(shù)是一種有效的數(shù)學(xué)工具,因此給出度分布及余度分布的概率生成函數(shù)

(6)

網(wǎng)絡(luò)的另一個重要性質(zhì)就是聚類特性,“物以類聚,人以群分”。聚類系數(shù)就是用來描述網(wǎng)絡(luò)中節(jié)點聚集程度的度量,分為全局和局部聚類系數(shù)。在給出聚類系數(shù)的定義之前,先給出網(wǎng)絡(luò)中二元組、三元組以及三角形的概念。在網(wǎng)絡(luò)G中,稱i-j為二元組(也稱邊或?qū)?,

若定義

(7)

其中i,j=1,2,…,N。類似地,在網(wǎng)絡(luò)G中,如果節(jié)點i和j,節(jié)點j和h之間都有連邊則稱i-j-h為三元組,特別地,如果i和h互為鄰居,則此三元組為三角形或閉三元組;否則為開三元組,其定義分別為

(8)

因此,網(wǎng)絡(luò)中三元組,開三元組和三角形數(shù)量分別為

(9)

(10)

對于網(wǎng)絡(luò)G的任意節(jié)點j,其度為kj,其鄰居之間實際存在的邊數(shù)Ej,則以該節(jié)點為中心的三角形數(shù)量為Ej,三元組數(shù)量為kj(kj-1)/2,則節(jié)點j的聚類系數(shù)定義為

(11)

除以上網(wǎng)絡(luò)特性外,網(wǎng)絡(luò)的一些特征之間也有相關(guān)性,如節(jié)點度、節(jié)點狀態(tài)等。為定量刻畫網(wǎng)絡(luò)中節(jié)點間的相關(guān)性大小,有以下三類相關(guān)系數(shù)的定義:

(1) 不同狀態(tài)節(jié)點之間的相關(guān)性：狀態(tài)為A和C的節(jié)點間的相關(guān)系數(shù)[7]

(12)

其中,[AC]表示狀態(tài)為A與狀態(tài)為C節(jié)點間的實際連邊數(shù),[A]和[C]分別表示狀態(tài)A和C的節(jié)點數(shù)。

(2) 不同度節(jié)點之間的相關(guān)性：度為k和l的節(jié)點間的相關(guān)系數(shù)[8]

(13)

其中,Nkl是度為k與l的節(jié)點間的實際連邊數(shù)。

(3) 節(jié)點處于不同度和狀態(tài)之間的相關(guān)性：狀態(tài)為A度為k和狀態(tài)為C度為m的節(jié)點間的相關(guān)系數(shù)[1]

(14)

其中,[Ak]表示狀態(tài)為A度為k的節(jié)點數(shù),[Cm]表示狀態(tài)為C度為m的節(jié)點數(shù),[AkCm]表示這兩類節(jié)點間的實際連邊數(shù)。

不同的網(wǎng)絡(luò)結(jié)構(gòu)有不同的網(wǎng)絡(luò)拓撲特性,經(jīng)典的網(wǎng)絡(luò)有四種:規(guī)則網(wǎng)絡(luò)、隨機網(wǎng)絡(luò)[2]、小世界網(wǎng)絡(luò)[9]和無標度網(wǎng)絡(luò)[3],表1給出了這四類網(wǎng)絡(luò)度分布和聚類系數(shù)的特征。

表1 經(jīng)典網(wǎng)絡(luò)的度分布和聚類系數(shù)

規(guī)則網(wǎng)絡(luò)的聚類系數(shù)大、隨機網(wǎng)絡(luò)度分布均勻聚類系數(shù)小,小世界網(wǎng)絡(luò)的度分布均勻聚類系數(shù)大,而無標度網(wǎng)絡(luò)的度分布異質(zhì)但聚類不明顯[1]。除了一般的隨機網(wǎng)絡(luò),學(xué)者們經(jīng)常用到的是廣義的隨機網(wǎng)絡(luò)即配置網(wǎng)絡(luò)[10],這類網(wǎng)絡(luò)通過給定的度分布序列生成隨機網(wǎng)絡(luò),當網(wǎng)絡(luò)規(guī)模足夠大時,聚類系數(shù)趨于零,即網(wǎng)絡(luò)結(jié)構(gòu)為類樹結(jié)構(gòu)。

以上介紹了網(wǎng)絡(luò)中一些拓撲特征量的基本概念和具體的數(shù)學(xué)表達式,下面將對靜態(tài)網(wǎng)絡(luò)上的四類傳播動力學(xué)模型(基于對關(guān)系、度、節(jié)點以及滲流理論的動力學(xué)模型)的建模思想、分析方法以及主要進展逐一介紹。本文用到的主要符號及含義如表2所示。

表2 本文的基本符號表

1 網(wǎng)絡(luò)傳播動力學(xué)模型

最基本的兩類倉室模型為SIS和SIR模型[1],其中個體可處于易感S、染病I、恢復(fù)R三種狀態(tài)。對于SIS類型的疾病,個體得病后還可以恢復(fù)成易感個體,而對于SIR類型的疾病,個體得病后恢復(fù)成永久免疫性個體。網(wǎng)絡(luò)傳播動力學(xué)將群體中的個體看成節(jié)點,個體與個體之間的接觸看成邊,研究網(wǎng)絡(luò)結(jié)構(gòu)和疾病或者信息共同演化的規(guī)律?；诓煌臉藴?網(wǎng)絡(luò)傳播動力學(xué)模型有不同的分類。如基于不同的網(wǎng)絡(luò),模型可分為規(guī)則網(wǎng)絡(luò)、隨機網(wǎng)絡(luò)及無標度網(wǎng)絡(luò)等動力學(xué)模型。基于網(wǎng)絡(luò)度異質(zhì)性,模型可以分為均勻網(wǎng)絡(luò)模型,異質(zhì)網(wǎng)絡(luò)模型?；诰W(wǎng)絡(luò)結(jié)構(gòu)是否隨時間變化,模型可分為靜態(tài)網(wǎng)絡(luò)模型和動態(tài)網(wǎng)絡(luò)模型。而基于建模角度和方法的不同,模型可以分為基于對關(guān)系、度、節(jié)點及滲流理論的動力學(xué)模型,下面分別介紹靜態(tài)網(wǎng)絡(luò)中的這四類模型。

1.1 基于對關(guān)系的動力學(xué)模型

考慮一個標準傳染率的SIS均勻混合動力學(xué)模型

(15)

其中β和γ分別表示傳染率和恢復(fù)率系數(shù),[S]和[I]分別表示易感者和染病者的數(shù)量。顯然,從網(wǎng)絡(luò)的角度來看,均勻混合模型將網(wǎng)絡(luò)看作是規(guī)則網(wǎng)絡(luò)或者完全圖,忽略了網(wǎng)絡(luò)復(fù)雜的結(jié)構(gòu)及其動態(tài)演化?；趯﹃P(guān)系的動力學(xué)模型主要研究節(jié)點以及節(jié)點間的連邊(對或二元組)隨時間的動力學(xué)演化過程,下面從均勻網(wǎng)絡(luò)和異質(zhì)網(wǎng)絡(luò)兩個方面來介紹基于對關(guān)系的SIS動力學(xué)模型。

1.1.1 均勻網(wǎng)絡(luò)上的對關(guān)系模型

考慮一個規(guī)模為N的網(wǎng)絡(luò),其中每個個體有兩種不同的狀態(tài):易感狀態(tài)S和染病狀態(tài)I,則節(jié)點及節(jié)點之間連邊的動力學(xué)方程為

=γ[II]-γ[SI]-β[SI]-β[ISI]+β[SSI],

(16)

其中,[SI]二元組表示易感和染病節(jié)點的連邊數(shù)量,[SSI]代表三元組S-S-I的數(shù)量而[ISI]代表三元組I-S-I數(shù)量的二倍[7]。在模型(16)中單節(jié)點的變化依賴二元組的變化,二元組的變化又依賴三元組的變化,方程并不封閉。為了研究其動力學(xué)性態(tài)須在誤差允許的范圍內(nèi)封閉方程,下面介紹幾種封閉方程的逼近方法,分無聚類和有聚類兩種。

1)無聚類的均勻網(wǎng)絡(luò)三元組逼近

文獻[12]提出了用一元組(即單節(jié)點)和二元組來近似表示三元組的方法。對于給定的無聚類網(wǎng)絡(luò),設(shè)節(jié)點狀態(tài)分為A、B、C三種類型。對于狀態(tài)為B的節(jié)點,若其鄰居狀態(tài)為A和C的節(jié)點數(shù)都服從泊松分布且相互獨立,三元組可近似表示為

(17)

對于狀態(tài)為B的節(jié)點,若其鄰居狀態(tài)為A和C的節(jié)點數(shù)服從多項分布,三元組可近似表示為

(18)

2)含聚類的均勻網(wǎng)絡(luò)三元組逼近

在含聚類的網(wǎng)絡(luò)中,文獻[7,13-14]給出了均勻網(wǎng)絡(luò)中三元組的近似表達式

(19)

其中φ表示網(wǎng)絡(luò)的全局聚類系數(shù)(見式(10)),CAC為狀態(tài)相關(guān)系數(shù)(見式(12))。

1.1.2 異質(zhì)網(wǎng)絡(luò)上的對關(guān)系模型

與均勻網(wǎng)絡(luò)相比,異質(zhì)網(wǎng)絡(luò)主要表現(xiàn)在節(jié)點度的差異性大,有的節(jié)點度非常大,有的則很小。而現(xiàn)實生活中大部分網(wǎng)絡(luò)均為異質(zhì)網(wǎng)絡(luò),為使模型更加準確地反映現(xiàn)實,考慮不同狀態(tài)、不同度的節(jié)點間構(gòu)成的二元組變化更加合理。因此,建立如下異質(zhì)網(wǎng)絡(luò)的對關(guān)系模型[15]

(20)

其中,K(K≤N)表示網(wǎng)絡(luò)的最大度,[Sk]與[Ik]表示度為k的易感者和染病者的數(shù)量;正如表2所示,[SkSl],[SkSl],[SkSl]表示相應(yīng)二元組的數(shù)量。同樣地,要封閉模型(20),有兩類異質(zhì)網(wǎng)絡(luò)逼近公式:1)異質(zhì)網(wǎng)絡(luò)三元組的逼近公式,分有無聚類兩種情形[15];2)異質(zhì)網(wǎng)絡(luò)二元組的逼近公式。

1)異質(zhì)網(wǎng)絡(luò)三元組的逼近公式[15]

①無聚類的異質(zhì)網(wǎng)絡(luò)三元組逼近公式:不考慮聚類的影響,即φ=0時,異質(zhì)網(wǎng)絡(luò)三元組近似為

(21)

②含聚類的異質(zhì)網(wǎng)絡(luò)三元組逼近公式:考慮異質(zhì)網(wǎng)絡(luò)中三角形的影響,當φ≠0時,三元組近似為

(22)

其中CAkCm表示網(wǎng)絡(luò)中度為k狀態(tài)為A與度為m狀態(tài)為C的節(jié)點之間的相關(guān)系數(shù)(見(14))。

2)異質(zhì)網(wǎng)絡(luò)二元組的逼近公式

①基于二元組的異質(zhì)網(wǎng)絡(luò)二元組的反卷積逼近公式:2002年,Eames和Keeling[15]基于性傳播疾病,提出了二元組的反卷積逼近

(23)

其中,Ckl表示度為k和l節(jié)點之間的相關(guān)系數(shù)(見(13))。

②基于節(jié)點的異質(zhì)網(wǎng)絡(luò)二元組的反卷積逼近公式:2011年,House和Keeling[8]提出了基于節(jié)點的異質(zhì)網(wǎng)絡(luò)二元組的反卷積逼近

(24)

逼近公式(24)假設(shè)B狀態(tài)節(jié)點連接到Ak型節(jié)點不依賴于Ak節(jié)點的度,即與網(wǎng)絡(luò)的局部結(jié)構(gòu)無關(guān)。緊對模型就是根據(jù)這一逼近公式得到,超緊對模型也是在緊對模型的基礎(chǔ)上建立的,模型的維數(shù)更低[16]。

③基于同配混合的異質(zhì)網(wǎng)絡(luò)二元組的反卷積逼近公式:在同配混合的假設(shè)下,與公式(23)不同,文[8]也給出了二元組[AkBl]的逼近

(25)

這個逼近雖然保持了網(wǎng)絡(luò)的同配性,卻忽略了節(jié)點狀態(tài)之間的聯(lián)系。

注1.當度分布pk取Delta分布,即每個節(jié)點的度為常數(shù)k,模型(20)通過逼近公式(25)近似后的模型與均勻混合模型(15)一致,因此網(wǎng)絡(luò)動力學(xué)模型考慮的更加細致。

注2.通過逼近公式(25),模型(20)變?yōu)榉匠?/p>

(26)

在度不相關(guān)的網(wǎng)絡(luò)中,相關(guān)系數(shù)Ckl=1,則模型(26)與Pastor-Satorra等基于節(jié)點度的分類提出的異質(zhì)平均場模型[4]一致,在1.2節(jié)對此將做詳細介紹。

基于對關(guān)系的傳播動力學(xué)模型不僅能描述網(wǎng)絡(luò)中不同狀態(tài)節(jié)點隨時間的演化過程,而且能捕捉到不同狀態(tài)節(jié)點間連邊隨時間的演化規(guī)律,通過模型中所含的網(wǎng)絡(luò)拓撲參數(shù)來揭示網(wǎng)絡(luò)結(jié)構(gòu)對疾病傳播的影響。然而,找到合適且精確的對逼近公式是對關(guān)系模型能否精確的關(guān)鍵,也是研究的挑戰(zhàn)之一。Matsuda[17]在1992年首次提出對關(guān)系模型,之后Keeling[7],Rand[13],Eamse[15]等給出了不同的模型和逼近公式,Trapman[14]等討論了網(wǎng)絡(luò)結(jié)構(gòu)對基本再生數(shù)的影響,Luo[18]等分析了均勻網(wǎng)絡(luò)上的SIS對逼近模型的全局動力學(xué)性態(tài)。基于對關(guān)系的模型也推廣到了異質(zhì)網(wǎng)絡(luò)[15]、有向網(wǎng)絡(luò)[16]、加權(quán)網(wǎng)絡(luò)[19]以及網(wǎng)絡(luò)顯示模體[20]、非馬爾科夫過程傳播[21]、緊對模型[8,22]、超緊對模型[23]、婚姻網(wǎng)絡(luò)[24]等。

1.2 基于度的動力學(xué)模型

從對關(guān)系模型(26)看出,在度不相關(guān)的網(wǎng)絡(luò)中,即相關(guān)系數(shù)Ckl=1時,通過基于同配混合的異質(zhì)網(wǎng)絡(luò)二元組的反卷積逼近公式(25)得到的對關(guān)系模型與Pastor-Satorra等基于節(jié)點度的分類提出的異質(zhì)平均場模型[4,25]一致?；诠?jié)點度的動力學(xué)模型假設(shè)度相同的節(jié)點具有相同的動力學(xué)規(guī)律,這部分將介紹兩種基于節(jié)點度的動力學(xué)模型:異質(zhì)平均場模型和邊倉室模型。

1.2.1 異質(zhì)平均場模型

Pastor-Satorras等人首次用復(fù)雜網(wǎng)絡(luò)來刻畫個體間的接觸信息,研究個體接觸的異質(zhì)性對疾病傳播的影響[4]。在文獻[4]中,假設(shè)相同度的節(jié)點有相同的動力學(xué)規(guī)律,然后應(yīng)用平均場理論建立確定性模型來研究相同度節(jié)點的動力學(xué)過程。下面以SIS模型為例來介紹異質(zhì)平均場模型。

設(shè)網(wǎng)絡(luò)中度為k的節(jié)點中染病節(jié)點的密度為ρk,得到以下SIS異質(zhì)平均場模型

(27)

即網(wǎng)絡(luò)中任意一條邊指向染病者的概率等于染病者發(fā)出的總邊數(shù)占網(wǎng)絡(luò)總邊數(shù)的比例。從模型(27)得其基本再生數(shù)為

R0=β〈k2〉/〈k〉.

(28)

因此,疾病的傳播閾值為βc=〈k〉/〈k2〉。當疾病的傳染率小于傳播閾值βc(或R0<1)時,疾病最終消失,而當疾病的傳染率大于傳播閾值βc(或R0>1)時,疾病流行。特別地,Pastor-Satorras等人發(fā)現(xiàn)在度分布為pk∝k-α的無標度網(wǎng)絡(luò)中,當網(wǎng)絡(luò)規(guī)模N→∞,冪指數(shù)2<α≤3時,疾病的傳播閾值會消失,而均勻混合網(wǎng)絡(luò)上始終存在有限閾值,這一發(fā)現(xiàn)顛覆了傳統(tǒng)的有限傳播閾值理論。

異質(zhì)平均場模型通過網(wǎng)絡(luò)度分布的信息,描述了度分布對傳播動力學(xué)的影響,但忽略了聚類系數(shù)、團簇系數(shù)等網(wǎng)絡(luò)拓撲結(jié)構(gòu)的影響。此外,在度不相關(guān)的假設(shè)下,異質(zhì)平均場模型被推廣到SIR類型的疾病[27],帶有人口動力學(xué)的動態(tài)網(wǎng)絡(luò)[28],多菌株傳染病[29],有向網(wǎng)絡(luò)[30],加權(quán)網(wǎng)絡(luò)等。文獻[31]也給出了在度相關(guān)網(wǎng)絡(luò)中SIS和SIR模型的疾病傳播閾值,發(fā)現(xiàn)在無標度網(wǎng)絡(luò)中,當網(wǎng)絡(luò)規(guī)模N→∞,冪指數(shù)2<α≤3是疾病閾值消失的充分條件。

1.2.2 邊倉室模型

傳統(tǒng)的SIR倉室模型是按個體的狀態(tài)將人群分為三種不同的類型(倉室):易感者, 染病者和恢復(fù)者人群,考慮了人群在各個倉室之間的轉(zhuǎn)移。這類倉室模型的一個基本假設(shè)是人群是均勻混合的,忽略了個體單位時間內(nèi)接觸人數(shù)的異質(zhì)性。而異質(zhì)平均場模型考慮了個體接觸的異質(zhì)性,但模型的維數(shù)一般都比較高,增加了數(shù)學(xué)分析的難度。而邊倉室模型[32-33]的出現(xiàn)彌補了傳統(tǒng)倉室模型和異質(zhì)平均場模型的不足。它借鑒倉室模型的思想,將邊按照不同的類型分成三個不同的倉室,考慮不同邊倉室之間的演化規(guī)律,得到一個低維的模型。下面詳細介紹SIR邊倉室模型[32-33]。

網(wǎng)絡(luò)中易感者的比例等于從網(wǎng)絡(luò)中隨機抽取的一個測試節(jié)點i是易感者的概率,為計算此概率,邊倉室模型做出如下假設(shè):1) 測試節(jié)點i不會傳染疾病給它的鄰居;2) 節(jié)點i的鄰居節(jié)點間相互獨立,即假設(shè)網(wǎng)絡(luò)的聚類很小;3) 節(jié)點間的度不相關(guān),因此沿著一條邊到達度為k的節(jié)點的概率為kpk/〈k〉。

設(shè)S(t),I(t),R(t)分別為網(wǎng)絡(luò)中易感者、染病者和恢復(fù)者的比例;Θ(t)表示在t時刻,隨機選擇測試節(jié)點i,它的一個鄰居節(jié)點j還沒有把疾病傳給i節(jié)點的概率。節(jié)點i是易感者意味著節(jié)點i的任意一個鄰居都沒有傳染節(jié)點i,當節(jié)點i的度為k且其鄰居節(jié)點間相互獨立時,節(jié)點i是易感者的概率為Θk(t)。因此,網(wǎng)絡(luò)中易感者的比例為

(29)

為得到Θ,在t時刻根據(jù)鄰居節(jié)點j的狀態(tài)分成三部分:1)鄰居節(jié)點j是易感者的概率為ΦS;2)鄰居節(jié)點j是染病者且沒有傳染節(jié)點i的概率為ΦI;3)鄰居節(jié)點j是恢復(fù)者且沒有傳染節(jié)點i的概率為ΦR;則

Θ=ΦS+ΦI+ΦR.

(30)

各邊倉室之間的流程圖如圖1所示。

Fig.1 Flow diagram for edge-based compartmental model[33]圖1 邊倉室模型流程圖[33]

下面給出ΦS,ΦI和ΦR的求解過程。

由于節(jié)點的度不相關(guān),節(jié)點i連接到度為k的鄰居節(jié)點j的概率為kpk/〈k〉,同時節(jié)點i不會傳染疾病給節(jié)點j,則度為k的j節(jié)點為易感者的概率為Θk-1。因此,

(31)

(32)

綜上,可得邊倉室模型為

S=G0(Θ),

I=1-S-R.

(33)

對于模型(33)由無病平衡點的局部漸近穩(wěn)定性,得疾病的基本再生數(shù)為

(34)

(35)

邊倉室模型僅用一維模型Θ的動力學(xué)方程便可以刻畫疾病的動力學(xué)行為,其復(fù)雜程度與均勻混合模型一致,但可以將網(wǎng)絡(luò)的度分布信息結(jié)合到模型中。然而,由于邊倉室模型假設(shè)鄰居節(jié)點間相互獨立,因此它不適用于SIS類型的疾病[19],將邊倉室模型推廣到SIS類型的疾病傳播是一個挑戰(zhàn)性的工作。此外,利用反卷積逼近和三元組逼近公式

可以推出邊倉室模型與基于對關(guān)系的動力學(xué)模型(36)等價[34]。

=β[SSI]-β[ISI]-β[SI]-β[SI].

(36)

邊倉室模型也推廣到含斷邊重連的動態(tài)網(wǎng)絡(luò)[33],聚類網(wǎng)絡(luò)[34],加權(quán)網(wǎng)絡(luò)[35-36],帶有人口動力學(xué)的動態(tài)網(wǎng)絡(luò)[37]以及性傳播與非性傳播同時存在的疾病模型[38]等。

1.3 基于節(jié)點的動力學(xué)模型

在動力學(xué)傳播模型中,一種考慮更精確的模型為基于節(jié)點的動力學(xué)模型,不同于對關(guān)系和度的動力學(xué)模型,該模型應(yīng)用連續(xù)時間Markov鏈技術(shù),充分考慮到每個節(jié)點的特征,深入研究網(wǎng)絡(luò)的拓撲結(jié)構(gòu)對傳染病的影響。下面介紹VanMieghem[39]提出的基于節(jié)點(鄰接矩陣)構(gòu)建的病毒傳播動力學(xué)模型。

2009年,VanMieghem[39]提出了基于節(jié)點的病毒傳播動力學(xué)模型,分析了病毒在網(wǎng)絡(luò)上的動力學(xué)傳播過程?？紤]一個包含N個節(jié)點L條邊的簡單無向連通圖G,其鄰接矩陣為A=(aij)N×N。染病節(jié)點i傳染其一個鄰居的速率為β>0,恢復(fù)率為γ>0,假定疾病的傳染和恢復(fù)是兩個獨立的泊松過程。Xi(t)表示在t時刻節(jié)點i的狀態(tài),即

(37)

令Δt→0,得到隨機SIS病毒動力學(xué)傳播模型

(38)

利用平均場的思想,對式(37)兩邊取均值E[Si(t)]=Pr[Xi(t)=1]=vi(t),得

(39)

對于式(39)右邊的第三項

E[1{Xi(t)}=11{Xj(t)}=1]=Pr[Xi(t)=1,Xj(t)=1]=Pr[Xi(t)=1]Pr[Xj(t)=1|Xi(t)],

在網(wǎng)絡(luò)連通的情況下,有Pr[Xj(t)=1|Xi(t)=1]≥Pr[Xj(t)=1],因為給定一個染病者節(jié)點i,不可能對其鄰居節(jié)點j的染病概率有抑制作用。現(xiàn)假定隨機變量1{Xi(t)=1}和1{Xj(t)=1}相互獨立,即

E[1{Xi(t)}=11{Xj(t)}=1]=E[1{Xi(t)}=1]E[1{Xj(t)}=1].

(40)

令Δt→0,結(jié)合公式(39)和(40)得到確定性SIS病毒傳播模型

(41)

方程(41)也稱為N-intertwined SIS病毒傳播模型。記V(t)=[v1(t),v2(t),…vN(t)],diag(vi(t))是對角元素為v1(t),v2(t),…,vN(t)的一個對角矩陣,則微分方程(41)相應(yīng)的矩陣形式為

(42)

記鄰接矩陣A的最大實特征值為λmax(A),對方程(42),只要初始值V(0)≠0,當有效傳染率β/γ≤1/λmax(A)時,無病平衡點是全局漸近穩(wěn)定的;當有效傳染率β/γ>1/λmax(A)時,地方病平衡點也是全局漸近穩(wěn)定的。

文獻[39]對隨機模型(38)與確定性模型(41)做了比較,得出平均場近似的N-intertwined SIS模型(41)高估了節(jié)點被傳染的概率,原因是假定隨機變量1{Xi(t)=1}和1{Xj(t)=1}相互獨立?？梢钥闯龌诠?jié)點的隨機SIS網(wǎng)絡(luò)模型更加精確但難以數(shù)學(xué)處理,而確定性SIS模型可作為隨機SIS模型的近似,且隨著網(wǎng)絡(luò)規(guī)模的增大,隨機SIS網(wǎng)絡(luò)模型與確定性SIS網(wǎng)絡(luò)模型的解的差異減小?；诠?jié)點的動力學(xué)模型充分考慮了每個節(jié)點的特征,能深入研究網(wǎng)絡(luò)的拓撲結(jié)構(gòu)對傳染病的影響,其建模的思想也推廣到了其他的模型中,如病毒傳播模型[40-41],有單病毒模型[42-46], 雙病毒-單網(wǎng)絡(luò)模型[47],雙病毒-雙網(wǎng)絡(luò)模型[48-49]等,其中,文獻[40-48]的病毒傳播模型基于線性傳播率,文獻[49-51]的模型是基于非線性的傳播率。

1.4 基于滲流理論的動力學(xué)模型

除了上面三類動力學(xué)模型,在復(fù)雜網(wǎng)絡(luò)上研究傳播動力學(xué)的另外一種方法是基于滲流理論的動力學(xué)模型,簡稱滲流模型。滲流是物理學(xué)中的一種叫法,在現(xiàn)實生活存在著許許多多的滲流現(xiàn)象。例如,在Internet上,由路由器組成的網(wǎng)絡(luò)中,究竟哪些路由器不工作或者多大比例的路由器不工作會影響到Internet的正常運行呢?再比如,在疾病傳播過程中,到底切斷人與人之間的哪些傳播途徑或者切斷多少能夠抑制疾病的大規(guī)模流行?這些現(xiàn)象和問題都可以通過滲流模型來解釋和研究[52]。

滲流分為點滲流和邊滲流,點滲流主要研究隨機選擇的點被占用后形成的連通分支或巨連通分支對網(wǎng)絡(luò)功能和結(jié)構(gòu)的影響(見圖 2(a),灰色的點為“占用點”),如研究網(wǎng)絡(luò)對節(jié)點隨機刪除的彈性度 (Resilience)[53-54],而邊滲流主要研究隨機選擇的邊被占用后,由“占用邊”連接的點形成的連通分支或巨連通分支對網(wǎng)絡(luò)功能和結(jié)構(gòu)的影響(見圖 2(b),灰色的邊為“占用邊”),如研究疾病的流行閾值和最終規(guī)模等[55]。其中,連通分支(Component)為相互連通的占用點(或由占用邊連接的點)形成的網(wǎng)絡(luò)子圖,如圖 2(a)中1-6,3-4,8三個連通分支和圖 2(b)中2-3-4-7,5-8兩個連通子圖,當連通分支包含了網(wǎng)絡(luò)中相當比例的節(jié)點即連通分支的節(jié)點規(guī)模與網(wǎng)絡(luò)的規(guī)模為同一數(shù)量級時這一連通分支稱為巨連通分支(Giant Component)[56]。

Fig.2 (a) Site percolation (Grey occupied node); (b) Bond percolation (Bold-grey occupied edge)圖2 (a)點滲流(灰色為占用點);(b)邊滲流(灰色為占用邊)

一般地,用“占用概率T”來表示網(wǎng)絡(luò)中被占用點或邊的比例。在點滲流中,正常的節(jié)點可以看成是被占用的節(jié)點(如圖 2(a)的灰色節(jié)點)。關(guān)于點滲流,Cohen等發(fā)現(xiàn)在度分布服從冪率分布,pk～k-α(α<3)時,網(wǎng)絡(luò)始終存在一個巨連通分支,即使點占用概率的臨界值Tc等于或小于零,表明冪率網(wǎng)絡(luò)對點隨機刪除有很強的魯棒性[54]。對點滲流的其他研究和擴展見文獻[53,57]。疾病的傳播動力學(xué)主要通過邊滲流來研究,因此下面主要回顧在不含聚類網(wǎng)絡(luò)和含聚類網(wǎng)絡(luò)上,邊滲流模型在傳播動力學(xué)中的研究進展。

1.4.1 不含聚類的邊滲流模型

網(wǎng)絡(luò)上的SIR傳染病模型可以映射到邊滲流模型中[55]?？紤]染病節(jié)點i和它的一個易感鄰居j,假定這兩節(jié)點之間的平均傳染率為βij,染病節(jié)點i的病程時間為τi,則疾病這這段時間內(nèi)沒有從節(jié)點i傳染到節(jié)點j的概率為

(43)

因此,從節(jié)點i到節(jié)點j傳染的概率為

Tij=1-e-βijτi.

(44)

傳染率βij,染病時間τi分別服從分布P(β),P(τ)且相互獨立,則每條邊的平均傳染概率,即邊占用概率為

(45)

G1(x;T)=G1(1+(x-1)T).

(46)

H0(x;T)表示任選一點所屬的連通分支(由占用邊連接而成)規(guī)模分布的生成函數(shù),H1(x;T)表示任選一條邊到達的節(jié)點所屬的連通分支(由占用邊連接而成)規(guī)模分布的生成函數(shù),

H0(x;T)=xG0(H1(x;T);T),

H1(x;T)=xG1(H1(x;T);T).

(47)

當網(wǎng)絡(luò)中沒有巨連通分支時,由式(47)得占用邊連接的連通分支的平均規(guī)模,即疾病暴發(fā)的平均規(guī)模為

(48)

因此,

(49)

從式(49)得疾病的閾值為

(50)

當網(wǎng)絡(luò)中出現(xiàn)巨連通分支,即邊占用概率T>Tc時,由于H0(x;T)僅表示連通分支規(guī)模的分布,而網(wǎng)絡(luò)由連通分支和巨連通分支組成,即

H0(1;T)=1-MR,

(51)

MR(T)表示巨連通分支規(guī)模(由占用邊連接而成)占整個種群規(guī)模的比例。因此,流行病的最終規(guī)模為

MR(T)=1-G0(u;T),

u=G1(u;T).

(52)

u為沿著一條單邊到達的節(jié)點不屬于由占用邊連接而成的巨連通分支的概率。

綜上,可以看出邊滲流模型和SIR傳染病相對應(yīng)的量分別是:滲流相變閾值對應(yīng)傳染病的流行閾值,連通分支(由占用邊連接的點形成)的分布對應(yīng)傳染病暴發(fā)規(guī)模的分布,閾值之上形成的巨連通分支對應(yīng)傳染病流行的最終規(guī)模。在時間取極限,網(wǎng)絡(luò)規(guī)模無限大時,邊滲流模型可以提供傳染病的流行規(guī)模,但目前滲流還不能反映流行病隨時間的演化特性。此外,對于異質(zhì)的染病時間分布,Kenah[58],Miller[59]給出了相應(yīng)的流行病閾值,平均暴發(fā)規(guī)模,流行病最終規(guī)模。

當占用概率T=1時,如文獻[6]所述,H0(x)表示整個網(wǎng)絡(luò)中隨機任選一節(jié)點所屬連通分支規(guī)模的概率生成函數(shù),即網(wǎng)絡(luò)中所有的邊被占用,H0(x;1)=H0(x);H1(x)表示任選一條邊到達節(jié)點所屬連通分支規(guī)模的概率生成函數(shù),H1(x;1)=H1(x),這樣可得到整個網(wǎng)絡(luò)連通分支的平均規(guī)模,巨連通分支規(guī)模在網(wǎng)絡(luò)中所占的比例及閾值。以上結(jié)果在不含聚類的配置網(wǎng)絡(luò)中得到,但現(xiàn)實網(wǎng)絡(luò)一般都含有聚類,因此Newman將滲流推廣到含聚類的網(wǎng)絡(luò)中。

1.4.2 含聚類的邊滲流模型

2009年,Newman構(gòu)建了有三角形的弱聚類配置網(wǎng)絡(luò)[11],如圖3所示。所謂弱聚類網(wǎng)絡(luò)是指三角形之間無重邊數(shù)或很小,而強聚類網(wǎng)絡(luò)指邊的重數(shù)大,多個三角形共享一條邊[60]。

Fig.3 Illustration of network with weak clustering圖3 弱聚類網(wǎng)絡(luò)示意圖[6]

在該弱聚類網(wǎng)絡(luò)中,每個節(jié)點有兩種度:單邊和三角形。定義網(wǎng)絡(luò)的聯(lián)合度分布pst為網(wǎng)絡(luò)中有s條單邊,t個三角節(jié)點的比例,顯然該類節(jié)點的度為k=s+2t,因此網(wǎng)絡(luò)的度分布為

(53)

其中,δij為Delta函數(shù)。聯(lián)合度分布pst和度分布pk的生成函數(shù)分別為

(54)

(55)

進一步定義節(jié)點的余度分布qst,rst,

(56)

其中,qst表示沿著一條單邊到達一個節(jié)點,其剩余邊數(shù)為s,三角形數(shù)為t的概率;qst表示沿著一個三角形到達一個節(jié)點,其單邊數(shù)為s,剩余三角形數(shù)為t的概率,〈s〉,〈t〉為相應(yīng)的均值。兩余度分布對應(yīng)的生成函數(shù)為

(57)

下面利用以上變量計算聚類網(wǎng)絡(luò)巨連通分支的規(guī)模,定義u1為沿著一條單邊到達的節(jié)點不屬于巨連通分支的概率,v1沿著一個三角形到達的節(jié)點不屬于巨連通分支的概率,則

(58)

同樣用MR表示巨連通分支規(guī)模占整個網(wǎng)絡(luò)的比例,則

(59)

文獻[11]同樣給出了相變的閾值條件

(60)

當網(wǎng)絡(luò)中三角形為零時,該閾值條件變回到原始閾值條件(當Tc=1時見式(50))。

類似于無聚類網(wǎng)絡(luò)[55],當邊占用概率為T時,u2為沿著一條單邊到達的節(jié)點屬于連通分支(由占用邊連接而成)的概率,v2沿著一個三角形到達的節(jié)點屬于連通分支(由占用邊連接而成)的概率,則流行病的最終規(guī)模MR(T)為

(61)

Newman發(fā)現(xiàn)當該弱聚類網(wǎng)絡(luò)的平均度(總度的平均度)不變,增加聚類系數(shù)時疾病的閾值增加,流行病最終規(guī)模減小[11]。Newman在強聚類的二部圖投影網(wǎng)絡(luò)中,也發(fā)現(xiàn)了同樣的結(jié)果[61]。而Miller卻發(fā)現(xiàn)與相同聯(lián)合度分布和相同度度相關(guān)性的無聚類網(wǎng)絡(luò)相比,弱聚類網(wǎng)絡(luò)中疾病閾值和疾病的流行規(guī)模都減小[62]。Gleeson構(gòu)建了含有團(Clique)的聚類網(wǎng)絡(luò),發(fā)現(xiàn)與Miller同樣的結(jié)果[63]。那么,聚類的增加到底是促進疾病閾值還是抑制呢?我們得出聚類對疾病閾值的影響是雙重的既可以增加閾值又可以減少閾值[64]。

2 結(jié)論

網(wǎng)絡(luò)上的疾病或信息傳播動力學(xué)作為復(fù)雜網(wǎng)絡(luò)研究中的重要課題,具有非常重要的意義。通過網(wǎng)絡(luò)傳播動力學(xué)模型來研究疾病或信息在網(wǎng)絡(luò)上的傳播過程,有助于弄清網(wǎng)絡(luò)結(jié)構(gòu)和疾病或信息的耦合動力學(xué)演化機制,揭開網(wǎng)絡(luò)結(jié)構(gòu)(如度分布,度異質(zhì)性、度相關(guān)性,狀態(tài)相關(guān)性、聚類等)對疾病或信息傳播影響的面紗,進而為制定疾病預(yù)防控制策略和網(wǎng)絡(luò)輿情控制提供指導(dǎo)。

本文介紹了靜態(tài)網(wǎng)絡(luò)上基于對關(guān)系、度、節(jié)點和滲流理論4類傳播動力學(xué)模型的建模思想和分析方法,并探究了各類模型的優(yōu)勢和局限性?；趯﹃P(guān)系,節(jié)點的動力學(xué)模型和基于度的異質(zhì)平均場模型,既可以研究SIS模型也可以研究SIR模型,而基于度的邊倉室模型和滲流模型僅適用于SIR模型。基于節(jié)點的動力學(xué)模型,利用Markov鏈和網(wǎng)絡(luò)的鄰接矩陣考慮了每個節(jié)點的動力學(xué)過程,比對關(guān)系和度的動力學(xué)模型更精群,但數(shù)學(xué)分析比較困難。此外,基于滲流理論的模型不同于另外三種模型,可以給出SIR流行病的閾值,流行病最終規(guī)模,但不能描述動力學(xué)的時間演化過程,并且僅僅適用于SIR模型。動態(tài)網(wǎng)絡(luò)[28]、耦合網(wǎng)絡(luò)[65]、多層網(wǎng)絡(luò)[66]上的傳播動力學(xué)研究也有一定的研究成果,總之網(wǎng)絡(luò)上疾病和信息的傳播動力學(xué)研究在今后仍將是研究熱點,并將廣泛的推廣到實際應(yīng)用中。

致謝：研究生荊文君、曹曉春、馮姍姍及王寧寧在整理文獻和論文的撰寫過程中所做的工作。

[1] 靳禎,孫桂全,劉茂省.網(wǎng)絡(luò)傳染病動力學(xué)建模與分析[M].北京：科學(xué)出版社, 2014.

[2] Erd?s P,Rényi A.On the Evolution of Random Graphs[J].PublicationsoftheMathematicalInstituteoftheHungarianAcademyofSciences,1960,5:17-61.

[4] Pastor-Satorras R,Vespignani A.Epidemic Spreading in Scale-free Networks[J].PhysicalReviewLetters,2000,86(14):3200.DOI:10.1103/PhysRevLett.86.3200.

[5] 史定華.網(wǎng)絡(luò)度分布理論[M].北京：高等教育出版社,2011.

[6] Newman M E J,Strogatz S H,Watts D J.Random Graphs with Arbitrary Degree Distributions and Their Applications[J].PhysicalReviewE,2001,64(2):026118.DOI:10.1103/PhysRevE.64.026118.

[7] Keeling M J.The Effects of Local Spatial Structure on Epidemiological Invasions[J].ProceedingsoftheRoyalSocietyofLondonB:BiologicalSciences,1999,266(1421):859-867.DOI:10.1098/rspb.1999.0716.

[8] House T,Keeling M J.Insights from Unifying Modern Approximations to Infections on Networks[J].PhysicalReviewDParticles&Fields,2011,8(54):67-73.DOI:10.1098/rsif.2010.0179.

[9] Watts D J,Strogatz S H.Collective Dynamics of ‘small-world’ Networks[J].Nature,1998,393(6684):440-442.DOI:10.1038/30918.

[10] Bender E A,Canfield E R.The Asymptotic Number of Labeled Graphs with Given Degree Sequences[J].JournalofCombinatorialTheory,SeriesA,1978,24(3):296-307.DOI:10.1016/0097-3165(78)90059-6.

[11] Newman M E J.Random Graphs with Clustering[J].PhysicalReviewLetters,2009,103(5):058701.DOI:10.1103/PhysRevLett.103.058701.

[12] Morris,John A,Morris,etal.Representing Spatial Interactions in Simple Ecological Models[D].University of Warwick,1997.

[13] Rand D A.Correlation Equations and Pair Approximations for Spatial Ecologies[J].AdvancedEcologicalTheory:PrinciplesandApplications,1999,100.

[14] Trapman P.Reproduction Numbers for Epidemics on Networks using Pair Approximation[J].MathematicalBiosciences,2007,210(2):464-489.DOI:10.1016/j.mbs.2007.05.011.

[15] Eames K T D,Keeling M J.Modeling Dynamic and Network Heterogeneities in the Spread of Sexually Transmitted Diseases[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2002,99(20):13330-5.DOI:10.1073/pnas.202244299.

[16] Sharkey K J,Fernandez C,Morgan K L,etal.Pair-level Approximations to the Spatio-temporal Dynamics of Epidemics on Asymmetric Contact Networks[J].JournalofMathematicalBiology,2006,53(1):61-85.DOI:10.1007/s00285-006-0377-3.

[17] Matsuda H,Ogita N,Sasaki A,etal.Statistical Mechanics of Population The Lattice Lotka-Volterra Model[J].ProgressofTheoreticalPhysics,1992,88(6):1035-1049.DOI:10.1143/PTP.88.1035.

[18] Luo X F,Zhang X,Sun G Q,etal.Epidemical Dynamics of SIS Pair Approximation Models on Regular and Random Networks[J].PhysicaAStatisticalMechanics&ItsApplications,2014,410(12):144-153.DOI:10.1016/j.physa.2014.05.020.

[19] Rattana P,Blyuss K B,Eames K T,etal.A Class of Pairwise Models for Epidemic Dynamics on Weighted Networks[J].BulletinofMathematicalBiology,2013,75(3):466.DOI:10.1007/s11538-013-9816-7.

[20] House T,Davies G,Danon L,etal.A Motif-Based Approach to Network Epidemics[J].BulletinofMathematicalBiology,2009,71(7):1693-1706.DOI:10.1007/s11538-009-9420-z.

[21] Kiss I Z,R?st G,Vizi Z.Generalization of Pairwise Models to non-Markovian Epidemics on Networks[J].PhysicalReviewLetters,2015,115(7):487-494.DOI:10.1103/PhysRevLett.115.078701.

[22] Sherborne N,Blyuss K B,Kiss I Z.Compact Pairwise Models for Epidemics with Multiple Infectious Stages on Degree Heterogeneous and Clustered Networks[J].JournalofTheoreticalBiology,2016,407:387-400.DOI:10.1016/j.jtbi.2016.07.015.

[23] Simon P L,Kiss I Z.Super Compact Pairwise Model for SIS Epidemic on Heterogeneous Networks[J].JournalofComplexNetworks,2016,4(2):187-200.DOI:10.1093/comnet/cnv018.

[24] Pei X,Zhan X X,Jin Z.Application of Pair Approximation Method to Modeling and Analysis of a Marriage Network[J].AppliedMathematics&Computation,2017,294:280-293.DOI:10.1016/j.amc.2016.09.010.

[25] Wang W,Tang M,Eugene S H,etal.Unification of Theoretical Approaches for Epidemic Spreading on Complex Networks[J].ReportsonProgressinPhysicsPhysicalSociety,2016,80(3):036603.DOI:10.1088/1361-6633/aa5398.

[26] Pastor-Satorras R,Vespignani A.Epidemic Dynamics and Endemic States in Complex Networks[J].PhysicalReviewE,2001,63(6):066117.DOI:10.1103/PhysRevE.63.066117.

[27] Moreno Y,Pastor-Satorras R,Vespignani A.Epidemic Outbreaks in Complex Heterogeneous Networks[J].TheEuropeanPhysicalJournalB,2002,26(4):521-529.DOI:10.1140/ejpb/e20020122.

[28] Jin Z,Sun G,Zhu H.Epidemic Models for Complex Networks with Demographics[J].MathematicalBiosciencesandEngineering,2014,11(6):1295-1317.DOI:10.3934/mbe.2014.11.1295.

[29] Masuda N,Konno N.Multi-state Epidemic Processes on Complex Networks[J].JournalofTheoreticalBiology,2006,243(1):64-75.DOI:10.1016/j.jtbi.2006.06.010.

[30] Wang J,Liu Z.Mean-field Level Analysis of Epidemics in Directed Networks[J].JournalofPhysicsAMathematical&Theoretical,2009,42(35):355001.DOI:10.1088/1751-8113/42/35/355001.

[32] Miller J C.A Note on a Paper by Erik Volz:SIR Dynamics in Random Networks[J].JournalofMathematicalBiology,2011,62(3):349-358.DOI:10.1007/s00285-010-0337-9.

[33] Miller J C,Slim A C,Volz E M.Edge-based Compartmental Modelling for Infectious Disease Spread[J].JournaloftheRoyalSocietyInterface,2012,9(70):890-906.DOI:10.1098/rsif.2011.0403.

[34] Volz E M,Miller J C,Galvani A,etal.Effects of Heterogeneous and Clustered Contact Patterns on Infectious Disease Dynamics[J].PlosComputationalBiology,2011,7(6):e1002042.DOI:10.1371/journal.pcbi.1002042.

[35] Rattana P,Miller J C,Kiss I Z.Pairwise and Edge-based Models of Epidemic Dynamics on Correlated Weighted Networks[J].MathematicalModellingofNaturalPhenomena,2011,9(2):58-81.DOI:10.1051/mmnp/20149204.DOI:10.1051/mmnp/20149204.

[36] Wang W,Tang M,Zhang H F,etal.Epidemic Spreading on Complex Networks with General Degree and Weight Distributions[J].PhysicalReviewE,2014,90(4-1):042803.DOI:10.1103/PhysRevE.90.042803.

[37] Millera J C,Slim A C.Modeling Disease Spread in Populations with Birth,Death,and Concurrency[J].arXivPreprintarXiv:1611.04800,2016.

[38] Miller J C.Mathematical Models of SIR Disease Spread with Combined Non-sexual and Sexual Transmission Routes[J].InfectiousDiseaseModelling,2017,2(1):35-55.DOI:10.1016/j.idm.2016.12.003.

[39] Van Mieghem P,Omic J,Kooij R.Virus Spread in Networks[J].IEEE/ACMTransactionsonNetworking(TON),2009,17(1):1-14.DOI:10.1109/TNET.2008.925623.

[40] Youssef M,Scoglio C.An Individual-based Approach to SIR Epidemics in Contact Networks[J].JournalofTheoreticalBiology,2011,283(1):136-144.DOI:10.1016/j.jtbi.2011.05.029.

[41] Sahneh F D,Scoglio C,Van Mieghem P.Generalized Epidemic Mean-field Model for Spreading Processes Over Multilayer Complex Networks[J].IEEE/ACMTransactionsonNetworking,2013,21(5):1609-1620.DOI:10.1109/TNET.2013.2239658.

[42] Yang L,Draief M,Yang X.Heterogeneous Virus Propagation in Networks:A Theoretical Study[J].MathematicalMethodsintheAppliedSciences,2017,40(5):1396-1413.DOI:10.1002/mma.4061.

[43] Yang L X,Draief M,Yang X.The Impact of the Network Topology on the Viral Prevalence:A Node-based Spproach[J].PloSOne,2015,10(7):e0134507.DOI:10.1371/journal.pone.0134507.

[44] Sahneh F D,Scoglio C.Epidemic Spread in Human Networks[C].Decision and Control and European Control Conference (CDC-ECC),2011:3008-3013.

[45] Sahneh F D,Chowdhury F N,Scoglio C M.On the Existence of a Threshold for Preventive Behavioral Responses to Suppress Epidemic Spreading[J].ScientificReports,2012,2:632.DOI:10.1038/srep00632.

[46] Liu J,Paré P E,Nedic＇A,etal.On the Analysis of a Continuous-time Bi-virus Model[C].Decision and Control (CDC),2016:290-295.

[47] Sahneh F D,Scoglio C.Competitive Epidemic Spreading Over Arbitrary Multilayer Networks[J].PhysicalReviewE,2014,89(6):062817.DOI:10.1103/PhysRevE.89.062817.

[48] Yang L X,Yang X,Wu Y.The Impact of Patch Forwarding on the Prevalence of Computer Virus:A Theoretical Assessment Approach[J].AppliedMathematicalModelling,2017,43:110-125.DOI:10.1016/j.apm.2016.10.028.

[49] Xu S,Lu W,Zhan Z.A Stochastic Model of Multivirus Dynamics[J].IEEETransactionsonDependableandSecureComputing,2012,9(1):30-45.DOI:10.1109/TDSC.2011.33.

[50] Xu S,Lu W,Xu L.Push-and Pull-based Epidemic Spreading in Networks:Thresholds and Deeper Insights[J].ACMTransactionsonAutonomousandAdaptiveSystems(TAAS),2012,7(3):32.DOI:10.1145/2348832.2348835.

[51] Xu S,Lu W,Xu L,etal.Adaptive Epidemic Dynamics in Networks:Thresholds and Control[J].ACMTransactionsonAutonomousandAdaptiveSystems(TAAS),2014,8(4):19.DOI:10.1145/2555613.

[52] Newman M E J.Networks:An Introduction[M].United Slates:Oxford University Press Inc.,New York,2010,1-2.

[53] Callaway D S,Newman M E J,Strogatz S H,etal.Network Robustness and Fragility:Percolation on Random Graphs[J].PhysicalReviewLetters,2000,85(25):5468.DOI:10.1103/PhysRevLett.85.5468.

[54] Cohen R,Havlin S,Ben-Avraham D.Efficient Immunization Strategies for Computer NetWorks and Populations[J].PhysicalReviewLetters,2003,91(24):247901.DOI:10.1103/PhysRevLett.91.247901.

[55] Newman M E J.Spread of Epidemic Disease on Networks[J].PhysicalReviewE,2002,66(1):016128.DOI:10.1103/PhysRevE.66.016128.

[56] 汪小帆,李翔,陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論[M].北京：高等教育出版社,2012，406：387-482.

[57] Albert R.Attack and Error Tolerance in Complex Networks[J].Nature,2000,406:387-482.

[58] Kenah E,Robins J M.Second Look at the Spread of Epidemics on Networks[J].PhysicalReviewE,2007,76(3):036113.DOI:10.1103/PhysRevE.76.036113.

[59] Miller J C.Epidemic Size and Probability in Populations with Heterogeneous Infectivity and Susceptibility[J].PhysicalReviewE,2007,76(1):010101.DOI:10.1103/PhysRevE.76.010101.

[60] Serrano M,Boguna M.Clustering in Complex Networks.I.General Formalism[J].PhysicalReviewE,2006,74(5):056114.DOI:10.1103/PhysRevE.74.056114.

[61] Newman M E J.Properties of Highly Clustered[J].PhysicalReviewE,2003,68(2):026121.

[62] Miller J C.Percolation and Epidemics in Random Clustered Networks[J].PhysicalReviewE,2009,80(2):020901.DOI:10.1103/PhysRevE.80.020901.

[63] Gleeson J P,Melnik S,Hackett A.How Clustering Affects the Bond Percolation Threshold in Complex Networks[J].PhysicalReviewE.81,2010,066114.DOI:10.1103/PhysRevE.81.066114.

[64] 李淑萍.網(wǎng)絡(luò)拓撲結(jié)構(gòu)對傳播的影響研究[D].太原：中北大學(xué),2015.

[65] Pan W,Sun G Q,Jin Z.How Demography-driven Evolving Networks Impact Epidemic Transmission Between Communities[J].JournalofTheoreticalBiology,2015,382:309-319.

[66] 張曉光.網(wǎng)絡(luò)拓撲結(jié)構(gòu)與傳播動力學(xué)分析[D].太原：中北大學(xué),2014.

Advances in Spreading Dynamics Research on Complex Networks

JIN Zhen1,2，LUO Xiaofeng1,3

(1.Complex System Research Center,Shanxi University,Taiyuan,Shanxi 030006,China;2.Shanxi Key Laboratory of Methods of Disease Prevention and Control and Big Data analysis, Shanxi University,Taiyuan,Shanxi 030006, China;3.School of Computer and Information Technology, Shanxi University, Taiyuan, Shanxi 030006,China)

Information or epidemic spread on networks is one of the hot issues in complex network research fields. It is a coupled dynamic process of diseases propagation and network evolution which depends on not only the transmission characteristics of information or epidemics themselves but also network structure and evolution, resulting in very complicated dynamic phenomena. The paper mainly focuses on some basic concepts, modelling and studying methods in respect to spreading dynamics on complex networks, containing 4 kinds of dynamic models——pair-based, degree-based, node-based and percolation theory-based models——and some advances in dynamic modelling and analyzing respects on complex networks.

complex networks;pair approximation;adjacent matrix;edge compartment;percolation theory

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.03.006

2017-06-14；

2017-06-25

國家自然科學(xué)基金重點項目(11331009)；國家自然科學(xué)基金面上項目(11501340；11301491)；山西省回國留學(xué)人員科研資助項目(2014-020)；山西大學(xué)人才引進項目

靳禎(1965-)，男，博士生導(dǎo)師，教授，研究方向：生物動力學(xué)系統(tǒng)，復(fù)雜網(wǎng)絡(luò)傳播動力學(xué)等。E-mail:jinzhn@263.net

O175

A

0253-2395(2017)03-0426-16