淬火平均場方法的有效性分析

楊關(guān)玲，楊鑫松

(重慶師范大學(xué)數(shù)學(xué)學(xué)院，重慶 401331)

淬火平均場方法的有效性分析

楊關(guān)玲，楊鑫松

(重慶師范大學(xué)數(shù)學(xué)學(xué)院，重慶 401331)

對淬火平均場方法求解爆發(fā)閾值的有效性進(jìn)行分析，利用淬火平均場研究ER網(wǎng)絡(luò)、SF網(wǎng)絡(luò)和實(shí)證網(wǎng)絡(luò)上的SIR傳播，發(fā)現(xiàn)當(dāng)鄰接矩陣的最大特征值所對應(yīng)的特征向量為非局域特征向量時(shí)，淬火平均場得到的理論閾值與真實(shí)閾值能較好地吻合；否則，理論閾值低于真實(shí)閾值。

復(fù)雜網(wǎng)絡(luò)；流行病傳播；淬火平均場

網(wǎng)絡(luò)科學(xué)是研究許多自然和社會(huì)現(xiàn)象的重要工具之一。在過去的十多年中，對社會(huì)網(wǎng)絡(luò)的研究取得了輝煌的成果?？偟膩碚f，這些研究可以分為網(wǎng)絡(luò)動(dòng)力學(xué)和網(wǎng)絡(luò)上的動(dòng)力學(xué)。前者主要是指網(wǎng)絡(luò)演化，主要典型代表為小世界網(wǎng)絡(luò)模型(WS模型和NS模型)、BA模型；對于后者，其研究成果更為豐富，比如滲流、級聯(lián)失效、同步、博弈以及傳播等[1-2]。

復(fù)雜網(wǎng)絡(luò)上的流行病傳播一直以來是人們研究的熱點(diǎn)課題之一[3-8]。一般來說，對流行病的傳播主要關(guān)注其爆發(fā)閾值和傳播范圍。在復(fù)雜網(wǎng)絡(luò)中，Pastor-Satorras和Vespignani首次利用異質(zhì)平均場研究了復(fù)雜網(wǎng)絡(luò)上的流行病傳播[9]。他們發(fā)現(xiàn)由于中心節(jié)點(diǎn)的存在，在熱力學(xué)極限下，任意的疾病傳播率都會(huì)導(dǎo)致流行病的爆發(fā)[9-10]。異質(zhì)平均場假設(shè)相同度的節(jié)點(diǎn)在網(wǎng)絡(luò)中所處的地位完全相同，這在一定程度上忽略了網(wǎng)絡(luò)的淬火特性。為了能最大程度上反映出網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對傳播動(dòng)力學(xué)的影響，Wang等[9]利用淬火平均場對復(fù)雜網(wǎng)絡(luò)上的傳播動(dòng)力學(xué)進(jìn)行了研究，發(fā)現(xiàn)疾病的爆發(fā)閾值為網(wǎng)絡(luò)鄰接矩陣的最大特征值的倒數(shù)。此后，淬火平均場成為研究復(fù)雜網(wǎng)絡(luò)上傳播動(dòng)力學(xué)的重要工具之一[11-12]。然而，據(jù)我們所知，還未曾有文獻(xiàn)專門研究利用淬火平均場所得的SIR(Susceptible-Infected-Recovered)[10]流行病傳播理論閾值的有效性。

鑒于此，在本文中將對此問題詳細(xì)分析，首先利用淬火平均場理論分析復(fù)雜網(wǎng)絡(luò)上的SIR傳播，發(fā)現(xiàn)在某些情況下根據(jù)淬火平均場理論得出的疾病爆發(fā)閾值能很好地對應(yīng)真實(shí)閾值，而在某些情況下并不能很好地對應(yīng)真實(shí)閾值。然后，利用特征向量參與反比率來刻畫該特征向量是否為局域特征向量。通過分析ER網(wǎng)絡(luò)[13]、SF網(wǎng)絡(luò)[14]以及真實(shí)網(wǎng)絡(luò)上的SIR流行病傳播，發(fā)現(xiàn)當(dāng)鄰接矩陣的最大特征值所對應(yīng)的特征向量為非局域特征向量時(shí)，淬火平均場理論所得到的疾病爆發(fā)閾值與真實(shí)閾值能較好地吻合；相反，特征向量的局域性越強(qiáng)，淬火平均場越難以描述復(fù)雜網(wǎng)絡(luò)上的流行病爆發(fā)閾值。

