復(fù)雜網(wǎng)絡(luò)的同步能力與傳播動(dòng)力學(xué)性態(tài)

1、傅新楚，朱杰傅新楚，朱杰 （上海大學(xué)理學(xué)院，上海（上海大學(xué)理學(xué)院，上海 200444） 2010第六屆全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議第六屆全國(guó)復(fù)雜網(wǎng)絡(luò)學(xué)術(shù)會(huì)議 ，蘇州大學(xué)，蘇州大學(xué)，2010年年10月月15-18日日 摘摘 要要 本文首先從無(wú)標(biāo)度網(wǎng)絡(luò)構(gòu)造方式的區(qū)別開始，討論了本文首先從無(wú)標(biāo)度網(wǎng)絡(luò)構(gòu)造方式的區(qū)別開始，討論了 網(wǎng)絡(luò)在不同結(jié)構(gòu)下的同步性和魯棒性；隨后，討論了網(wǎng)絡(luò)在不同結(jié)構(gòu)下的同步性和魯棒性；隨后，討論了 傳染病在無(wú)標(biāo)度網(wǎng)絡(luò)上的傳染病閾值，以及在各種不傳染病在無(wú)標(biāo)度網(wǎng)絡(luò)上的傳染病閾值，以及在各種不 同免疫的條件下閾值的變化情況，并描述了在網(wǎng)絡(luò)同同免疫的條件下閾值的變化情況，并描述了在網(wǎng)絡(luò)同 步的

2、情況下傳染病的傳播動(dòng)力學(xué)性態(tài)。該文還步的情況下傳染病的傳播動(dòng)力學(xué)性態(tài)。該文還重點(diǎn)解重點(diǎn)解 決決了了Physical Review E, 77 (2008) 036113一文中的一文中的 兩個(gè)遺留數(shù)學(xué)問題，嚴(yán)格證明了不同免疫條件下閾值兩個(gè)遺留數(shù)學(xué)問題，嚴(yán)格證明了不同免疫條件下閾值 比較的兩個(gè)不等式。比較的兩個(gè)不等式。 關(guān)鍵詞：關(guān)鍵詞：無(wú)標(biāo)度網(wǎng)絡(luò)，網(wǎng)絡(luò)同步，傳染病閾值，免疫控制，同步傳播無(wú)標(biāo)度網(wǎng)絡(luò)，網(wǎng)絡(luò)同步，傳染病閾值，免疫控制，同步傳播 Xinchu Fu, Jie Zhu （College of Sciences, Shanghai University, Shanghai 200444, C

3、hina） ABSTRACT: This paper discusses the different constructions of scale-free networks, then considers synchronization and robustness for networks with different topology structures. It then estimates epidemic thresholds for disease spreading on scale-free networks, and their variance under differe

4、nt immunization strategies. Finally, the interaction between spreading behavior of diseases and network synchronization is studied. And it also focus on solving two mathematical problems left behind in Physical Review E, 77 (2008) 036113 by proving the related two inequalities for the comparison of

5、epidemic thresholds. Key words: Scale-free networks; network synchronization; epidemic thresholds; immunization; spreading. 網(wǎng)絡(luò)分類網(wǎng)絡(luò)分類 v規(guī)則網(wǎng)絡(luò)規(guī)則網(wǎng)絡(luò): 規(guī)則網(wǎng)絡(luò)具有很強(qiáng)規(guī)則性，例如全連接網(wǎng)絡(luò)，規(guī)則網(wǎng)絡(luò)具有很強(qiáng)規(guī)則性，例如全連接網(wǎng)絡(luò)， 環(huán)形，鏈形，星形網(wǎng)絡(luò)以及格點(diǎn)和分形圖等環(huán)形，鏈形，星形網(wǎng)絡(luò)以及格點(diǎn)和分形圖等 v隨機(jī)網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò):隨機(jī)網(wǎng)絡(luò)是指按照某種明確的統(tǒng)計(jì)規(guī)律生成隨機(jī)網(wǎng)絡(luò)是指按照某種明確的統(tǒng)計(jì)規(guī)律生成 的網(wǎng)絡(luò)，與規(guī)則網(wǎng)絡(luò)相對(duì)應(yīng)，主要是經(jīng)典的隨機(jī)圖模型的網(wǎng)絡(luò)

