網(wǎng)絡(luò)動力學(xué)課件

復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)——網(wǎng)絡(luò)動力學(xué)復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)——網(wǎng)絡(luò)動力學(xué)16.1復(fù)雜網(wǎng)絡(luò)上的物理傳輸過程動力學(xué)6.2網(wǎng)絡(luò)的同步6.1復(fù)雜網(wǎng)絡(luò)上的物理傳輸過程動力學(xué)26.1網(wǎng)絡(luò)上的物理傳輸過程動力學(xué)復(fù)雜網(wǎng)絡(luò)上的傳播動力學(xué)問題是復(fù)雜網(wǎng)絡(luò)研究的一個重要方向。主要研究社會和自然界中各種復(fù)雜網(wǎng)絡(luò)的傳播機理與動力學(xué)行為以及對這些行為高效可行的控制方法。復(fù)雜網(wǎng)絡(luò)上的傳播過程可以分為兩類：不符合物質(zhì)或能量守恒的過程以及符合物質(zhì)或能量守恒的過程。首先介紹復(fù)雜網(wǎng)絡(luò)上的流行病傳播機理，接著介紹復(fù)雜網(wǎng)絡(luò)的免疫策略，然后介紹復(fù)雜網(wǎng)絡(luò)上的輿論傳播，最后介紹復(fù)雜網(wǎng)絡(luò)上的數(shù)據(jù)包傳遞機理和擁塞控制。6.1網(wǎng)絡(luò)上的物理傳輸過程動力學(xué)復(fù)雜網(wǎng)絡(luò)上的傳播動力學(xué)問題36.1.1復(fù)雜網(wǎng)絡(luò)上的流行病傳播流行病傳播的速度很快，對社會的影響非常大，引起全社會的極大關(guān)注，如網(wǎng)絡(luò)病毒、人類社會中的SARS、性病、艾滋病和謠言等等。在復(fù)雜網(wǎng)絡(luò)上，最近的理論和實驗都表明流行病的傳播閾值與網(wǎng)絡(luò)系統(tǒng)的尺寸(節(jié)點數(shù))有著緊密聯(lián)系。在復(fù)雜網(wǎng)絡(luò)傳播動力學(xué)的研究中，傳播閾值λc是理論和實驗研究工作者特別關(guān)注的一個重要參量。對于尺寸非常大的網(wǎng)絡(luò)系統(tǒng)而言，如果流行病的傳播概率大于該傳播閾值，那么受感染人數(shù)將占一個有限大小的比例，即傳染病會爆發(fā)且持續(xù)地存在；否則，受感染人數(shù)會呈指數(shù)衰減，其占總?cè)藬?shù)的比例將接近于0，即傳染病將會自然消失。6.1.1復(fù)雜網(wǎng)絡(luò)上的流行病傳播流行病傳播的速度很快，對社會4流行病傳播的基本模型需要采用不同的數(shù)學(xué)模型來表征不同的傳播規(guī)律，它們是復(fù)雜網(wǎng)絡(luò)傳播動力學(xué)研究的基礎(chǔ)。傳播模型中的每一類個體都處于同一種狀態(tài)?；緺顟B(tài)包括：易感狀態(tài)(S)，即健康的狀態(tài)，但有可能被感染；感染狀態(tài)(I)，即染病的狀態(tài)，具有傳染性；移除狀態(tài)(R)，即感染后被治愈并獲得了免疫力或感染后死亡的狀態(tài)。處于移除狀態(tài)的個體不具有傳染性，也不會再次被感染，即不再對相應(yīng)動力學(xué)行為產(chǎn)生任何影響，可以看作已經(jīng)從系統(tǒng)中移除。在真實系統(tǒng)中不同種類的傳染病具有不同的傳播方式，研究它們的傳播行為通常采用不同的傳播模型流行病傳播的基本模型需要采用不同的數(shù)學(xué)模型來表征不同的傳播規(guī)5SIS模型描述像感冒這類治愈后患者不能獲得免疫力的疾病。此外計算機病毒也屬于這一類型。個體分為兩類：易感人群(S)和染病人群(I)。染病人群為傳染的源頭，它通過一定的概率λ把傳染病傳給易感人群。染病人群本身也有一定的概率u可以被治愈；易感人群一旦被感染，就又變成了新的傳染源。SIS模型的感染機制可以用下式表示：SIS模型6s(t)，i(t)分布標(biāo)記群體中個體在時刻t處于S態(tài)和I態(tài)的密度，當(dāng)易感人群和感染人群充分混合時，其動力學(xué)可以用下列微分方程組描述：此方程中存在一個閾值λc=α/β，當(dāng)λ<λc時其定態(tài)解為i(T)=0，而當(dāng)λ>λc時其定態(tài)解為i(T)>0，這里T為達到穩(wěn)定態(tài)的時間。s(t)，i(t)分布標(biāo)記群體中個體在時刻t處于S態(tài)和I態(tài)的7SIR模型適合描述那些染病者在治愈后可以獲得終生免疫能力的疾病，如麻疹、腮腺炎、水痘、百日咳等，或者幾乎不可避免走向死亡的疾病，如艾滋病等。人群分為三類：易感人群(S)、染病人群(I)和免疫人群(R)。不同于SIS模型，這里染病人群將不再變?yōu)橐赘腥巳憾且愿怕蕌變成免疫人群。在每一個給定的時間，個體處于三態(tài)之一，其動力學(xué)方程如下：SIR模型8用s(t)，i(t)，r(t)分布標(biāo)記群體處于S態(tài)、I態(tài)、R態(tài)的密度。當(dāng)易感人群和染病人群充分混合時，SIR模型的動力學(xué)可以用下列微分方程組描述：隨著時間進行，感染人數(shù)將逐步增加。經(jīng)過充分長的時間后，因為易感個體的不足使得感染個體也開始減少，直至感染人數(shù)變?yōu)?，傳染過程結(jié)束。因此，SIR模型在穩(wěn)態(tài)時刻t=T的傳染密度r(T)和有效傳染率λ存在著一一對應(yīng)的關(guān)系，且r(T)可以用來測量傳染的有效率。當(dāng)λ<λc時感染無法擴散，而當(dāng)λ>λc時感染爆發(fā)。用s(t)，i(t)，r(t)分布標(biāo)記群體處于S態(tài)、I態(tài)、R9其他模型SI模型用于描述那些染病后不可能治愈的疾病，或?qū)τ谕蝗槐l(fā)尚缺乏有效控制的流行病，如黑死病及非典型肺炎。也就是說，在SI模型中，個體一旦被感染就會永久處于感染狀態(tài)。SIRS模型適合于描述免疫期有限或者說免疫能力有限的疾病。與SIR模型不同的是，在SIRS模型中，處于移除狀態(tài)的個體(治愈后具有免疫力)還會以概率γ失去免疫力。SEIR模型適合于描述具有潛伏態(tài)的疾病，如季節(jié)性感冒。與SIR模型不同，易感個體與感染個體接觸后先以一定概率α變?yōu)闈摲鼞B(tài)(E)，然后再以一定概率β變?yōu)楦腥緫B(tài)。其他模型10均勻網(wǎng)中的流行病傳播按照度分布，復(fù)雜網(wǎng)絡(luò)可以分為均勻網(wǎng)絡(luò)和非均勻網(wǎng)網(wǎng)絡(luò)。均勻網(wǎng)的度分布范圍不大，在某一平均值附近且度分布指數(shù)衰減，如隨機網(wǎng)絡(luò)與小世界網(wǎng)絡(luò)。對于均勻網(wǎng)絡(luò)，其傳播動力學(xué)通常可以由平均場或均勻混合方法給出。本小節(jié)介紹均勻網(wǎng)絡(luò)中的流行病傳播規(guī)律，分別基于SIS和SIR兩種模型加以討論。均勻網(wǎng)中的流行病傳播按照度分布，復(fù)雜網(wǎng)絡(luò)可以分為均勻網(wǎng)絡(luò)和非111．基于SIS模型的情形均勻網(wǎng)絡(luò)中每個節(jié)點的度近似等于網(wǎng)絡(luò)的平均度，即k≈＜k＞。對于SIS模型來說，在每一個時間步，如果網(wǎng)絡(luò)中易感個體至少和一個感染個體相連，則它被感染的概率為α；同時，感染個體被治愈變?yōu)橐赘袀€體的概率為β。為了便于研究，這里對SIS模型作了兩個假設(shè)：(1)均勻混合假設(shè)：有效傳染率λ與系統(tǒng)中處于感染狀態(tài)的個體的密度ρ(t)成正比，即α和β都是常數(shù)。(2)假設(shè)病毒的時間尺度遠遠小于個體的生命周期，從而不考慮個體的出生和自然死亡。令有效傳染率(或叫有效傳播率)λ＝α／β，它是一個非常重要的參量。1．基于SIS模型的情形12均勻網(wǎng)絡(luò)中存在一個傳播閾值λc。當(dāng)有效傳播率λ大于λc時，感染個體能夠?qū)⒉《緜鞑U散，并使得整個網(wǎng)絡(luò)中感染個體的總數(shù)最終穩(wěn)定于某一平衡狀態(tài)，網(wǎng)絡(luò)此時處于激活相態(tài)(activephase)；當(dāng)有效傳播率λ小于λc時，感染個體的數(shù)量呈指數(shù)衰減，無法大范圍傳播，網(wǎng)絡(luò)此時處于吸收相態(tài)(absorbingphase)。所以在均勻網(wǎng)絡(luò)中，存在一個正的傳播閾值以將激活相態(tài)和吸收相態(tài)明確地分隔開。均勻網(wǎng)絡(luò)中存在一個傳播閾值λc。13不失一般性，令β＝1(這種做法只是改變演化時間的尺度)，利用平均場理論，均勻網(wǎng)絡(luò)中被感染個體的密度隨時間的演化滿足如下方程：式中第一項表示感染個體以單位速率減少(因為假設(shè)概率β＝1)，第二項表示單個感染個體產(chǎn)生的新感染個體的平均密度，它與有效傳播率、節(jié)點(個體)的平均度＜k＞及感染節(jié)點與易感節(jié)點連接的概率ρ(t)[1-ρ(t)]成正比。式中，ρ為感染個體的穩(wěn)態(tài)密度。可以解得，均勻網(wǎng)絡(luò)流行病傳播的閾值為：不失一般性，令β＝1(這種做法只是改變演化時間的尺度)，利用14而且滿足由此可見，傳播閾值與平均度成反比。這很好理解，因為接觸的人越多，被感染的幾率就越大，故降低平均度是控制傳染病傳播的一個有效手段。而且滿足152.基于SIR模型的情形對于SIR模型來說，處于易感狀態(tài)、感染狀態(tài)和移除狀態(tài)的個體的密度s(t)、i(t)和r(t)滿足如下約束條件：同樣令λ＝α／β，β＝1(這種做法只是改變演化時間的尺度)，在與SIS模型相同的假設(shè)條件下，易感個體、感染個體和免疫個體(處于移除狀態(tài)的個體)的密度滿足：不同于SIS模型，這里傳染效率是以最終感染人口r∞(t趨于無窮大時r(t)的值)來衡量的。2.基于SIR模型的情形16當(dāng)λ＜λc時，r∞在非常大的人口極限下為無窮小；而當(dāng)λ＞λc時，疾病傳播并感染有限比例的人群。在初始條件r(0)＝0與s(0)≈1下，由上式容易得到：將此結(jié)果與約束條件式相結(jié)合，可得到總感染人數(shù)滿足下列自治方程：為了得到非零解，必須滿足下列條件：這個條件等價于限制λ＞λc，其閾值在這個特殊情形下取λc＝＜k＞-1。在λ＝λc處進行泰勒展開，可得傳染效率為：上面兩種模型討論可見：對于均勻網(wǎng)絡(luò)，有效傳染率存在一個大于零的臨界值，當(dāng)有效傳染率大于傳播閾值時，疾病可以在網(wǎng)絡(luò)中傳播，并可以持久的存在，當(dāng)有效傳染率小于傳播閾值，疾病則在網(wǎng)絡(luò)中消亡。當(dāng)λ＜λc時，r∞在非常大的人口極限下為無窮小；而當(dāng)λ＞λc17非均勻網(wǎng)中的流行病傳播在無標(biāo)度網(wǎng)絡(luò)中，無論流行病的傳染性是多么弱，流行病仍然能夠爆發(fā)并且持續(xù)的存在。在無標(biāo)度網(wǎng)絡(luò)中，由于度分布滿足冪律分布，一個隨機選取的節(jié)點傾向于連接關(guān)鍵節(jié)點或連接度大的節(jié)點，因此度大的節(jié)點就容易感染，然后作為種子去感染其他人，從而導(dǎo)致比均勻網(wǎng)絡(luò)上更快的流行病傳播。為了刻畫網(wǎng)絡(luò)拓撲對流行病傳播的影響，通常將節(jié)點按照度來分組，相同度的節(jié)點成為一組。本小節(jié)分別基于SIS模型和SIR模型兩種情形介紹非均勻網(wǎng)絡(luò)中的流行病傳播規(guī)律。非均勻網(wǎng)中的流行病傳播在無標(biāo)度網(wǎng)絡(luò)中，無論流行病的傳染性是多181．基于SIS模型的情形設(shè)ρk(t)表示t時刻度為k的節(jié)點組中感染節(jié)點的密度，則它滿足如下微分方程：式中第一項為湮滅項，感染群體以單位速率減少(假設(shè)概率β＝1)；第二項為產(chǎn)生項，它正比于有效傳播率、易感人群的密度[1-ρk(t)]、節(jié)點的度k以及任意鄰居被感染的概率。其中，任意鄰居被感染的概率記作Θ(ρ(t))，它表示從一個度為k的節(jié)點連到度為任意k'的節(jié)點的聯(lián)合概率p(k'|k)ρk'(t)的平均。從而上式可重新描述為：1．基于SIS模型的情形19設(shè)ρk為度為k的節(jié)點組中感染個體的穩(wěn)態(tài)密度。顯然，ρk只是λ的函數(shù)，因而穩(wěn)態(tài)時相應(yīng)地概率Θ也變?yōu)棣说碾[函數(shù)。利用穩(wěn)態(tài)條件可得：(*)對于非關(guān)聯(lián)網(wǎng)絡(luò)，概率P(k'｜k)滿足：則Θ(λ)可以寫成如下自治方程：利用上式，容易求得Θ(λ)，再代入(*)式可以解得ρk。最終的感染個體穩(wěn)態(tài)密度ρ則可由下式估算：另外，由自治方程可得：(**)設(shè)ρk為度為k的節(jié)點組中感染個體的穩(wěn)態(tài)密度。顯然，ρk只是λ20顯然，該式存在一個平凡解Θ(λ)＝0。如果要使該方程存在一個非平凡解，必須滿足：即于是，可求得非均勻網(wǎng)上SIS傳播模型的閾值為：對該閾值可理解如下：當(dāng)λ＜λc，若(**)式中Θ(λ)≠0，則由Θ(λ)＞0可知：故式(**)的第二項肯定大于0，故當(dāng)λ＜λc時只有Θ(λ)＝0才能使(**)式成立。所以，只有當(dāng)λ≥λc時，才能由第二項得到不為0的Θ(λ)。顯然，該式存在一個平凡解Θ(λ)＝0。如果要使該方程存在一個21對于規(guī)模無限大的具有度分布P(k)∝k-γ(γ≤3)的網(wǎng)絡(luò)，＜k2＞=∞，對應(yīng)的λc=0。由此可見，在無標(biāo)度網(wǎng)絡(luò)中，無論傳染概率多么小，流行病都能持久存在，這個結(jié)果很好地解釋了為什么病毒與輿論可以在Internet與社會網(wǎng)絡(luò)中傳播的如此快。對于規(guī)模無限大的具有度分布P(k)∝k-γ(γ≤3)的網(wǎng)絡(luò)，222.基于SIR模型的情形假設(shè)一個度為k的節(jié)點組中處于易感狀態(tài)、感染狀態(tài)和移除狀態(tài)的個體的密度分別表示為sk(t)、ik(t)和rk(t)，則它們滿足約束關(guān)系：與SIS模型分析類似，令