1 理論分析

在本文中采用SIR流行病傳播模型，每個(gè)節(jié)點(diǎn)在任意時(shí)刻只能處于易感態(tài)(S態(tài))、感染態(tài)(I態(tài))和恢復(fù)態(tài)(R態(tài))中的一種狀態(tài)。每個(gè)I態(tài)節(jié)點(diǎn)嘗試感染它的每個(gè)鄰居節(jié)點(diǎn)，若鄰居節(jié)點(diǎn)處于S態(tài)，則以概率β變?yōu)镮態(tài)。與此同時(shí)，每個(gè)I態(tài)節(jié)點(diǎn)也會(huì)以概率γ恢復(fù)成R態(tài)。節(jié)點(diǎn)一旦變?yōu)镽態(tài)，它在后續(xù)的傳播過程中將一直處于R態(tài)。當(dāng)網(wǎng)絡(luò)中不存在I態(tài)節(jié)點(diǎn)時(shí)，傳播過程結(jié)束。不失一般性，本文假設(shè)恢復(fù)概率γ=1.0。上述模型即為經(jīng)典的SIR流行病傳播模型[10]。對于復(fù)雜網(wǎng)絡(luò)上SIR流行病的研究已有很多，這些研究主要關(guān)注流行病何時(shí)爆發(fā)以及爆發(fā)范圍。

對于SIR模型，每個(gè)節(jié)點(diǎn)在t時(shí)刻都為一個(gè)隨機(jī)變量Xi(t)∈{0,1,2}。Xi(t)=0表示節(jié)點(diǎn)處于易感態(tài)，Xi(t)=1為節(jié)點(diǎn)處于感染態(tài)，Xi(t)=2表示節(jié)點(diǎn)處于恢復(fù)態(tài)。記si(t)=Pr[Xi(t)=0]為節(jié)點(diǎn)處于S態(tài)的概率，ρi(t)=Pr[Xi(t)=1]為節(jié)點(diǎn)處于I態(tài)的概率，ri(t)=Pr[Xi(t)=2]為節(jié)點(diǎn)處于恢復(fù)態(tài)的概率。用鄰接矩陣A表示整個(gè)網(wǎng)絡(luò)，Aij=1表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間存在一條連邊；否則，Aij=0。

對于節(jié)點(diǎn)被疾病i感染，則意味著它至少有一個(gè)鄰居節(jié)點(diǎn)j被疾病感染。在很小時(shí)間區(qū)間內(nèi)dt，節(jié)點(diǎn)被感染的概率為βsi(t)∑jAijρj(t)dt。根據(jù)動(dòng)力學(xué)機(jī)制，si(t)遵循N個(gè)非線性耦合方程組[15]

(1)

其中，N為網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)。節(jié)點(diǎn)從S態(tài)變?yōu)镮態(tài)，導(dǎo)致I態(tài)節(jié)點(diǎn)比例增加；I態(tài)節(jié)點(diǎn)恢復(fù)成R態(tài)使得I態(tài)節(jié)點(diǎn)比例減少。不難得出ρi(t)的耦合方程組為

(2)

類似地，可以得到

(3)

式(1)～(3)描述了復(fù)雜網(wǎng)絡(luò)上的SIR流行病傳播模型。

在初始時(shí)刻，只有少許節(jié)點(diǎn)處于感染態(tài)和恢復(fù)態(tài)。因此，當(dāng)t→0時(shí)，可以近似地看作式(2)變?yōu)?/p>

