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

楊關玲，楊鑫松

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

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

楊關玲，楊鑫松

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

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

復雜網絡；流行病傳播；淬火平均場

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

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

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

1 理論分析

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

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

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

(1)

其中，N為網絡中節點個數。節點從S態變為I態，導致I態節點比例增加；I態節點恢復成R態使得I態節點比例減少。不難得出ρi(t)的耦合方程組為

(2)

類似地，可以得到

(3)

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

在初始時刻，只有少許節點處于感染態和恢復態。因此，當t→0時，可以近似地看作式(2)變為

(4)

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

(5)

(6)

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

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

(7)

(8)

為復雜網絡上的流行病爆發閾值。

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

圖1 ER網絡上疾病傳播范圍隨傳播率的變化

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

(9)

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

2 實驗模擬

圖2 SF網絡上疾病傳播范圍隨傳播率的變化

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

圖3 真實網絡中疾病傳播范圍隨傳播率的變化

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

3 結論

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

淬火平均場理論方法是研究復雜網絡上傳播動力學的重要工具之一。然而，該理論雖然考慮了網絡的拓撲結構，卻仍然忽略了動力學關聯性。因此，在以后的工作中需要建立更加完善的理論框架來研究復雜網絡上的傳播動力學，并考慮網絡的淬火特性所帶來的動力學關聯性。

[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]馬知恩, 周義倉, 王穩地, 等. 傳染病動力學的數學建模與研究[M]. 北京: 科學出版社，2004: 150-200.

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

[8] 傅新楚, Michael S, 陳關榮. 復雜網絡傳播動力學——模型、方法與穩定性分析[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-)，女，重慶巫溪人，碩士研究生，主要研究方向為復雜網絡傳播動力學。

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

N945.12;N94

A