6、，與規(guī)則網(wǎng)絡(luò)相對(duì)應(yīng)，主要是經(jīng)典的隨機(jī)圖模型 及其派生出來的相關(guān)模型及其派生出來的相關(guān)模型 v小世界網(wǎng)絡(luò)小世界網(wǎng)絡(luò): 主要有主要有WS改邊小世界網(wǎng)絡(luò)和改邊小世界網(wǎng)絡(luò)和NW加邊小世加邊小世 界網(wǎng)絡(luò)界網(wǎng)絡(luò) v無(wú)標(biāo)度網(wǎng)絡(luò)無(wú)標(biāo)度網(wǎng)絡(luò)：BA無(wú)標(biāo)度網(wǎng)絡(luò)是第一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)。我無(wú)標(biāo)度網(wǎng)絡(luò)是第一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)。我 們將主要討論此類網(wǎng)絡(luò)上的同步與傳播問題們將主要討論此類網(wǎng)絡(luò)上的同步與傳播問題 v可導(dǎo)航網(wǎng)絡(luò)可導(dǎo)航網(wǎng)絡(luò) 網(wǎng)絡(luò)同步與傳播動(dòng)力學(xué)網(wǎng)絡(luò)同步與傳播動(dòng)力學(xué) 復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)的特點(diǎn)：復(fù)雜網(wǎng)絡(luò)動(dòng)力學(xué)的特點(diǎn)： v網(wǎng)絡(luò)規(guī)模大，結(jié)構(gòu)復(fù)雜網(wǎng)絡(luò)規(guī)模大，結(jié)構(gòu)復(fù)雜; v節(jié)點(diǎn)之間的連接方式多樣，如，方向可以不節(jié)點(diǎn)之間的連接方式多樣，如，方

7、向可以不 同，權(quán)重也可以不同同，權(quán)重也可以不同; v網(wǎng)絡(luò)具有時(shí)空復(fù)雜性，節(jié)點(diǎn)之間的復(fù)雜相互網(wǎng)絡(luò)具有時(shí)空復(fù)雜性，節(jié)點(diǎn)之間的復(fù)雜相互 作用可導(dǎo)致同步、復(fù)雜的傳播行為等作用可導(dǎo)致同步、復(fù)雜的傳播行為等; v復(fù)雜網(wǎng)絡(luò)科學(xué)有著廣闊的應(yīng)用前景。復(fù)雜網(wǎng)絡(luò)科學(xué)有著廣闊的應(yīng)用前景。 兩種同步網(wǎng)絡(luò)的構(gòu)造兩種同步網(wǎng)絡(luò)的構(gòu)造 v同步最優(yōu)網(wǎng)絡(luò)：同步最優(yōu)網(wǎng)絡(luò)： 新加入節(jié)點(diǎn)的連接方式與網(wǎng)絡(luò)中節(jié)點(diǎn)的度新加入節(jié)點(diǎn)的連接方式與網(wǎng)絡(luò)中節(jié)點(diǎn)的度 有關(guān)，需要注意的是，在同步最優(yōu)網(wǎng)絡(luò)生成的過程中，只是有關(guān)，需要注意的是，在同步最優(yōu)網(wǎng)絡(luò)生成的過程中，只是 在每條新邊加入時(shí)網(wǎng)絡(luò)的同步化性能達(dá)到最優(yōu)，并不能保證在每條新邊加入時(shí)網(wǎng)絡(luò)的同步化性能