(4)

將式(4)寫成矩陣形式為

(5)

(6)

其中，Λr為矩陣A的第r個(gè)特征值，vr為其與之所對應(yīng)的特征向量，αr(0)為常系數(shù)。進(jìn)一步研究等式(6)，Φ的漸近增長形式為

Φ～α1(0)v1e(βΛr-γ)t

(7)

(8)

為復(fù)雜網(wǎng)絡(luò)上的流行病爆發(fā)閾值。

通過式(8)，我們便能容易地確定出復(fù)雜網(wǎng)絡(luò)上的流行病爆發(fā)閾值與網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)之間的關(guān)系。圖1給出了在ER網(wǎng)絡(luò)上的流行病傳播范圍隨傳播率β的變化圖。圖中，采用網(wǎng)絡(luò)規(guī)模N=10 001，前10 000個(gè)節(jié)點(diǎn)所構(gòu)成的網(wǎng)絡(luò)平均度為8，最后一個(gè)節(jié)點(diǎn)的度為m。在1 000個(gè)不同的網(wǎng)絡(luò)上進(jìn)行模擬實(shí)驗(yàn)，每個(gè)網(wǎng)絡(luò)上重復(fù)2 000次取平均值。在圖中圓圈為實(shí)驗(yàn)?zāi)M值，上三角為根據(jù)式(8)所得出的疾病爆發(fā)閾值。從圖中不難發(fā)現(xiàn)當(dāng)m=8時(shí)，式(8)能很好地對應(yīng)疾病爆發(fā)閾值。然而，當(dāng)m越大，根據(jù)式(8)所得到的疾病爆發(fā)閾值越低于疾病爆發(fā)的真實(shí)閾值。我們將進(jìn)一步研究是什么原因?qū)е铝耸?8)不再是流行病爆發(fā)閾值。

圖1 ER網(wǎng)絡(luò)上疾病傳播范圍隨傳播率的變化

從式(7)中發(fā)現(xiàn)，新增感染節(jié)點(diǎn)數(shù)量不僅僅與最大特征值相關(guān)，還與特征向量呈線性關(guān)系。為了研究Φ隨時(shí)間的變化情況，將討論最大特征值所對應(yīng)的特征向量是否為局域特征值向量，并采用參與反比率[16-17]

(9)

進(jìn)行描述。在熱力學(xué)極限下，則特征值Λ所對應(yīng)的特征向量v為局域特征向量。對于局域特征向量，其分量主要局限于網(wǎng)絡(luò)中的少許節(jié)點(diǎn)。對于非局域特征向量，通常的值IPR(Λ)非常小。根據(jù)式(9)計(jì)算得出m=8,800,400和800時(shí)，它們的最大特征值Λ1所對應(yīng)的IPR(Λ1)分別為0.000 17，0.088 7，0.230 9和0.236 1。不難發(fā)現(xiàn)，m越大，IPR(Λ1)越大，最大特征值所對應(yīng)的特征向量的分量局限于少許大度節(jié)點(diǎn)，最終導(dǎo)致式(8)不能很好地刻畫網(wǎng)絡(luò)的疾病爆發(fā)閾值。因此，不難發(fā)現(xiàn)當(dāng)特征向量為局域特征向量時(shí)，式(8)所得的理論閾值小于疾病爆發(fā)的真實(shí)閾值。

2 實(shí)驗(yàn)?zāi)M

圖2 SF網(wǎng)絡(luò)上疾病傳播范圍隨傳播率的變化