，可以得到下列動力學(xué)演化方程：2.基于SIR模型的情形23上述方程組初始條件為rk(0)=0、ik(0)=i0和sk(0)=1-i0。在極限i0→0時，我們可取ik(0)≈0，sk(0)≈1。在該近似條件下，由演化方程的第一個方程可得：其中，為如下的輔助函數(shù)(考慮演化方程的第三個方程)：其導(dǎo)數(shù)可簡化為：由此我們得到了關(guān)于的一個自治方程，它在給定的P(k)條件下可以求解。一旦得到，就可以得到

，從而由可得：上述方程組初始條件為rk(0)=0、ik(0)=i0和sk(24由于得到，從而可以得到關(guān)于的自治方程：為了得到非平凡解(非零解)，必須滿足如下條件：于是從而得到閾值為這個結(jié)果與SIS模型完全相同。由于得到，從而可以25在SIS傳播模型下，比較在相同平均度條件下WS小世界網(wǎng)絡(luò)與BA無標(biāo)度網(wǎng)絡(luò)的傳播規(guī)律(傳染率λ和感染個體的穩(wěn)態(tài)密度ρ的關(guān)系)，如下圖所示。

WS小世界網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)的傳播規(guī)律比較BA無標(biāo)度網(wǎng)絡(luò)的參數(shù)m=3，其平均度為2m等于6，取WS小世界網(wǎng)絡(luò)的參數(shù)＜k＞=6?？梢?，BA網(wǎng)絡(luò)的傳染率連續(xù)而平滑地過渡到0，說明無標(biāo)度網(wǎng)絡(luò)不存在正傳播閾值。對于BA網(wǎng)絡(luò)，只要傳染率大于0，病毒都能傳播并最終維持在一個穩(wěn)定態(tài)，這也反映了BA網(wǎng)絡(luò)對病毒傳播的脆弱性。ρλ在SIS傳播模型下，比較在相同平均度條件下WS小世界網(wǎng)絡(luò)與B26幾種網(wǎng)絡(luò)傳播臨界值比較幾種網(wǎng)絡(luò)傳播臨界值比較27群落網(wǎng)結(jié)構(gòu)對流行病傳播的影響社團結(jié)構(gòu)一般都具有群落結(jié)構(gòu)，群落可以由同事、朋友、同學(xué)或俱樂部成員等組成。在社會網(wǎng)絡(luò)中，各群落內(nèi)部成員聯(lián)系緊密；相反，在不同群落之間則聯(lián)系較少。群落網(wǎng)絡(luò)的結(jié)構(gòu)示意圖如圖所示。群落結(jié)構(gòu)的存在必然影響流行病的傳播。本小節(jié)重點探討群落結(jié)構(gòu)對流行病傳播的影響。含三個社團的社團網(wǎng)絡(luò)結(jié)構(gòu)示意圖(社團內(nèi)實線連接，社團間虛線連接)群落網(wǎng)結(jié)構(gòu)對流行病傳播的影響社團結(jié)構(gòu)一般都具有群落結(jié)構(gòu)，群落28社會網(wǎng)絡(luò)通常具備高的集聚系數(shù)，群落內(nèi)的連線密度高，而群落間的連線密度低。假設(shè)我們將產(chǎn)生一個含有N個節(jié)點、m個組的群落網(wǎng)模型，提出如下簡單方法來構(gòu)造群落網(wǎng)絡(luò)：步驟1：初始化。將N個節(jié)點隨機分成m個組，每組內(nèi)的節(jié)點數(shù)為ni(i=1，2，…，m)，即步驟2：群落內(nèi)連線。每個組內(nèi)的節(jié)點間以概率p連線，從而組i內(nèi)的連線數(shù)為。步驟3：群落間連線。任意兩個組間的節(jié)點間以概率q連線，從而組i和組j間的連線數(shù)為。通過上述構(gòu)造方法，最終得到的網(wǎng)絡(luò)總邊數(shù)為