8、達(dá)到最優(yōu)，并不能保證 最終得到的整個(gè)網(wǎng)絡(luò)的同步特性達(dá)到全局最優(yōu)。這種同步最最終得到的整個(gè)網(wǎng)絡(luò)的同步特性達(dá)到全局最優(yōu)。這種同步最 優(yōu)網(wǎng)絡(luò)有極少量的節(jié)點(diǎn)與大量節(jié)點(diǎn)相連接，而其余大部分節(jié)優(yōu)網(wǎng)絡(luò)有極少量的節(jié)點(diǎn)與大量節(jié)點(diǎn)相連接，而其余大部分節(jié) 點(diǎn)的連接度數(shù)則很低。因此該網(wǎng)絡(luò)同步化性能比無(wú)標(biāo)度網(wǎng)絡(luò)點(diǎn)的連接度數(shù)則很低。因此該網(wǎng)絡(luò)同步化性能比無(wú)標(biāo)度網(wǎng)絡(luò) 強(qiáng)，但在惡意攻擊下容易被破壞。強(qiáng)，但在惡意攻擊下容易被破壞。 v同步優(yōu)先網(wǎng)絡(luò)：新節(jié)點(diǎn)連接概率與得到的網(wǎng)絡(luò)的同步化性能同步優(yōu)先網(wǎng)絡(luò)：新節(jié)點(diǎn)連接概率與得到的網(wǎng)絡(luò)的同步化性能 成正比，它的連接度分布既不服從冪律分布又不服從指數(shù)分成正比，它的連接度分布既不服從冪律分布

9、又不服從指數(shù)分 布，具有很強(qiáng)的魯棒性。布，具有很強(qiáng)的魯棒性。 v理論分析理論分析 傳播動(dòng)力學(xué)傳播動(dòng)力學(xué) v在在SIS傳染病模型中存在一個(gè)傳染病閾值傳染病模型中存在一個(gè)傳染病閾值 ,當(dāng)傳染當(dāng)傳染 率大于該值時(shí)，感染個(gè)體能夠?qū)⒉《緜鞑U(kuò)散并使得率大于該值時(shí)，感染個(gè)體能夠?qū)⒉《緜鞑U(kuò)散并使得 整個(gè)網(wǎng)絡(luò)感染個(gè)體總數(shù)最終穩(wěn)定于某一平穩(wěn)狀態(tài)，此整個(gè)網(wǎng)絡(luò)感染個(gè)體總數(shù)最終穩(wěn)定于某一平穩(wěn)狀態(tài)，此 時(shí)稱網(wǎng)絡(luò)處于激活相態(tài)時(shí)稱網(wǎng)絡(luò)處于激活相態(tài) ；如果有效傳播率低于此臨；如果有效傳播率低于此臨 界值，則感染個(gè)體數(shù)呈指數(shù)衰減，無(wú)法大范圍傳播，界值，則感染個(gè)體數(shù)呈指數(shù)衰減，無(wú)法大范圍傳播， 網(wǎng)絡(luò)此時(shí)處于吸收相態(tài)。網(wǎng)絡(luò)此時(shí)處

10、于吸收相態(tài)。 v傳染病閾值的大小決定了傳染病在網(wǎng)絡(luò)中傳播的結(jié)果，傳染病閾值的大小決定了傳染病在網(wǎng)絡(luò)中傳播的結(jié)果， 是傳播動(dòng)力學(xué)中的一個(gè)重要的參數(shù)。是傳播動(dòng)力學(xué)中的一個(gè)重要的參數(shù)。 v不同的網(wǎng)絡(luò)特性以及免疫方式對(duì)傳染病閾值的影響也不同的網(wǎng)絡(luò)特性以及免疫方式對(duì)傳染病閾值的影響也 不同。不同。 c 非零閾值的存在性非零閾值的存在性 v具有分片線性傳染力的網(wǎng)絡(luò)存在正的閾值。具有分片線性傳染力的網(wǎng)絡(luò)存在正的閾值。 可以假設(shè)傳染力函數(shù)為：可以假設(shè)傳染力函數(shù)為： v免疫前的閾值為：免疫前的閾值為： ( )min(,)kk A 1 1 m cA A m kdk kdkAkdk 隨機(jī)免疫隨機(jī)免疫 v若在網(wǎng)絡(luò)中對(duì)