根據(jù)式(1)～(3)所描述的SIR傳播動(dòng)力學(xué)，完全描述了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，只是忽略了動(dòng)力學(xué)關(guān)聯(lián)性[20]。式(8)在某些實(shí)證網(wǎng)絡(luò)中能反應(yīng)出SIR疾病爆發(fā)閾值。Astro網(wǎng)絡(luò)和Hamster網(wǎng)絡(luò)[21]的鄰接矩陣最大特征值所對應(yīng)的特征向量的參與反比率分別為0.005和0.009， 從圖3a和圖3b中不難發(fā)現(xiàn)式(8)能較好地反應(yīng)疾病爆發(fā)閾值。然而，在AS網(wǎng)絡(luò)和Facebook網(wǎng)絡(luò)[21]中，鄰接矩陣的最大特征值的倒數(shù)不能很好地反映疾病爆發(fā)閾值。因?yàn)?，它們的鄰接矩陣的最大特征值所對?yīng)的特征向量的參與反比率分別為0.087和0.244。在表格1中對這4個(gè)實(shí)證網(wǎng)絡(luò)的統(tǒng)計(jì)特性進(jìn)行了詳細(xì)的介紹。其中，N為網(wǎng)絡(luò)規(guī)模，即節(jié)點(diǎn)數(shù)量，kmax為節(jié)點(diǎn)的最大度，根據(jù)式(8)所得到的疾病爆發(fā)閾值和根據(jù)式(9)所得的最大特征值所對應(yīng)的最大特征向量的參與反比率IPR。

圖3 真實(shí)網(wǎng)絡(luò)中疾病傳播范圍隨傳播率的變化

Nkmax1/ΛI(xiàn)PRAstro148453600.0140.005Hamster20002730.0200.009As647414580.0220.087Facebook28887690.0360.244

3 結(jié)論

在本文中，通過大量的實(shí)驗(yàn)?zāi)M和理論分析對淬火平均場理論方法求解SIR流行病傳播進(jìn)行了深入研究。在ER網(wǎng)絡(luò)、SF網(wǎng)絡(luò)以及真實(shí)網(wǎng)絡(luò)中，發(fā)現(xiàn)只有當(dāng)鄰接矩陣的最大特征值所對應(yīng)的特征性向量為非局域特征向量時(shí)，淬火平均場才能很好地描述傳播動(dòng)力學(xué)；相反，由于局域特征向量的存在，使得淬火平均場理論在此情況下不能描述復(fù)雜網(wǎng)絡(luò)上的傳播動(dòng)力學(xué)。這一發(fā)現(xiàn)不僅僅能促使對淬火平均場理論本身的認(rèn)識，還有助于日后研究復(fù)雜網(wǎng)絡(luò)上的傳播動(dòng)力學(xué)。

淬火平均場理論方法是研究復(fù)雜網(wǎng)絡(luò)上傳播動(dòng)力學(xué)的重要工具之一。然而，該理論雖然考慮了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，卻仍然忽略了動(dòng)力學(xué)關(guān)聯(lián)性。因此，在以后的工作中需要建立更加完善的理論框架來研究復(fù)雜網(wǎng)絡(luò)上的傳播動(dòng)力學(xué)，并考慮網(wǎng)絡(luò)的淬火特性所帶來的動(dòng)力學(xué)關(guān)聯(lián)性。

[1]Albert R,Barabási A L. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002,74: 0034-6861.

[2]Dorogovtsev S N, Goltsev A V, Mendes J F F.Critical phenomena in complex networks[J]. Reviews of Modern Physics，2008,80(4): 0034-6861.

[3]馬知恩, 周義倉, 王穩(wěn)地, 等. 傳染病動(dòng)力學(xué)的數(shù)學(xué)建模與研究[M]. 北京: 科學(xué)出版社，2004: 150-200.