社會網(wǎng)絡(luò)通常具備高的集聚系數(shù)，群落內(nèi)的連線密度高，而群落間的29令序參量σ=p／q表示群落化的程度，則對于群落網(wǎng)絡(luò)應(yīng)該有σ>>１。如果σ=1，則上述方法得到的網(wǎng)絡(luò)將退化為一般的隨機網(wǎng)絡(luò)。如果給定總邊數(shù)M、總節(jié)點數(shù)N及群落劃分方案和序參量σ，則概率p和q可由下式給定：令序參量σ=p／q表示群落化的程度，則對于群落網(wǎng)絡(luò)應(yīng)該有σ>30社團網(wǎng)絡(luò)上的流行病傳播用SIS模型來討論流行病在群落網(wǎng)中的傳播規(guī)律。假定易感個體以概率α與每個周圍的感染個體接觸。若節(jié)點vj處于易感狀態(tài)且有kj個鄰居，它們中有kinf個處于感染狀態(tài)，則在每個時間步，節(jié)點vj將以概率變?yōu)楦腥緺顟B(tài)。同時每個感染節(jié)點以概率β變?yōu)橐赘袪顟B(tài)。同前面的討論一樣，為簡單起見，這里令λ=α／β，β=1。假定初始時有一粒種子，則它的每個鄰居將以λ的概率被感染，然后再感染它們的鄰居。一定時間后，感染達到穩(wěn)態(tài)。社團網(wǎng)絡(luò)上的流行病傳播用SIS模型來討論流行病在群落網(wǎng)中的傳31對于λ＜λc，穩(wěn)態(tài)為0；而對于λ＞λc，穩(wěn)態(tài)為非零。由于群落網(wǎng)絡(luò)的非均勻結(jié)構(gòu)，最終的狀態(tài)依賴于選取的種子及網(wǎng)絡(luò)構(gòu)型，因此有意義的結(jié)果必須為對各種網(wǎng)絡(luò)構(gòu)型及各種初始條件的平均。對具有σ>>１的群落網(wǎng)，當(dāng)λ較小時，傳播會限制在種子所在的群落內(nèi)。從統(tǒng)計意義上看，可以認為種子被均勻選取在每個社團。對于每個特定的群落i，其閾值λc(i)由其平均連線數(shù)決定。當(dāng)群落間的連線遠小于群落內(nèi)的連線時，有且此關(guān)系對所有的種子成立。整個系統(tǒng)的λc為不同構(gòu)型及不同實現(xiàn)的平均，即對不同的種子平均，因此λc與p間的定量關(guān)系為λc～1／p。對于λ＜λc，穩(wěn)態(tài)為0；而對于λ＞λc，穩(wěn)態(tài)為非零。32其中a為一常數(shù)。因此λc與M成反比。對于給定的M，上式可被寫為：這就是λc對群落程度σ的依賴關(guān)系。隨著群落度的降低，流行病的傳播閾值將增加并在隨機網(wǎng)時達到極大值。換句話說，流行病在隨機網(wǎng)上比在群落網(wǎng)上更不容易爆發(fā)。通過前面的討論，還可以得到一個結(jié)論：傳染病本身的動力學(xué)性質(zhì)和個體所在的網(wǎng)絡(luò)結(jié)構(gòu)共同決定了流行病的傳染行為和傳染過程。網(wǎng)絡(luò)動力學(xué)課件33無標(biāo)度網(wǎng)絡(luò)是很容易受到病毒感染而導(dǎo)致病毒流行的，因此選擇合適的免疫策略顯得非常重要。人們針對免疫策略作了較多的研究，通常根據(jù)節(jié)點在網(wǎng)絡(luò)中的地位(例如以節(jié)點的度來衡量)來關(guān)注節(jié)點的選擇。下面簡要介紹復(fù)雜網(wǎng)絡(luò)的三種免疫策略：隨機免疫、目標(biāo)免疫和熟人免疫。無標(biāo)度網(wǎng)絡(luò)是很容易受到病毒感染而導(dǎo)致病毒流行的，因此選擇合適34隨機免疫完全隨機地選取網(wǎng)絡(luò)中的一部分節(jié)點進行免疫。免疫節(jié)點不會再被感染，所以它們不會再影響它們的鄰居。針對均勻網(wǎng)絡(luò)，容易得出隨機免疫的免疫臨界值為：對于無標(biāo)度網(wǎng)絡(luò)來說，推導(dǎo)，可以得到此時隨機免疫的免疫臨界值gc為顯然，隨著網(wǎng)絡(luò)規(guī)模的無限增長，無標(biāo)度網(wǎng)絡(luò)的＜k2＞→∞，其傳播閾值λc趨于0，而免疫臨界值gc趨于1。這表明，如果對于無標(biāo)度網(wǎng)絡(luò)采取隨機免疫策略，則需要對網(wǎng)絡(luò)幾乎所有節(jié)點都實施免疫才能保證最終消滅病毒傳染。隨機免疫完全隨機地選取網(wǎng)絡(luò)中的一部分節(jié)點進行免疫。35目標(biāo)免疫根據(jù)無標(biāo)度網(wǎng)絡(luò)的不均勻特性，選取少量度最大的節(jié)點進行免疫。就BA無標(biāo)度網(wǎng)絡(luò)而言，目標(biāo)免疫對應(yīng)的免疫臨界值為：上式表明，即使傳染率λ在很大的范圍內(nèi)取不同的值，都可以得到很小的免疫臨界值。因此，有選擇地對無標(biāo)度網(wǎng)絡(luò)進行目標(biāo)免疫，其臨界值要比隨機免疫小得多。目標(biāo)免疫根據(jù)無標(biāo)度網(wǎng)絡(luò)的不均勻特性，選取少量度最大的節(jié)點進行36

對BA無標(biāo)度網(wǎng)絡(luò)采取隨機免疫和目標(biāo)免疫的對比上圖橫坐標(biāo)為免疫密度g，縱坐標(biāo)為ρg/ρ0，ρ0表示網(wǎng)絡(luò)未加免疫的穩(wěn)態(tài)感染密度，ρg為網(wǎng)絡(luò)中加入比例為g的免疫節(jié)點后的穩(wěn)態(tài)感染密度?？梢钥闯觯S機免疫和目標(biāo)免疫在無標(biāo)度網(wǎng)絡(luò)中存在著明顯的臨界值差別。在隨機免疫情況下，隨著免疫密度g的增大，最終的被感染程度下降緩慢，只有當(dāng)g=1時，才能使被感染數(shù)為零。而在目標(biāo)免疫的情況下，gc≈0.16，這意味著只要對少量度很大節(jié)點進行免疫，就能消除無標(biāo)度網(wǎng)絡(luò)中的病毒擴散。對BA無標(biāo)度網(wǎng)絡(luò)37熟人免疫:對隨機選出的節(jié)點的鄰居進行免疫，該策略基本思想是：從N個節(jié)點中隨機選出比例為s的節(jié)點，再從每一個被選出的節(jié)點中隨機選擇它的某個鄰居節(jié)點進行免疫。