11、節(jié)點(diǎn)隨機(jī)進(jìn)行概率為若在網(wǎng)絡(luò)中對(duì)節(jié)點(diǎn)隨機(jī)進(jìn)行概率為 的免疫，則閾值的免疫，則閾值 變?yōu)椋鹤優(yōu)椋?可以看出免疫是有效的，但是，免疫具有隨機(jī)性，并沒有考可以看出免疫是有效的，但是，免疫具有隨機(jī)性，并沒有考 慮到復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的度對(duì)網(wǎng)絡(luò)傳播的影響，而且當(dāng)傳染病慮到復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)的度對(duì)網(wǎng)絡(luò)傳播的影響，而且當(dāng)傳染病 閾值趨于足夠大時(shí)，免疫率也要趨近于閾值趨于足夠大時(shí)，免疫率也要趨近于1，理論上要對(duì)所有，理論上要對(duì)所有 節(jié)點(diǎn)免疫才能夠消除傳染病，效率偏低。節(jié)點(diǎn)免疫才能夠消除傳染病，效率偏低。 (0,1) ( ) 11 1( ) ( )1 k cc k kP k kk P k 目標(biāo)免疫目標(biāo)免疫 v在目標(biāo)免疫中

12、，定義一個(gè)整數(shù)在目標(biāo)免疫中，定義一個(gè)整數(shù) ，當(dāng)節(jié)點(diǎn)的度大于它時(shí)，當(dāng)節(jié)點(diǎn)的度大于它時(shí) 進(jìn)行免疫，度小于它時(shí)，不進(jìn)行免疫，等于它時(shí)，以一定進(jìn)行免疫，度小于它時(shí)，不進(jìn)行免疫，等于它時(shí)，以一定 的概率進(jìn)行免疫。的概率進(jìn)行免疫。 v在計(jì)算過程中，在計(jì)算過程中， 的正負(fù)性用于描述的正負(fù)性用于描述 目標(biāo)免疫相對(duì)與隨機(jī)免疫的有效性，經(jīng)過分析和數(shù)值模擬，目標(biāo)免疫相對(duì)與隨機(jī)免疫的有效性，經(jīng)過分析和數(shù)值模擬， 可以得到，它可以得到，它總大于零總大于零，那就說明了當(dāng)免疫率相等時(shí)，目，那就說明了當(dāng)免疫率相等時(shí)，目 標(biāo)免疫比隨機(jī)免疫更有效標(biāo)免疫比隨機(jī)免疫更有效。 v目標(biāo)免疫的流行病閾值：目標(biāo)免疫的流行病閾值： cov(,

13、() k kk (1)( ) c k kk 1 c 熟人免疫熟人免疫 v該方法不需要知道整個(gè)網(wǎng)絡(luò)的度分布，比較實(shí)用。該方法不需要知道整個(gè)網(wǎng)絡(luò)的度分布，比較實(shí)用。 v該免疫的傳染病閾值為該免疫的傳染病閾值為 為關(guān)于為關(guān)于 的函數(shù)，經(jīng)過計(jì)算，對(duì)于較小的的函數(shù)，經(jīng)過計(jì)算，對(duì)于較小的 ，熟人免疫，熟人免疫 的有效性不如目標(biāo)免疫，但是，當(dāng)?shù)挠行圆蝗缒繕?biāo)免疫，但是，當(dāng) 大于一個(gè)常數(shù)時(shí)，大于一個(gè)常數(shù)時(shí)， 熟人免疫的有效性超過了目標(biāo)免疫，并且當(dāng)熟人免疫的有效性超過了目標(biāo)免疫，并且當(dāng) 時(shí)，時(shí)， 有：有： 具體的分析過程見下頁(yè)。具體的分析過程見下頁(yè)。 (1)() ()() cc c kk p kkkk Ck 2