[4] 李翔, 劉宗華, 汪秉宏. 網(wǎng)絡(luò)傳播動(dòng)力學(xué)[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2010, 7(2/3): 1672-3813. Li Xiang，Liu Zonghua，Wang Binghong. On spreading dynamics on networks [J].Complex Systems and Complexity Science, 2010, 7(2/3): 1672-3813.

[5] Keeling M, Rohani P. Modeling Infectious Diseases in Humans and Animals[M]. Princeton: Princeton University Press, 2007: 150-170.

[6] 張海峰, 王陽陽, 汪秉宏. 行為反應(yīng)對復(fù)雜網(wǎng)絡(luò)上傳染病動(dòng)力學(xué)的影響[J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2012, 9(3): 13-21. Zhang Haifeng, Wang Yangyang, Wang Binghong. The impacts of behavioral responses on the spread of infectious diseases on complex networks [J].Complex Systems and Complexity Science, 2012, 9(3):13-21.

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

[8] 傅新楚, Michael S, 陳關(guān)榮. 復(fù)雜網(wǎng)絡(luò)傳播動(dòng)力學(xué)——模型、方法與穩(wěn)定性分析[M]. 北京: 高等教育出版社, 2014: 230-260.

[9] Pastor-Satorras R, Vespignani A.Epidemic spreading in scale-free networks [J]. Phys Rev Lett, 2001, 86(14): 3200.

[10] Moreno Y, Pastor-Satorras R, Vespignani A. Epidemic outbreaks in complex heterogeneous networks[J]. Eur Phys J B, 2002, 26, 521-529.

[11] Wang Y, Chakrabarti D, Wang C X, et al. Epidemic spreading in real networks: an eigenvalue view point [J]. Computer Science Department,2003, 9(1):544.

[12] Van Mieghem P. Epidemic phase transition of the SIS type in networks [J]. Europhys Lett, 2012, 97: 48004.

[13] Erdos P, Renyi. On random graphs [J].Publ Math,1959,6:290-297.

[14] Newman M E J. Power laws, Pareto distributions and Zipf’slaw [J].Contemp Phys, 2005,46:323-351.

[15] Van Mieghem P. Virus spread in networks[J]. IEEE/ACM Transactions on Networking, 2009, 17(1), 1063-6692.

[16] Goltsev A V, Dorogovtsev S N, Oliveira J G, et al. Localization and spreading of diseases in complex networks [J]. Phys Rev Lett, 2012, 109:128702.

[17] Martin T, Zhang X, Newman M E J. Localization and centrality in networks[DB/OL]. [2014-02-20].http://www.researchgate. net/publication/259824255_Localization_and_centrality_in networks.

[18] Catanzaro M, Boguá M, Pastor-Satorras R. Generation of uncorrelated random scale-free networks [J]. Phys Rev E, 2005,71(2): 027103.

[19] Newman M E J, Strogatz S H, Watts D J. Random graphs with arbitrary degree distributions and their applications [J]. Phys Rev E, 2001, 64(2):026118.

[20] 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 [J]. Phys Rev E, 2012, 86(4): 041125.

[21] Networks [DB/OL]. [2014-02-20].http://konect.uni-koblenz.de/networks.

(責(zé)任編輯 李進(jìn))

Analyzing the Validity of Quenched Mean-Field Method

YANG Guanling, YANG Xinsong

(Department of Mathematics, Chongqing Normal University, Chongqing 401331)

We investigate the validation of the threshold predicated by the quenched mean-field theory. By using quenched mean-filed theory, we analyze SIR epidemic spreading models on ER networks, SF networks, and real networks. We find that when the eigenvector of the leading eigenvalue of the adjacent matrix is delocalized, the threshold predicated by this theoretical approach can basically fit its real threshold, and that once the leading eigenvector is localized, the theoretical threshold is lower than its actual threshold.

complex networks; epidemic spreading; quenched mean-field theory

1672-3813(2015)04-0032-04;

10.13306/j.1672-3813.2015.04.004

2014-04-01；

2014-08-10

國家自然科學(xué)基金(61263020)

楊關(guān)玲(1988-)，女，重慶巫溪人，碩士研究生，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)傳播動(dòng)力學(xué)。

楊鑫松(1968-)，男，湖南懷化人，碩士，教授，主要研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)隨機(jī)動(dòng)力系統(tǒng)，右端不連續(xù)動(dòng)力系統(tǒng)，混沌同步與控制，脈沖微分方程等。

N945.12;N94

A