無標(biāo)度網(wǎng)絡(luò)中免疫臨界值隨冪律指數(shù)的變化情況10.80.60.40.2022.533.5γgc熟人免疫:對隨機選出的節(jié)點的鄰居進行免疫，該策略基本思想是：38復(fù)雜網(wǎng)絡(luò)上的輿論演化動力學(xué)輿論及其特性輿論是由許許多多的社會個體的意見相互作用而形成的，其發(fā)展變化受到自然、社會、經(jīng)濟、文化、政治、法律等各種因素的影響，它的演化過程具有：復(fù)雜性開放性不確定性非平衡性自組織性等特性。協(xié)議是社會群體中非常重要的方面之一，每天的日常生活都需要人們達到共識，而協(xié)議使得組織更協(xié)調(diào)有效并可以擴展在社會上的影響力。復(fù)雜網(wǎng)絡(luò)上的輿論演化動力學(xué)輿論及其特性39輿論傳播的動力學(xué)行為也服從SIR模型。但是它的三種狀態(tài)和流行病中的三種狀態(tài)S、I、R代表：不知道消息的人群，知道消息的并有能力繼續(xù)傳播消息的人群，及知道消息但已經(jīng)失去傳播能力或興趣的人群。假設(shè)網(wǎng)絡(luò)上有N個節(jié)點，每個節(jié)點代表一個可傳播消息的個人，他們傳播消息的行為方式如下：如果得到了一個消息(I態(tài))，那么他就有興趣把這個消息傳播出去，在傳播過程中，他將隨機地從鄰居中選取一人并將消息傳給他，如果這個鄰居不知道這個消息(S態(tài))，則該鄰居就得到此消息(I態(tài))，并進行下一輪的傳播。但如果他的鄰居已經(jīng)知道了這個消息，那么傳播消息的人會認為該消息失去了繼續(xù)傳播的價值，并失去傳播該消息的興趣(R態(tài))。整個過程可由以下關(guān)系簡單地表示出來：輿論傳播的動力學(xué)行為也服從SIR模型。但是它的三種狀態(tài)和流行40假設(shè)在一個有限網(wǎng)絡(luò)中所有的節(jié)點都處于S態(tài)，在某一時刻突然有一個節(jié)點得到了一個新的消息，它將成為I態(tài)。那么按照上面所定義的規(guī)則，這個消息將在網(wǎng)絡(luò)中傳播，直到最終網(wǎng)絡(luò)中沒有I態(tài)的節(jié)點為止。稱這個狀態(tài)為終態(tài)。對于相同平均度的網(wǎng)絡(luò)，無標(biāo)度網(wǎng)比隨機網(wǎng)絡(luò)具有更多度大的節(jié)點，因此無標(biāo)度網(wǎng)中的消息可較容易的傳遞給大節(jié)點然后再到其他節(jié)點。一旦大節(jié)點處于I態(tài)或R態(tài)，其他節(jié)點因為以較大概率連接到它們，從而更容易變成R態(tài)；而隨機網(wǎng)則沒有這個特點。因此，輿論在無標(biāo)度網(wǎng)絡(luò)上的傳播要比在隨機網(wǎng)絡(luò)上結(jié)束得快，從而導(dǎo)致無標(biāo)度網(wǎng)的總感染密度比隨機網(wǎng)的小。網(wǎng)絡(luò)動力學(xué)課件41網(wǎng)絡(luò)的同步早在三百多年前，物理學(xué)家惠更斯在給父親的信里提到他臥病在床的幾天中驚奇的發(fā)現(xiàn)，掛在同一個橫梁上的兩個鐘擺在一段時間以后會出現(xiàn)同步的擺動現(xiàn)象。這種現(xiàn)象發(fā)生的原因是它們通過懸掛其上的橫粱相互作用。除了這種兩個個體相互作用產(chǎn)生的同步現(xiàn)象之外，很多重要的同步現(xiàn)象出現(xiàn)在多體系統(tǒng)中。網(wǎng)絡(luò)的同步42隨著對復(fù)雜網(wǎng)絡(luò)研究的深入，復(fù)雜網(wǎng)絡(luò)上的同步問題開始被廣泛關(guān)注?？紤]一個耦合動力學(xué)系統(tǒng)，其拓撲結(jié)構(gòu)是一個復(fù)雜網(wǎng)絡(luò)。系統(tǒng)中的各個節(jié)點在與外界孤立時，其演化方式是混沌的。初始時刻，各個點的狀態(tài)隨機分布，各不相同，經(jīng)過一段時間的過渡之后，各點的狀態(tài)可能會趨于相同，達到同步態(tài)。人們研究的重點是：網(wǎng)絡(luò)的拓撲結(jié)構(gòu)是如何影響其同步能力的。主要介紹多種不同混沌同步方式的定義，包括完全同步、廣義同步、相位同步和滯后同步等。隨著對復(fù)雜網(wǎng)絡(luò)研究的深入，復(fù)雜網(wǎng)絡(luò)上的同步問題開始被廣泛關(guān)注43混沌同步的定義通俗的講，同步是指兩個或多個系統(tǒng)，在外部驅(qū)動或者相互耦合的作用下。調(diào)整它們的某個動態(tài)性質(zhì)以達到具有相同性質(zhì)的過程。所謂混沌同步，指的是對于從不同的初始條件出發(fā)的兩個混沌系統(tǒng)，隨著時間的推移，它們的軌跡逐漸一致。一組動力單元(全同或者不全同)，通過一定的相互作用或者外界的驅(qū)動，使得它們的某種運動性質(zhì)趨于相同，我們就說這組單元達到了同步。同步廣泛存在于自然界和社會生活中，常見的同步的例子有：惠更斯擺、螢火蟲的同步發(fā)光、蛙的齊鳴、心肌細胞和大腦神網(wǎng)絡(luò)的同步，以及眾人長時間鼓掌導(dǎo)致掌聲頻率趨于同步?；煦缤降亩x通俗的講，同步是指兩個或多個系統(tǒng)，在外部驅(qū)動或44(精確)同步：兩個或多個動力學(xué)系統(tǒng)，除了自身的演化外，其間還有相互作用（耦合），這種作用既可以是單向的，也可以是雙向的。當(dāng)滿足一定條件時，在耦合的影響下，這些系統(tǒng)的狀態(tài)輸出就會逐漸趨同進而完全相等，稱為同步（精確同步）。廣義的同步還包括相同步和頻率同步等等。復(fù)雜系統(tǒng)中的同步主要有兩大類：完全同步和廣義同步，前者兩個相同單元研究得比較多，兩個不同單元研究得比較少；后者包括部分同步，如相同步、滯后同步、頻率同步等。(精確)同步：兩個或多個動力學(xué)系統(tǒng)，除了自身的演化外，其間還45對于系統(tǒng)其中，X＝（x1，x2，...，xn）T∈Rn，Y＝（y1，y2，...，ym）T∈Rm。系統(tǒng)的軌道關(guān)于性質(zhì)gx和gy同步，如存在與時間無關(guān)映射h：Rn×Rm→Rk，使得對于上述的統(tǒng)一定義，根據(jù)X和Y的不同情況可以給出四種不同同步的相應(yīng)定義：完全同步、相位同步、滯后同步和廣義同步。對于系統(tǒng)46完全同步：兩個耦合的相同系統(tǒng)，隨著時間的演化，若同步表現(xiàn)為兩個系統(tǒng)的狀態(tài)變量完全相等，我們稱之為完全同步。相位同步：混沌運動是被限制在某一局域的振蕩運動，對著這種運動，人們可以從相位和振幅兩個側(cè)面來描述系統(tǒng)的狀態(tài)。1996年，Rosenblum等人發(fā)現(xiàn)了一種相同步，即耦合的混沌振子在一定的條件下，其相位會達到同步，但其振幅幾乎沒有關(guān)聯(lián)。若系統(tǒng)（5.18）的解為振蕩型的，它們具有相位φx和φy，稱兩個子系統(tǒng)達到相位同步，如果存在兩個正整數(shù)p、q，使得其中ε是一個很小的正數(shù)。完全同步：兩個耦合的相同系統(tǒng)，隨著時間的演化，若同步表現(xiàn)為兩47滯后同步：對于系統(tǒng)，稱其兩個子系統(tǒng)達到滯后同步（延時同步），需要滿足m＝n，且存在與時間無關(guān)的常數(shù)τ，使得廣義同步：對于不全同的系統(tǒng)在一定的條件下驅(qū)動系統(tǒng)和響應(yīng)系統(tǒng)間存在的關(guān)系，對于系統(tǒng)，稱其兩個子系統(tǒng)達到關(guān)于性質(zhì)h廣義同步，如果存在連續(xù)映射h：。使得滯后同步：對于系統(tǒng)，稱其兩個子系統(tǒng)達到滯后同步（延時同步），48針對線性耦合網(wǎng)絡(luò)上的同步問題，Pecora和Carroll提出了主穩(wěn)定函數(shù)判據(jù)。他們首先假設(shè)：(1)所有的耦合振子都是完全相同的，(2)從每個振子提取的用于耦合其它振子的函數(shù)也是完全相同的，(3)同步流形是不變流形，(4)節(jié)點的耦合方式使在同步流形附近系統(tǒng)可以線性化。假設(shè)(1)和(3)是為了保證相空間中同步超平面的存在，假設(shè)(2)是為了使動力學(xué)系統(tǒng)和網(wǎng)絡(luò)結(jié)構(gòu)的穩(wěn)定性圖象更加清晰具體，假設(shè)(4)是為了更好地應(yīng)用線性近似這一研究耦合系統(tǒng)最常用的方法。在此基礎(chǔ)上，Pecora和Carroll完成了耦合振子系統(tǒng)的同步穩(wěn)定性分析，提出用主穩(wěn)定性函數(shù)方法確定動力學(xué)網(wǎng)絡(luò)同步的穩(wěn)定性。下面我們介紹主穩(wěn)定性函數(shù)的定義及其使用方法。針對線性耦合網(wǎng)絡(luò)上的同步問題，Pecora和Carroll提49考慮一個由N個全同節(jié)點構(gòu)成的復(fù)雜網(wǎng)絡(luò)。令m維矢量Xi代表節(jié)點i狀態(tài)，單個節(jié)點(與外界孤立)的動力學(xué)為:網(wǎng)絡(luò)中第i個節(jié)點的動力學(xué)為：其中，σ為耦合強度，H：Rm→Rm是一個任意的耦合函數(shù)，G為網(wǎng)絡(luò)的耦合系數(shù)矩陣Gij。矩陣G滿足

