(2021年整理)復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)知識(shí)

復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)知識(shí)復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)知識(shí)#下的近似表達(dá)式：f(x)沁——.]arctanh-—2jx2下的近似表達(dá)式：f(x)沁——.]arctanh-—2jx2+2-勺-+22-20)度分布對(duì)于WS小世界網(wǎng)絡(luò)，當(dāng)k$K/2時(shí)有:“、min《—于卩廠一“、K—(pK/2)k-T—n十P(k)=ECK/2(1—p)np!—n-e-于n(k—K/2—n)!n=0(2—21)當(dāng)kVK/2時(shí)，P(k)=0.對(duì)于NW小世界網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)的度至少為K,因此當(dāng)QK時(shí)，一個(gè)隨機(jī)選取的節(jié)點(diǎn)的度為k的概率為:(2—22)當(dāng)kVK時(shí)，P(k)=0。類(lèi)似ER隨機(jī)網(wǎng)絡(luò)模型，WS小世界網(wǎng)絡(luò)模型也是所有節(jié)點(diǎn)的度都近似相等的均勻網(wǎng)絡(luò)綜上所述,ER隨機(jī)網(wǎng)絡(luò)、WS小世界網(wǎng)絡(luò)和NW小世界網(wǎng)絡(luò)的度分布可近似用Poisson分布來(lái)表示，該分布在度的平均值＜k＞處有一峰值，然后按指數(shù)快速衰減。這類(lèi)網(wǎng)絡(luò)被稱(chēng)為均勻網(wǎng)絡(luò)(homogeneousnetwork)或指數(shù)網(wǎng)絡(luò)(exponentialnetwork)。2o3o4無(wú)標(biāo)度網(wǎng)絡(luò)(scale—freenetwork)近年來(lái)，大量的實(shí)證研究表明，許多大規(guī)模真實(shí)網(wǎng)絡(luò)(如WWW、Internet以及

新陳代謝網(wǎng)絡(luò)等)的度分布函數(shù)都是呈幕律分布的形式：P(k)*k。在這樣的網(wǎng)絡(luò)中，大部分節(jié)點(diǎn)的度都很小，但也有一小部分節(jié)點(diǎn)具有很大的度，沒(méi)有一個(gè)特征標(biāo)度?由于這類(lèi)網(wǎng)絡(luò)的節(jié)點(diǎn)的連接度并沒(méi)有明顯的特征標(biāo)度，故稱(chēng)為“無(wú)標(biāo)度網(wǎng)絡(luò)"。為了解釋實(shí)際網(wǎng)絡(luò)中幕律分布產(chǎn)生的機(jī)理，Barabdsi和Albert在1999年提出了一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)模型，稱(chēng)為BA無(wú)標(biāo)度模型。該模型的構(gòu)造主要基于現(xiàn)實(shí)網(wǎng)絡(luò)的兩個(gè)內(nèi)在機(jī)制:①增長(zhǎng)機(jī)制：大多數(shù)真實(shí)網(wǎng)絡(luò)是一個(gè)開(kāi)放系統(tǒng)，隨著時(shí)間的推移，網(wǎng)絡(luò)規(guī)模將不斷增大，即網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)和連邊數(shù)是不斷增加的。②擇優(yōu)連接：新增加的節(jié)更傾向于與那些具有較高連接度的節(jié)點(diǎn)相連。也就是富人更富的觀點(diǎn)(richgetricher)。BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造算法：(1)增長(zhǎng)：在初始時(shí)刻，假定網(wǎng)絡(luò)中己有m個(gè)節(jié)點(diǎn)，在以后的每一個(gè)時(shí)間步長(zhǎng)中，增加一個(gè)連接度為m的節(jié)點(diǎn)(mWm),新增節(jié)點(diǎn)與網(wǎng)絡(luò)中已經(jīng)存在的m個(gè)不同的節(jié)點(diǎn)相連,且不存在重復(fù)連接。(2)優(yōu)先連接:在選擇新節(jié)點(diǎn)的連接點(diǎn)時(shí)，一個(gè)新節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連的概率n與節(jié)點(diǎn)i的度k成正比：(2—23)經(jīng)過(guò)t步后,這種算法能夠產(chǎn)生一個(gè)含有N=t+m個(gè)節(jié)點(diǎn)、mt條邊的網(wǎng)絡(luò)。如圖2-12所示的是m=m=2時(shí)，BA網(wǎng)絡(luò)的演化過(guò)程。初始網(wǎng)絡(luò)有兩個(gè)節(jié)點(diǎn)，每次新增加的一個(gè)節(jié)點(diǎn)按優(yōu)先連接機(jī)制與網(wǎng)絡(luò)中已經(jīng)存在的兩個(gè)節(jié)點(diǎn)相連。

圖2—12BA圖2—12BA無(wú)標(biāo)度網(wǎng)絡(luò)的演化過(guò)程(取自文獻(xiàn)[])BA無(wú)標(biāo)度網(wǎng)絡(luò)模型具有如下基本特性：(1)平均路徑長(zhǎng)度BA無(wú)標(biāo)度網(wǎng)絡(luò)的平均路徑長(zhǎng)度為：2—24)L乂f2—24)loglogN這表明BA無(wú)標(biāo)度網(wǎng)絡(luò)也具有小世界性。2)簇系數(shù)'m+1'In1m丿m+1Im+1Itm2(m+1)2C=—4(m一1)(2—25)與ER隨機(jī)網(wǎng)絡(luò)類(lèi)似，當(dāng)網(wǎng)絡(luò)規(guī)模充分大時(shí)，BA無(wú)標(biāo)度網(wǎng)絡(luò)不具有明顯的聚類(lèi)特性。度分布BA無(wú)標(biāo)度網(wǎng)絡(luò)的度分布計(jì)算主要有三種方法：①平均場(chǎng)理論(mean—fieldapproach)；②主方程法(master—equationapproach)；③速率方程法(rate-equationapproach)。三種方法得到的漸近結(jié)果相同。其中，主方程法和速率方程法等價(jià).分析計(jì)算可得：p（p（k）二k（；:2）2m2k_32-26)這表明BA無(wú)標(biāo)度網(wǎng)絡(luò)的度分布可以由幕指數(shù)為3的幕律函數(shù)來(lái)近似描述，圖213所示為網(wǎng)絡(luò)規(guī)模為N=104的BA無(wú)標(biāo)度網(wǎng)絡(luò)的度分布。圖2圖2。13BA無(wú)標(biāo)度網(wǎng)絡(luò)的度分布（n=100000），（取自文獻(xiàn)】］）下面比較WS小世界網(wǎng)絡(luò)模型、BA無(wú)標(biāo)度網(wǎng)絡(luò)模型與真實(shí)網(wǎng)絡(luò)的主要性質(zhì)的異同。如表2—1所示，小世界網(wǎng)絡(luò)和無(wú)標(biāo)度網(wǎng)絡(luò)各自捕捉到了真實(shí)網(wǎng)絡(luò)三個(gè)主要性質(zhì)中的兩個(gè)。后來(lái)，學(xué)者們又建立了許多模型來(lái)更好地體現(xiàn)真實(shí)網(wǎng)絡(luò)的所有特性，但由于這兩種網(wǎng)絡(luò)模型規(guī)則簡(jiǎn)潔，并抓住了復(fù)雜網(wǎng)絡(luò)的基本性質(zhì)，到目前依然是使用最