14、 ln1 1 ln1() 26 A m AmA mm 主動(dòng)免疫（略）主動(dòng)免疫（略） 當(dāng)當(dāng) 時(shí)，目標(biāo)免疫更有效，時(shí)，目標(biāo)免疫更有效， 下面討論下面討論 與與 之間的關(guān)系：之間的關(guān)系： ( )( )0 kk kkk 11 1 11 1111 1 1111 ( )( ) ()( ) 1 1 ()() ) 11 4 () (1)(1) kk kkk ACC kk CC AAAA Cm CA Cm A 從而當(dāng)從而當(dāng)時(shí)，時(shí)，。 0 與與 的的分分析析： A 1 121 2 1 22 ( )( ) (ln1)(ln1) 2 () 2(ln1)ln1 2 kk kkk CAA CC m AA CC m 當(dāng)當(dāng)

15、： 無(wú)法直接判斷無(wú)法直接判斷的符號(hào)。在上式中對(duì)的符號(hào)。在上式中對(duì)求偏導(dǎo)：求偏導(dǎo)： 時(shí)，時(shí)， 1 212 ()(ln1)0 A CC m A 0 因此，當(dāng)因此，當(dāng)時(shí)，也有時(shí)，也有 。 ( ,)m 0 綜上所述：對(duì)于任意的綜上所述：對(duì)于任意的，總有，總有 所以，在平均免疫率相等的情況下，目標(biāo)免疫比隨機(jī)免疫更有效。所以，在平均免疫率相等的情況下，目標(biāo)免疫比隨機(jī)免疫更有效。 2 ln (1)( ) 0 1 ( )( )ln1() 26 kk m pAm A kkkk C kmm 2 lnln 1 11 ln1()ln1 262 AA mm Am AA mmmm 當(dāng)當(dāng) A 時(shí)：時(shí)： A 當(dāng)當(dāng) 時(shí)：時(shí)：

16、1 2 ln1 (1)( ) 0 1 ( )( )ln1() 26 AA kk m pAm A kkkk C kmm 2 ln1ln1 11 ln1()ln1 262 AA mm Am AA mmmm 無(wú)法直接確定無(wú)法直接確定 的范圍，的范圍， 1 但是，可以確定但是，可以確定 與與成正比，因此令成正比，因此令 1 2 ln1 1 1 ln1() 26 AA m Am A mm 解得解得 1131 0 1 ()() 26 Am A m 0 ( ,)m1 0 (,) 1 0 1 綜上所述：當(dāng)綜上所述：當(dāng)時(shí)，時(shí)，； 時(shí)，時(shí)， 當(dāng)當(dāng) 時(shí)，時(shí)， 。 當(dāng)當(dāng) ； 網(wǎng)絡(luò)同步能力對(duì)傳播動(dòng)力學(xué)的影響網(wǎng)絡(luò)同步能力

17、對(duì)傳播動(dòng)力學(xué)的影響 v傳染病在網(wǎng)絡(luò)中同步傳播的能力與網(wǎng)絡(luò)中個(gè)體交流的密切程傳染病在網(wǎng)絡(luò)中同步傳播的能力與網(wǎng)絡(luò)中個(gè)體交流的密切程 度有著很大的關(guān)系，當(dāng)交流頻繁時(shí)，傳染病就容易在網(wǎng)絡(luò)中度有著很大的關(guān)系，當(dāng)交流頻繁時(shí)，傳染病就容易在網(wǎng)絡(luò)中 同步傳播。同步傳播。 v網(wǎng)絡(luò)上傳染病同步流行的控制變?yōu)閷?duì)網(wǎng)絡(luò)中耦合強(qiáng)度的控制，網(wǎng)絡(luò)上傳染病同步流行的控制變?yōu)閷?duì)網(wǎng)絡(luò)中耦合強(qiáng)度的控制， 當(dāng)出現(xiàn)傳染病時(shí)，若網(wǎng)絡(luò)中的耦合強(qiáng)度足夠大，傳染病就容當(dāng)出現(xiàn)傳染病時(shí)，若網(wǎng)絡(luò)中的耦合強(qiáng)度足夠大，傳染病就容 易在網(wǎng)絡(luò)中同步傳播；降低網(wǎng)絡(luò)耦合強(qiáng)度，就能夠有效地降易在網(wǎng)絡(luò)中同步傳播；降低網(wǎng)絡(luò)耦合強(qiáng)度，就能夠有效地降 低網(wǎng)絡(luò)同步能力（不管