，保證了假設(shè)(3)能夠滿足，即系統(tǒng)存在不變的同步流形x1=x2=...=xN。我們關(guān)心的問題是：系統(tǒng)能否穩(wěn)定的處于同步態(tài)。考慮一個由N個全同節(jié)點構(gòu)成的復(fù)雜網(wǎng)絡(luò)。令m維矢量Xi代表節(jié)點50定義1：設(shè)f是從集合I到其自身的一個映射，對任意的x∈I，記f(0)(x)＝x，f(n)(x)＝f(f(n-1)(x))，稱f(n)(x)為f(x)的n次迭代。若f是拓撲空間I上的連續(xù)自映射，稱序列｛f(n)(x)：n∈N｝是由f迭代生成的離散拓撲半動力系統(tǒng)。若f是緊致度量空間I上的連續(xù)自映射，則稱離散拓撲半動力系統(tǒng)f為緊致系統(tǒng)。在眾多的混沌定義中，Li—Yorke的混沌定義是比較公認的和影響較大的。1975年，Li和Yorke從區(qū)間映射出發(fā)給出了混沌的一個數(shù)學(xué)定義，這也是第一次賦予混沌這個詞以嚴格的科學(xué)定義。該定義如下：定義1：設(shè)f是從集合I到其自身的一個映射，對任意的x∈I，51定義5.2：設(shè)I為R上的一個閉區(qū)間，對于連續(xù)自映射f：I→I，假設(shè)存在點x∈I，使得f(3)（x）≤x＜f（x）＜f(2)（x）或者f(3)（x）≥x＞f（x）＞f(2)（x）。如果：（1）f的周期點的周期無上界：f具有任意正整數(shù)周期的周期點，即對任意自然數(shù)n，有x∈I，使f(n)（x）＝x（非不動點的n周期點）。（2）閉區(qū)間I上存在不可數(shù)子集SI，滿足：（i）對x，y∈S，當(dāng)x≠y時有（ii）對x，y∈S有（iii）對x∈S和f的任一周期點y，有則稱f在S上為混沌的。定義5.2：設(shè)I為R上的一個閉區(qū)間，對于連續(xù)自映射f：I52Li—Yorke定義用三個本質(zhì)特征來刻劃混沌：“有界”、“非周期”和“初始條件敏感”。定義中的（1）是Sarkovskii定理的特例，存在所有正整數(shù)周期，就足以說明系統(tǒng)是相當(dāng)復(fù)雜的。滿足（2）的不可數(shù)集S（不可數(shù)集是一種無窮集合，它和整數(shù)集之間不存在一個雙射），稱為混沌集，其中的條件（i）和（ii）是本質(zhì)的，反映了軌道結(jié)構(gòu)的復(fù)雜特征。條件（iii）說明了S中無漸進周期點，但這個結(jié)論不是獨立的，實際上已經(jīng)蘊涵在（i）和（ii）中Li—Yorke定義用三個本質(zhì)特征來刻劃混沌：“有界”、“非53復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)——網(wǎng)絡(luò)動力學(xué)復(fù)雜系統(tǒng)與復(fù)雜網(wǎng)絡(luò)——網(wǎng)絡(luò)動力學(xué)546.1復(fù)雜網(wǎng)絡(luò)上的物理傳輸過程動力學(xué)6.2網(wǎng)絡(luò)的同步6.1復(fù)雜網(wǎng)絡(luò)上的物理傳輸過程動力學(xué)556.1網(wǎng)絡(luò)上的物理傳輸過程動力學(xué)復(fù)雜網(wǎng)絡(luò)上的傳播動力學(xué)問題是復(fù)雜網(wǎng)絡(luò)研究的一個重要方向。主要研究社會和自然界中各種復(fù)雜網(wǎng)絡(luò)的傳播機理與動力學(xué)行為以及對這些行為高效可行的控制方法。復(fù)雜網(wǎng)絡(luò)上的傳播過程可以分為兩類：不符合物質(zhì)或能量守恒的過程以及符合物質(zhì)或能量守恒的過程。首先介紹復(fù)雜網(wǎng)絡(luò)上的流行病傳播機理，接著介紹復(fù)雜網(wǎng)絡(luò)的免疫策略，然后介紹復(fù)雜網(wǎng)絡(luò)上的輿論傳播，最后介紹復(fù)雜網(wǎng)絡(luò)上的數(shù)據(jù)包傳遞機理和擁塞控制。6.1網(wǎng)絡(luò)上的物理傳輸過程動力學(xué)復(fù)雜網(wǎng)絡(luò)上的傳播動力學(xué)問題566.1.1復(fù)雜網(wǎng)絡(luò)上的流行病傳播流行病傳播的速度很快，對社會的影響非常大，引起全社會的極大關(guān)注，如網(wǎng)絡(luò)病毒、人類社會中的SARS、性病、艾滋病和謠言等等。在復(fù)雜網(wǎng)絡(luò)上，最近的理論和實驗都表明流行病的傳播閾值與網(wǎng)絡(luò)系統(tǒng)的尺寸(節(jié)點數(shù))有著緊密聯(lián)系。在復(fù)雜網(wǎng)絡(luò)傳播動力學(xué)的研究中，傳播閾值λc是理論和實驗研究工作者特別關(guān)注的一個重要參量。對于尺寸非常大的網(wǎng)絡(luò)系統(tǒng)而言，如果流行病的傳播概率大于該傳播閾值，那么受感染人數(shù)將占一個有限大小的比例，即傳染病會爆發(fā)且持續(xù)地存在；否則，受感染人數(shù)會呈指數(shù)衰減，其占總?cè)藬?shù)的比例將接近于0，即傳染病將會自然消失。6.1.1復(fù)雜網(wǎng)絡(luò)上的流行病傳播流行病傳播的速度很快，對社會57流行病傳播的基本模型需要采用不同的數(shù)學(xué)模型來表征不同的傳播規(guī)律，它們是復(fù)雜網(wǎng)絡(luò)傳播動力學(xué)研究的基礎(chǔ)。傳播模型中的每一類個體都處于同一種狀態(tài)?；緺顟B(tài)包括：易感狀態(tài)(S)，即健康的狀態(tài)，但有可能被感染；感染狀態(tài)(I)，即染病的狀態(tài)，具有傳染性；移除狀態(tài)(R)，即感染后被治愈并獲得了免疫力或感染后死亡的狀態(tài)。處于移除狀態(tài)的個體不具有傳染性，也不會再次被感染，即不再對相應(yīng)動力學(xué)行為產(chǎn)生任何影響，可以看作已經(jīng)從系統(tǒng)中移除。在真實系統(tǒng)中不同種類的傳染病具有不同的傳播方式，研究它們的傳播行為通常采用不同的傳播模型流行病傳播的基本模型需要采用不同的數(shù)學(xué)模型來表征不同的傳播規(guī)58SIS模型描述像感冒這類治愈后患者不能獲得免疫力的疾病。此外計算機病毒也屬于這一類型。個體分為兩類：易感人群(S)和染病人群(I)。染病人群為傳染的源頭，它通過一定的概率λ把傳染病傳給易感人群。染病人群本身也有一定的概率u可以被治愈；易感人群一旦被感染，就又變成了新的傳染源。SIS模型的感染機制可以用下式表示：SIS模型59s(t)，i(t)分布標(biāo)記群體中個體在時刻t處于S態(tài)和I態(tài)的密度，當(dāng)易感人群和感染人群充分混合時，其動力學(xué)可以用下列微分方程組描述：此方程中存在一個閾值λc=α/β，當(dāng)λ<λc時其定態(tài)解為i(T)=0，而當(dāng)λ>λc時其定態(tài)解為i(T)>0，這里T為達到穩(wěn)定態(tài)的時間。s(t)，i(t)分布標(biāo)記群體中個體在時刻t處于S態(tài)和I態(tài)的60SIR模型適合描述那些染病者在治愈后可以獲得終生免疫能力的疾病，如麻疹、腮腺炎、水痘、百日咳等，或者幾乎不可避免走向死亡的疾病，如艾滋病等。人群分為三類：易感人群(S)、染病人群(I)和免疫人群(R)。不同于SIS模型，這里染病人群將不再變?yōu)橐赘腥巳憾且愿怕蕌變成免疫人群。在每一個給定的時間，個體處于三態(tài)之一，其動力學(xué)方程如下：SIR模型61用s(t)，i(t)，r(t)分布標(biāo)記群體處于S態(tài)、I態(tài)、R態(tài)的密度。當(dāng)易感人群和染病人群充分混合時，SIR模型的動力學(xué)可以用下列微分方程組描述：隨著時間進行，感染人數(shù)將逐步增加。經(jīng)過充分長的時間后，因為易感個體的不足使得感染個體也開始減少，直至感染人數(shù)變?yōu)?，傳染過程結(jié)束。因此，SIR模型在穩(wěn)態(tài)時刻t=T的傳染密度r(T)和有效傳染率λ存在著一一對應(yīng)的關(guān)系，且r(T)可以用來測量傳染的有效率。當(dāng)λ<λc時感染無法擴散，而當(dāng)λ>λc時感染爆發(fā)。用s(t)，i(t)，r(t)分布標(biāo)記群體處于S態(tài)、I態(tài)、R62其他模型SI模型用于描述那些染病后不可能治愈的疾病，或?qū)τ谕蝗槐l(fā)尚缺乏有效控制的流行病，如黑死病及非典型肺炎。也就是說，在SI模型中，個體一旦被感染就會永久處于感染狀態(tài)。SIRS模型適合于描述免疫期有限或者說免疫能力有限的疾病。與SIR模型不同的是，在SIRS模型中，處于移除狀態(tài)的個體(治愈后具有免疫力)還會以概率γ失去免疫力。SEIR模型適合于描述具有潛伏態(tài)的疾病，如季節(jié)性感冒。與SIR模型不同，易感個體與感染個體接觸后先以一定概率α變?yōu)闈摲鼞B(tài)(E)，然后再以一定概率β變?yōu)楦腥緫B(tài)。其他模型63均勻網(wǎng)中的流行病傳播按照度分布，復(fù)雜網(wǎng)絡(luò)可以分為均勻網(wǎng)絡(luò)和非均勻網(wǎng)網(wǎng)絡(luò)。均勻網(wǎng)的度分布范圍不大，在某一平均值附近且度分布指數(shù)衰減，如隨機網(wǎng)絡(luò)與小世界網(wǎng)絡(luò)。對于均勻網(wǎng)絡(luò)，其傳播動力學(xué)通?？梢杂善骄鶊龌蚓鶆蚧旌戏椒ńo出。本小節(jié)介紹均勻網(wǎng)絡(luò)中的流行病傳播規(guī)律，分別基于SIS和SIR兩種模型加以討論。均勻網(wǎng)中的流行病傳播按照度分布，復(fù)雜網(wǎng)絡(luò)可以分為均勻網(wǎng)絡(luò)和非641．基于SIS模型的情形均勻網(wǎng)絡(luò)中每個節(jié)點的度近似等于網(wǎng)絡(luò)的平均度，即k≈＜k＞。對于SIS模型來說，在每一個時間步，如果網(wǎng)絡(luò)中易感個體至少和一個感染個體相連，則它被感染的概率為α；同時，感染個體被治愈變?yōu)橐赘袀€體的概率為β。為了便于研究，這里對SIS模型作了兩個假設(shè)：(1)均勻混合假設(shè)：有效傳染率λ與系統(tǒng)中處于感染狀態(tài)的個體的密度ρ(t)成正比，即α和β都是常數(shù)。(2)假設(shè)病毒的時間尺度遠遠小于個體的生命周期，從而不考慮個體的出生和自然死亡。令有效傳染率(或叫有效傳播率)λ＝α／β，它是一個非常重要的參量。1．基于SIS模型的情形65均勻網(wǎng)絡(luò)中存在一個傳播閾值λc。當(dāng)有效傳播率λ大于λc時，感染個體能夠?qū)⒉《緜鞑U散，并使得整個網(wǎng)絡(luò)中感染個體的總數(shù)最終穩(wěn)定于某一平衡狀態(tài)，網(wǎng)絡(luò)此時處于激活相態(tài)(activephase)；當(dāng)有效傳播率λ小于λc時，感染個體的數(shù)量呈指數(shù)衰減，無法大范圍傳播，網(wǎng)絡(luò)此時處于吸收相態(tài)(absorbingphase)。所以在均勻網(wǎng)絡(luò)中，存在一個正的傳播閾值以將激活相態(tài)和吸收相態(tài)明確地分隔開。均勻網(wǎng)絡(luò)中存在一個傳播閾值λc。66不失一般性，令β＝1(這種做法只是改變演化時間的尺度)，利用平均場理論，均勻網(wǎng)絡(luò)中被感染個體的密度隨時間的演化滿足如下方程：式中第一項表示感染個體以單位速率減少(因為假設(shè)概率β＝1)，第二項表示單個感染個體產(chǎn)生的新感染個體的平均密度，它與有效傳播率、節(jié)點(個體)的平均度＜k＞及感染節(jié)點與易感節(jié)點連接的概率ρ(t)[1-ρ(t)]成正比。式中，ρ為感染個體的穩(wěn)態(tài)密度?？梢越獾茫鶆蚓W(wǎng)絡(luò)流行病傳播的閾值為：不失一般性，令β＝1(這種做法只是改變演化時間的尺度)，利用67而且滿足由此可見，傳播閾值與平均度成反比。這很好理解，因為接觸的人越多，被感染的幾率就越大，故降低平均度是控制傳染病傳播的一個有效手段。而且滿足682.基于SIR模型的情形對于SIR模型來說，處于易感狀態(tài)、感染狀態(tài)和移除狀態(tài)的個體的密度s(t)、i(t)和r(t)滿足如下約束條件：同樣令λ＝α／β，β＝1(這種做法只是改變演化時間的尺度)，在與SIS模型相同的假設(shè)條件下，易感個體、感染個體和免疫個體(處于移除狀態(tài)的個體)的密度滿足：不同于SIS模型，這里傳染效率是以最終感染人口r∞(t趨于無窮大時r(t)的值)來衡量的。2.基于SIR模型的情形69當(dāng)λ＜λc時，r∞在非常大的人口極限下為無窮?。欢?dāng)λ＞λc時，疾病傳播并感染有限比例的人群。在初始條件r(0)＝0與s(0)≈1下，由上式容易得到：將此結(jié)果與約束條件式相結(jié)合，可得到總感染人數(shù)滿足下列自治方程：為了得到非零解，必須滿足下列條件：這個條件等價于限制λ＞λc，其閾值在這個特殊情形下取λc＝＜k＞-1。在λ＝λc處進行泰勒展開，可得傳染效率為：上面兩種模型討論可見：對于均勻網(wǎng)絡(luò)，有效傳染率存在一個大于零的臨界值，當(dāng)有效傳染率大于傳播閾值時，疾病可以在網(wǎng)絡(luò)中傳播，并可以持久的存在，當(dāng)有效傳染率小于傳播閾值，疾病則在網(wǎng)絡(luò)中消亡。當(dāng)λ＜λc時，r∞在非常大的人口極限下為無窮小；而當(dāng)λ＞λc70非均勻網(wǎng)中的流行病傳播在無標(biāo)度網(wǎng)絡(luò)中，無論流行病的傳染性是多么弱，流行病仍然能夠爆發(fā)并且持續(xù)的存在。在無標(biāo)度網(wǎng)絡(luò)中，由于度分布滿足冪律分布，一個隨機選取的節(jié)點傾向于連接關(guān)鍵節(jié)點或連接度大的節(jié)點，因此度大的節(jié)點就容易感染，然后作為種子去感染其他人，從而導(dǎo)致比均勻網(wǎng)絡(luò)上更快的流行病傳播。為了刻畫網(wǎng)絡(luò)拓撲對流行病傳播的影響，通常將節(jié)點按照度來分組，相同度的節(jié)點成為一組。本小節(jié)分別基于SIS模型和SIR模型兩種情形介紹非均勻網(wǎng)絡(luò)中的流行病傳播規(guī)律。非均勻網(wǎng)中的流行病傳播在無標(biāo)度網(wǎng)絡(luò)中，無論流行病的傳染性是多711．基于SIS模型的情形設(shè)ρk(t)表示t時刻度為k的節(jié)點組中感染節(jié)點的密度，則它滿足如下微分方程：式中第一項為湮滅項，感染群體以單位速率減少(假設(shè)概率β＝1)；第二項為產(chǎn)生項，它正比于有效傳播率、易感人群的密度[1-ρk(t)]、節(jié)點的度k以及任意鄰居被感染的概率。其中，任意鄰居被感染的概率記作Θ(ρ(t))，它表示從一個度為k的節(jié)點連到度為任意k'的節(jié)點的聯(lián)合概率p(k'|k)ρk'(t)的平均。從而上式可重新描述為：1．基于SIS模型的情形72設(shè)ρk為度為k的節(jié)點組中感染個體的穩(wěn)態(tài)密度。顯然，ρk只是λ的函數(shù)，因而穩(wěn)態(tài)時相應(yīng)地概率Θ也變?yōu)棣说碾[函數(shù)。利用穩(wěn)態(tài)條件可得：(*)對于非關(guān)聯(lián)網(wǎng)絡(luò)，概率P(k'｜k)滿足：則Θ(λ)可以寫成如下自治方程：利用上式，容易求得Θ(λ)，再代入(*)式可以解得ρk。最終的感染個體穩(wěn)態(tài)密度ρ則可由下式估算：另外，由自治方程可得：(**)設(shè)ρk為度為k的節(jié)點組中感染個體的穩(wěn)態(tài)密度。顯然，ρk只是λ73顯然，該式存在一個平凡解Θ(λ)＝0。如果要使該方程存在一個非平凡解，必須滿足：即于是，可求得非均勻網(wǎng)上SIS傳播模型的閾值為：對該閾值可理解如下：當(dāng)λ＜λc，若(**)式中Θ(λ)≠0，則由Θ(λ)＞0可知：故式(**)的第二項肯定大于0，故當(dāng)λ＜λc時只有Θ(λ)＝0才能使(**)式成立。所以，只有當(dāng)λ≥λc時，才能由第二項得到不為0的Θ(λ)。顯然，該式存在一個平凡解Θ(λ)＝0。如果要使該方程存在一個74對于規(guī)模無限大的具有度分布P(k)∝k-γ(γ≤3)的網(wǎng)絡(luò)，＜k2＞=∞，對應(yīng)的λc=0。由此可見，在無標(biāo)度網(wǎng)絡(luò)中，無論傳染概率多么小，流行病都能持久存在，這個結(jié)果很好地解釋了為什么病毒與輿論可以在Internet與社會網(wǎng)絡(luò)中傳播的如此快。對于規(guī)模無限大的具有度分布P(k)∝k-γ(γ≤3)的網(wǎng)絡(luò)，752.基于SIR模型的情形假設(shè)一個度為k的節(jié)點組中處于易感狀態(tài)、感染狀態(tài)和移除狀態(tài)的個體的密度分別表示為sk(t)、ik(t)和rk(t)，則它們滿足約束關(guān)系：與SIS模型分析類似，令

