楊關玲，楊鑫松

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

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

楊關玲，楊鑫松

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

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

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

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

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

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

1 理論分析

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

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

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

(1)

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

(2)

類似地，可以得到

(3)

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

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

(4)

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

(5)

(6)

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

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

(7)

(8)

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

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

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

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

(9)

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

2 實驗模擬

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

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

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

Nkmax1/ΛIPRAstro148453600.0140.005Hamster20002730.0200.009As647414580.0220.087Facebook28887690.0360.244

3 結(jié)論

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

淬火平均場理論方法是研究復雜網(wǎng)絡上傳播動力學的重要工具之一。然而，該理論雖然考慮了網(wǎng)絡的拓撲結(jié)構(gòu)，卻仍然忽略了動力學關聯(lián)性。因此，在以后的工作中需要建立更加完善的理論框架來研究復雜網(wǎng)絡上的傳播動力學，并考慮網(wǎng)絡的淬火特性所帶來的動力學關聯(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)地, 等. 傳染病動力學的數(shù)學建模與研究[M]. 北京: 科學出版社，2004: 150-200.

[4] 李翔, 劉宗華, 汪秉宏. 網(wǎng)絡傳播動力學[J]. 復雜系統(tǒng)與復雜性科學, 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] 張海峰, 王陽陽, 汪秉宏. 行為反應對復雜網(wǎng)絡上傳染病動力學的影響[J]. 復雜系統(tǒng)與復雜性科學, 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] 汪小帆, 李翔, 陳關榮. 網(wǎng)絡科學導論[M]. 北京: 高等教育出版社, 2012: 220-300.

[8] 傅新楚, Michael S, 陳關榮. 復雜網(wǎng)絡傳播動力學——模型、方法與穩(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.

(責任編輯 李進)

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

國家自然科學基金(61263020)

楊關玲(1988-)，女，重慶巫溪人，碩士研究生，主要研究方向為復雜網(wǎng)絡傳播動力學。

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

N945.12;N94

A