18、是類型低網(wǎng)絡(luò)同步能力（不管是類型I還是類型還是類型II網(wǎng)絡(luò)）網(wǎng)絡(luò)）,從而有效抑從而有效抑 制傳染病的傳播。制傳染病的傳播。 v根據(jù)實(shí)際傳播網(wǎng)絡(luò)的自適應(yīng)性建立起不同類型的傳播同步模根據(jù)實(shí)際傳播網(wǎng)絡(luò)的自適應(yīng)性建立起不同類型的傳播同步模 型，即可研究網(wǎng)絡(luò)傳播率與同步穩(wěn)定性之間的關(guān)系，數(shù)值分型，即可研究網(wǎng)絡(luò)傳播率與同步穩(wěn)定性之間的關(guān)系，數(shù)值分 析結(jié)果進(jìn)一步表明，如果傳播網(wǎng)絡(luò)越容易爆發(fā)，那么傳播同析結(jié)果進(jìn)一步表明，如果傳播網(wǎng)絡(luò)越容易爆發(fā)，那么傳播同 步就越容易出現(xiàn)。步就越容易出現(xiàn)。 該項(xiàng)研究將揭示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、網(wǎng)絡(luò)同該項(xiàng)研究將揭示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、網(wǎng)絡(luò)同 步動(dòng)力學(xué)和網(wǎng)絡(luò)傳播動(dòng)力學(xué)這三者之間相互依賴關(guān)系步動(dòng)力

19、學(xué)和網(wǎng)絡(luò)傳播動(dòng)力學(xué)這三者之間相互依賴關(guān)系 (Ongoing research.)。 主要結(jié)果：主要結(jié)果： 圖圖 示：示： 參考文獻(xiàn)參考文獻(xiàn) Watts D J. Annual Review of Socialogy,2004 30: 243-270. 方錦清，汪小帆等，一門嶄新的交叉科學(xué)方錦清，汪小帆等，一門嶄新的交叉科學(xué)-網(wǎng)絡(luò)科學(xué)上篇，網(wǎng)絡(luò)科學(xué)上篇，2007，246-247. 陳關(guān)榮，復(fù)雜網(wǎng)絡(luò)及其新近研究進(jìn)展簡(jiǎn)介，力學(xué)進(jìn)展陳關(guān)榮，復(fù)雜網(wǎng)絡(luò)及其新近研究進(jìn)展簡(jiǎn)介，力學(xué)進(jìn)展, Vol.38, No.6 2008, 653-662. Bollobsi B. Random Graphs. New Yo

20、rk: Academic Press, 2001. Barabasi A L, Ravasz E, Vicsek T. Physica A, 2001, 299: 559-564 .Zhang Z. Z., Comellas F., Fertin G, et al. J. Phys. A: Math. and Gen., 2006, 39 (8): 1811- 1818. Boccaletti S, Latora V, Moreno Y, et al. Physics Reports, 2006, 424: 175-308. Gong B, Yang L, Yang K. Phys. Rev. E, 2005, 72: 037101. 陳關(guān)榮，汪小帆等，復(fù)雜網(wǎng)絡(luò)：理論及其應(yīng)用，清華大學(xué)出版社，陳關(guān)榮，汪小帆等，復(fù)雜網(wǎng)絡(luò)：理論及其應(yīng)用，清華大學(xué)出版社，2006. Li X，Chen G. Physica A，2003，328: 274-286. 方錦清，汪小帆等，一門嶄新的交叉科學(xué)方錦清，汪小帆等，一門嶄新的交叉科學(xué)-網(wǎng)絡(luò)科學(xué)上篇網(wǎng)絡(luò)科學(xué)上篇,200