，可以得到下列動力學(xué)演化方程：2.基于SIR模型的情形76上述方程組初始條件為rk(0)=0、ik(0)=i0和sk(0)=1-i0。在極限i0→0時，我們可取ik(0)≈0，sk(0)≈1。在該近似條件下，由演化方程的第一個方程可得：其中，為如下的輔助函數(shù)(考慮演化方程的第三個方程)：其導(dǎo)數(shù)可簡化為：由此我們得到了關(guān)于的一個自治方程，它在給定的P(k)條件下可以求解。一旦得到，就可以得到

，從而由可得：上述方程組初始條件為rk(0)=0、ik(0)=i0和sk(77由于得到，從而可以得到關(guān)于的自治方程：為了得到非平凡解(非零解)，必須滿足如下條件：于是從而得到閾值為這個結(jié)果與SIS模型完全相同。由于得到，從而可以78在SIS傳播模型下，比較在相同平均度條件下WS小世界網(wǎng)絡(luò)與BA無標(biāo)度網(wǎng)絡(luò)的傳播規(guī)律(傳染率λ和感染個體的穩(wěn)態(tài)密度ρ的關(guān)系)，如下圖所示。

WS小世界網(wǎng)絡(luò)和BA無標(biāo)度網(wǎng)絡(luò)的傳播規(guī)律比較BA無標(biāo)度網(wǎng)絡(luò)的參數(shù)m=3，其平均度為2m等于6，取WS小世界網(wǎng)絡(luò)的參數(shù)＜k＞=6?？梢?，BA網(wǎng)絡(luò)的傳染率連續(xù)而平滑地過渡到0，說明無標(biāo)度網(wǎng)絡(luò)不存在正傳播閾值。對于BA網(wǎng)絡(luò)，只要傳染率大于0，病毒都能傳播并最終維持在一個穩(wěn)定態(tài)，這也反映了BA網(wǎng)絡(luò)對病毒傳播的脆弱性。ρλ在SIS傳播模型下，比較在相同平均度條件下WS小世界網(wǎng)絡(luò)與B79幾種網(wǎng)絡(luò)傳播臨界值比較幾種網(wǎng)絡(luò)傳播臨界值比較80群落網(wǎng)結(jié)構(gòu)對流行病傳播的影響社團結(jié)構(gòu)一般都具有群落結(jié)構(gòu)，群落可以由同事、朋友、同學(xué)或俱樂部成員等組成。在社會網(wǎng)絡(luò)中，各群落內(nèi)部成員聯(lián)系緊密；相反，在不同群落之間則聯(lián)系較少。群落網(wǎng)絡(luò)的結(jié)構(gòu)示意圖如圖所示。群落結(jié)構(gòu)的存在必然影響流行病的傳播。本小節(jié)重點探討群落結(jié)構(gòu)對流行病傳播的影響。含三個社團的社團網(wǎng)絡(luò)結(jié)構(gòu)示意圖(社團內(nèi)實線連接，社團間虛線連接)群落網(wǎng)結(jié)構(gòu)對流行病傳播的影響社團結(jié)構(gòu)一般都具有群落結(jié)構(gòu)，群落81社會網(wǎng)絡(luò)通常具備高的集聚系數(shù)，群落內(nèi)的連線密度高，而群落間的連線密度低。假設(shè)我們將產(chǎn)生一個含有N個節(jié)點、m個組的群落網(wǎng)模型，提出如下簡單方法來構(gòu)造群落網(wǎng)絡(luò)：步驟1：初始化。將N個節(jié)點隨機分成m個組，每組內(nèi)的節(jié)點數(shù)為ni(i=1，2，…，m)，即步驟2：群落內(nèi)連線。每個組內(nèi)的節(jié)點間以概率p連線，從而組i內(nèi)的連線數(shù)為。步驟3：群落間連線。任意兩個組間的節(jié)點間以概率q連線，從而組i和組j間的連線數(shù)為。通過上述構(gòu)造方法，最終得到的網(wǎng)絡(luò)總邊數(shù)為

社會網(wǎng)絡(luò)通常具備高的集聚系數(shù)，群落內(nèi)的連線密度高，而群落間的82令序參量σ=p／q表示群落化的程度，則對于群落網(wǎng)絡(luò)應(yīng)該有σ>>１。如果σ=1，則上述方法得到的網(wǎng)絡(luò)將退化為一般的隨機網(wǎng)絡(luò)。如果給定總邊數(shù)M、總節(jié)點數(shù)N及群落劃分方案和序參量σ，則概率p和q可由下式給定：令序參量σ=p／q表示群落化的程度，則對于群落網(wǎng)絡(luò)應(yīng)該有σ>83社團網(wǎng)絡(luò)上的流行病傳播用SIS模型來討論流行病在群落網(wǎng)中的傳播規(guī)律。假定易感個體以概率α與每個周圍的感染個體接觸。若節(jié)點vj處于易感狀態(tài)且有kj個鄰居，它們中有kinf個處于感染狀態(tài)，則在每個時間步，節(jié)點vj將以概率變?yōu)楦腥緺顟B(tài)。同時每個感染節(jié)點以概率β變?yōu)橐赘袪顟B(tài)。同前面的討論一樣，為簡單起見，這里令λ=α／β，β=1。假定初始時有一粒種子，則它的每個鄰居將以λ的概率被感染，然后再感染它們的鄰居。一定時間后，感染達到穩(wěn)態(tài)。社團網(wǎng)絡(luò)上的流行病傳播用SIS模型來討論流行病在群落網(wǎng)中的傳84對于λ＜λc，穩(wěn)態(tài)為0；而對于λ＞λc，穩(wěn)態(tài)為非零。由于群落網(wǎng)絡(luò)的非均勻結(jié)構(gòu)，最終的狀態(tài)依賴于選取的種子及網(wǎng)絡(luò)構(gòu)型，因此有意義的結(jié)果必須為對各種網(wǎng)絡(luò)構(gòu)型及各種初始條件的平均。對具有σ>>１的群落網(wǎng)，當(dāng)λ較小時，傳播會限制在種子所在的群落內(nèi)。從統(tǒng)計意義上看，可以認為種子被均勻選取在每個社團。對于每個特定的群落i，其閾值λc(i)由其平均連線數(shù)決定。當(dāng)群落間的連線遠小于群落內(nèi)的連線時，有且此關(guān)系對所有的種子成立。整個系統(tǒng)的λc為不同構(gòu)型及不同實現(xiàn)的平均，即對不同的種子平均，因此λc與p間的定量關(guān)系為λc～1／p。對于λ＜λc，穩(wěn)態(tài)為0；而對于λ＞λc，穩(wěn)態(tài)為非零。85其中a為一常數(shù)。因此λc與M成反比。對于給定的M，上式可被寫為：這就是λc對群落程度σ的依賴關(guān)系。隨著群落度的降低，流行病的傳播閾值將增加并在隨機網(wǎng)時達到極大值。換句話說，流行病在隨機網(wǎng)上比在群落網(wǎng)上更不容易爆發(fā)。通過前面的討論，還可以得到一個結(jié)論：傳染病本身的動力學(xué)性質(zhì)和個體所在的網(wǎng)絡(luò)結(jié)構(gòu)共同決定了流行病的傳染行為和傳染過程。網(wǎng)絡(luò)動力學(xué)課件86無標(biāo)度網(wǎng)絡(luò)是很容易受到病毒感染而導(dǎo)致病毒流行的，因此選擇合適的免疫策略顯得非常重要。人們針對免疫策略作了較多的研究，通常根據(jù)節(jié)點在網(wǎng)絡(luò)中的地位(例如以節(jié)點的度來衡量)來關(guān)注節(jié)點的選擇。下面簡要介紹復(fù)雜網(wǎng)絡(luò)的三種免疫策略：隨機免疫、目標(biāo)免疫和熟人免疫。無標(biāo)度網(wǎng)絡(luò)是很容易受到病毒感染而導(dǎo)致病毒流行的，因此選擇合適87隨機免疫完全隨機地選取網(wǎng)絡(luò)中的一部分節(jié)點進行免疫。免疫節(jié)點不會再被感染，所以它們不會再影響它們的鄰居。針對均勻網(wǎng)絡(luò)，容易得出隨機免疫的免疫臨界值為：對于無標(biāo)度網(wǎng)絡(luò)來說，推導(dǎo)，可以得到此時隨機免疫的免疫臨界值gc為顯然，隨著網(wǎng)絡(luò)規(guī)模的無限增長，無標(biāo)度網(wǎng)絡(luò)的＜k2＞→∞，其傳播閾值λc趨于0，而免疫臨界值gc趨于1。這表明，如果對于無標(biāo)度網(wǎng)絡(luò)采取隨機免疫策略，則需要對網(wǎng)絡(luò)幾乎所有節(jié)點都實施免疫才能保證最終消滅病毒傳染。隨機免疫完全隨機地選取網(wǎng)絡(luò)中的一部分節(jié)點進行免疫。88目標(biāo)免疫根據(jù)無標(biāo)度網(wǎng)絡(luò)的不均勻特性，選取少量度最大的節(jié)點進行免疫。就BA無標(biāo)度網(wǎng)絡(luò)而言，目標(biāo)免疫對應(yīng)的免疫臨界值為：上式表明，即使傳染率λ在很大的范圍內(nèi)取不同的值，都可以得到很小的免疫臨界值。因此，有選擇地對無標(biāo)度網(wǎng)絡(luò)進行目標(biāo)免疫，其臨界值要比隨機免疫小得多。目標(biāo)免疫根據(jù)無標(biāo)度網(wǎng)絡(luò)的不均勻特性，選取少量度最大的節(jié)點進行89

對BA無標(biāo)度網(wǎng)絡(luò)采取隨機免疫和目標(biāo)免疫的對比上圖橫坐標(biāo)為免疫密度g，縱坐標(biāo)為ρg/ρ0，ρ0表示網(wǎng)絡(luò)未加免疫的穩(wěn)態(tài)感染密度，ρg為網(wǎng)絡(luò)中加入比例為g的免疫節(jié)點后的穩(wěn)態(tài)感染密度。可以看出，隨機免疫和目標(biāo)免疫在無標(biāo)度網(wǎng)絡(luò)中存在著明顯的臨界值差別。在隨機免疫情況下，隨著免疫密度g的增大，最終的被感染程度下降緩慢，只有當(dāng)g=1時，才能使被感染數(shù)為零。而在目標(biāo)免疫的情況下，gc≈0.16，這意味著只要對少量度很大節(jié)點進行免疫，就能消除無標(biāo)度網(wǎng)絡(luò)中的病毒擴散。對BA無標(biāo)度網(wǎng)絡(luò)90熟人免疫:對隨機選出的節(jié)點的鄰居進行免疫，該策略基本思想是：從N個節(jié)點中隨機選出比例為s的節(jié)點，再從每一個被選出的節(jié)點中隨機選擇它的某個鄰居節(jié)點進行免疫。

無標(biāo)度網(wǎng)絡(luò)中免疫臨界值隨冪律指數(shù)的變化情況10.80.60.40.2022.533.5γgc熟人免疫:對隨機選出的節(jié)點的鄰居進行免疫，該策略基本思想是：91復(fù)雜網(wǎng)絡(luò)上的輿論演化動力學(xué)輿論及其特性輿論是由許許多多的社會個體的意見相互作用而形成的，其發(fā)展變化受到自然、社會、經(jīng)濟、文化、政治、法律等各種因素的影響，它的演化過程具有：復(fù)雜性開放性不確定性非平衡性自組織性等特性。協(xié)議是社會群體中非常重要的方面之一，每天的日常生活都需要人們達到共識，而協(xié)議使得組織更協(xié)調(diào)有效并可以擴展在社會上的影響力。復(fù)雜網(wǎng)絡(luò)上的輿論演化動力學(xué)輿論及其特性92輿論傳播的動力學(xué)行為也服從SIR模型。但是它的三種狀態(tài)和流行病中的三種狀態(tài)S、I、R代表：不知道消息的人群，知道消息的并有能力繼續(xù)傳播消息的人群，及知道消息但已經(jīng)失去傳播能力或興趣的人群。假設(shè)網(wǎng)絡(luò)上有N個節(jié)點，每個節(jié)點代表一個可傳播消息的個人，他們傳播消息的行為方式如下：如果得到了一個消息(I態(tài))，那么他就有興趣把這個消息傳播出去，在傳播過程中，他將隨機地從鄰居中選取一人并將消息傳給他，如果這個鄰居不知道這個消息(S態(tài))，則該鄰居就得到此消息(I態(tài))，并進行下一輪的傳播。但如果他的鄰居已經(jīng)知道了這個消息，那么傳播消息的人會認為該消息失去了繼續(xù)傳播的價值，并失去傳播該消息的興趣(R態(tài))。整個過程可由以下關(guān)系簡單地表示出來：輿論傳播的動力學(xué)行為也服從SIR模型。但是它的三種狀態(tài)和流行93假設(shè)在一個有限網(wǎng)絡(luò)中所有的節(jié)點都處于S態(tài)，在某一時刻突然有一個節(jié)點得到了一個新的消息，它將成為I態(tài)。那么按照上面所定義的規(guī)則，這個消息將在網(wǎng)絡(luò)中傳播，直到最終網(wǎng)絡(luò)中沒有I態(tài)的節(jié)點為止。稱這個狀態(tài)為終態(tài)。對于相同平均度的網(wǎng)絡(luò)，無標(biāo)度網(wǎng)比隨機網(wǎng)絡(luò)具有更多度大的節(jié)點，因此無標(biāo)度網(wǎng)中的消息可較容易的傳遞給大節(jié)點然后再到其他節(jié)點。一旦大節(jié)點處于I態(tài)或R態(tài)，其他節(jié)點因為以較大概率連接到它們，從而更容易變成R態(tài)；而隨機網(wǎng)則沒有這個特點。因此，輿論在無標(biāo)度網(wǎng)絡(luò)上的傳播要比在隨機網(wǎng)絡(luò)上結(jié)束得快，從而導(dǎo)致無標(biāo)度網(wǎng)的總感染密度比隨機網(wǎng)的小。網(wǎng)絡(luò)動力學(xué)課件94網(wǎng)絡(luò)的同步早在三百多年前，物理學(xué)家惠更斯在給父親的信里提到他臥病在床的幾天中驚奇的發(fā)現(xiàn)，掛在同一個橫梁上的兩個鐘擺在一段時間以后會出現(xiàn)同步的擺動現(xiàn)象。這種現(xiàn)象發(fā)生的原因是它們通過懸掛其上的橫粱相互作用。除了這種兩個個體相互作用產(chǎn)生的同步現(xiàn)象之外，很多重要的同步現(xiàn)象出現(xiàn)在多體系統(tǒng)中。網(wǎng)絡(luò)的同步95隨著對復(fù)雜網(wǎng)絡(luò)研究的深入，復(fù)雜網(wǎng)絡(luò)上的同步問題開始被廣泛關(guān)注?？紤]一個耦合動力學(xué)系統(tǒng)，其拓撲結(jié)構(gòu)是一個復(fù)雜網(wǎng)絡(luò)。系統(tǒng)中的各個節(jié)點在與外界孤立時，其演化方式是混沌的。初始時刻，各個點的狀態(tài)隨機分布，各不相同，經(jīng)過一段時間的過渡之后，各點的狀態(tài)可能會趨于相同，達到同步態(tài)。人們研究的重點是：網(wǎng)絡(luò)的拓撲結(jié)構(gòu)是如何影響其同步能力的。主要介紹多種不同混沌同步方式的定義，包括完全同步、廣義同步、相位同步和滯后同步等。隨著對復(fù)雜網(wǎng)絡(luò)研究的深入，復(fù)雜網(wǎng)絡(luò)上的同步問題開始被廣泛關(guān)注96混沌同步的定義通俗的講，同步是指兩個或多個系統(tǒng)，在外部驅(qū)動或者相互耦合的作用下。調(diào)整它們的某個動態(tài)性質(zhì)以達到具有相同性質(zhì)的過程。所謂混沌同步，指的是對于從不同的初始條件出發(fā)的兩個混沌系統(tǒng)，隨著時間的推移，它們的軌跡逐漸一致。一組動力單元(全同或者不全同)，通過一定的相互作用或者外界的驅(qū)動，使得它們的某種運動性質(zhì)趨于相同，我們就說這組單元達到了同步。同步廣泛存在于自然界和社會生活