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

20第二章復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)知識(shí)網(wǎng)絡(luò)的概念所謂“網(wǎng)絡(luò)”(networks),實(shí)際上就是節(jié)點(diǎn)(node)和連邊(edge)的集合。如果節(jié)點(diǎn)對(duì)(i,j)與(j,i)對(duì)應(yīng)為同一條邊，那么該網(wǎng)絡(luò)為無(wú)向網(wǎng)絡(luò)(undirectednetworks),否則為有向網(wǎng)絡(luò)(directednetworks)。如果給每條邊都賦予相應(yīng)的權(quán)值，那么該網(wǎng)絡(luò)就為加權(quán)網(wǎng)絡(luò)(weightednetworks)，否則為無(wú)權(quán)網(wǎng)絡(luò)(unweightednetworks)，如圖2-1所示。⑧⑤?圖2-1網(wǎng)絡(luò)類(lèi)型示例(a)無(wú)權(quán)無(wú)向網(wǎng)絡(luò)(b)加權(quán)網(wǎng)絡(luò)(c)無(wú)權(quán)有向網(wǎng)絡(luò)如果節(jié)點(diǎn)按照確定的規(guī)則連邊，所得到的網(wǎng)絡(luò)就稱為“規(guī)則網(wǎng)絡(luò)"(regularnetworks)，如圖2-2所示。如果節(jié)點(diǎn)按照完全隨機(jī)的方式連邊，所得到的網(wǎng)絡(luò)就稱為“隨機(jī)網(wǎng)絡(luò)"(randomnetworks)。如果節(jié)點(diǎn)按照某種(自)組織原則的方式連邊，將演化成各種不同的網(wǎng)絡(luò)，稱為“復(fù)雜網(wǎng)絡(luò)"(complexnetworks)o圖2-2規(guī)則網(wǎng)絡(luò)示例(a)一維有限規(guī)則網(wǎng)絡(luò)(b)二維無(wú)限規(guī)則網(wǎng)絡(luò)2.2復(fù)雜網(wǎng)絡(luò)的基本特征量描述復(fù)雜網(wǎng)絡(luò)的基本特征量主要有：平均路徑長(zhǎng)度(averagepathlength)、簇系數(shù)(clusteringefficient)、度分布(degreedistribution)、介數(shù)(betweenness)等，下面介紹它們的定義。2.2.1平均路徑長(zhǎng)度(averagepathlength)定義網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)，和j之間的距離/j為從其中一個(gè)節(jié)點(diǎn)出發(fā)到達(dá)另一個(gè)節(jié)點(diǎn)所要經(jīng)過(guò)的連邊的最少數(shù)目。定義網(wǎng)絡(luò)的直徑(diameter)為網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間距離的最大值。即D=max{/}

iji,j(2-1)定義網(wǎng)絡(luò)的平均路徑長(zhǎng)度L為網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間距離的平均值。即L.2七iniN(N—1)ji=1j=i+1(2-2)其中N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，不考慮節(jié)點(diǎn)自身的距離。網(wǎng)絡(luò)的平均路徑長(zhǎng)度L又稱為特征路徑長(zhǎng)度(characteristicpathlength)。網(wǎng)絡(luò)的平均路徑長(zhǎng)度L和直徑D主要用來(lái)衡量網(wǎng)絡(luò)的傳輸效率。2.2.2簇系數(shù)(clusteringefficient)假設(shè)網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)i有勺條邊將它與其它節(jié)點(diǎn)相連，這ki個(gè)節(jié)點(diǎn)稱為節(jié)點(diǎn)i的鄰居節(jié)點(diǎn)，在這ki個(gè)鄰居節(jié)點(diǎn)之間最多可能有ki(ki-1)/2條邊。節(jié)點(diǎn)i的ki個(gè)鄰居節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)Ni和最多可能有的邊數(shù)ki(ki-1)/2之比就定義為節(jié)點(diǎn)i的簇系數(shù)，記為C.。即「2N.C=1——ik.(k.-1)ii(2-3)整個(gè)網(wǎng)絡(luò)的聚類(lèi)系數(shù)定義為網(wǎng)絡(luò)中所有節(jié)點(diǎn)i的聚類(lèi)系數(shù)Ci的平均值，記為。。即(2-4)廠1T廠

C(2-4)Nii=1顯然，0C1之間。當(dāng)C=0時(shí)，說(shuō)明網(wǎng)絡(luò)中所有節(jié)點(diǎn)均為孤立節(jié)點(diǎn)，即沒(méi)有任何連邊。當(dāng)C=1時(shí)，說(shuō)明網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)都直接相連，即網(wǎng)絡(luò)是全局耦合網(wǎng)絡(luò)。2.2.3度分布(degreedistribution)網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)i的度勺定義為與該節(jié)點(diǎn)相連接的其它節(jié)點(diǎn)的數(shù)目，也就是該節(jié)點(diǎn)的鄰居數(shù)。通常情況下，網(wǎng)絡(luò)中不同節(jié)點(diǎn)的度并不相同，所有節(jié)點(diǎn)i的度勺的的平均值稱為網(wǎng)絡(luò)的(節(jié)點(diǎn))平均度，記為＜k＞。即TOC\o"1-5"\h\z〈k〉=—寸k.(2-5)Ni-i=1網(wǎng)絡(luò)中節(jié)點(diǎn)的分布情況一般用度分布函數(shù)P(k)來(lái)描述。度分布函數(shù)P(k)表示在網(wǎng)絡(luò)中任意選取一節(jié)點(diǎn)，該節(jié)點(diǎn)的度恰好為k的概率。即P(k)=!寸5(k—4)(2-6)Ni=1通常，一個(gè)節(jié)點(diǎn)的度越大，意味著這個(gè)節(jié)點(diǎn)屬于網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)，在某種意義上也越“重要”。2.2.4介數(shù)(betweenness)節(jié)點(diǎn)i的介數(shù)定義為網(wǎng)絡(luò)中所有的最短路徑中，經(jīng)過(guò)節(jié)點(diǎn)i的數(shù)量。用Bi表示。即yg…(2-7)B=yminm,n豐i,m(2-7)igm,nmn式中g(shù)mn為節(jié)點(diǎn)m與節(jié)點(diǎn)n之間的最短路徑數(shù)，gm1n為節(jié)點(diǎn)m與節(jié)點(diǎn)n之間經(jīng)過(guò)節(jié)點(diǎn),的最短路徑數(shù)。節(jié)點(diǎn)的介數(shù)反映了該節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力。描述網(wǎng)絡(luò)結(jié)構(gòu)的特征量還有很多，這里就不一一介紹，在使用到它們的地方再給出詳細(xì)的說(shuō)明。2.3復(fù)雜網(wǎng)絡(luò)的基本模型人們?cè)趯?duì)不同領(lǐng)域內(nèi)的大量實(shí)際網(wǎng)絡(luò)進(jìn)行廣泛的實(shí)證研究后發(fā)現(xiàn)：真實(shí)網(wǎng)絡(luò)系統(tǒng)往往表現(xiàn)出小世界特性、無(wú)標(biāo)度特性和高聚集特性。為了解釋這些現(xiàn)象，人們構(gòu)造了各種各樣的網(wǎng)絡(luò)模型，以便從理論上揭示網(wǎng)絡(luò)行為與網(wǎng)絡(luò)結(jié)構(gòu)之間的關(guān)系，進(jìn)而考慮改善網(wǎng)絡(luò)的行為。下面介紹幾類(lèi)基本的網(wǎng)絡(luò)模型。規(guī)則網(wǎng)絡(luò)(regularnetwork)常見(jiàn)的規(guī)則網(wǎng)絡(luò)有三種：全局耦合網(wǎng)絡(luò)(globallycouplednetwork)、最近鄰耦合網(wǎng)絡(luò)(nearest-neighborcouplednetwork)和星型網(wǎng)絡(luò)模型(starcouplednetwork),如圖2-3所示。圖2-3三種典型的規(guī)則網(wǎng)絡(luò)(a)全局耦合網(wǎng)絡(luò)(b)最近鄰耦合網(wǎng)絡(luò)(c)星型網(wǎng)絡(luò)圖2-3(a)所示為一個(gè)含有N個(gè)節(jié)點(diǎn)的全局耦合網(wǎng)絡(luò)。網(wǎng)絡(luò)中共有N(N-1)/2條邊，其平均路徑長(zhǎng)度L=1(最小)，簇系數(shù)C=1(最大)。度分布P(后為以N-1為中心的3函數(shù)。模型的優(yōu)點(diǎn)：能反映實(shí)際網(wǎng)絡(luò)的小世界特性和大聚類(lèi)特性。模型的缺點(diǎn)：不能反映實(shí)際網(wǎng)絡(luò)的稀疏特性。因?yàn)橐粋€(gè)具有N個(gè)節(jié)點(diǎn)的全局耦合網(wǎng)絡(luò)的邊的數(shù)目為0(N2),而實(shí)際網(wǎng)絡(luò)的邊的數(shù)目一般是0(N)。圖2-3(b)所示為一個(gè)含有N個(gè)節(jié)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)只和它周?chē)泥従庸?jié)點(diǎn)相連，其中每個(gè)節(jié)點(diǎn)都與它左右各K/2個(gè)鄰居節(jié)點(diǎn)相連(K為偶數(shù))。對(duì)于固定的K值，網(wǎng)絡(luò)的平均路徑長(zhǎng)度為:NL氏-8(N-⑹2K(2-8)對(duì)于較大的K值，最近鄰耦合網(wǎng)絡(luò)的簇系數(shù)為:「3(K—2)3?4(K-1)4(2-9)度分布P(k)為以K為中心的^函數(shù)。模型的優(yōu)點(diǎn)：能反映實(shí)際網(wǎng)絡(luò)的大聚類(lèi)特性和稀疏特性。模型的缺點(diǎn)：不能反映實(shí)際網(wǎng)絡(luò)的小世界特性。圖2-3(c)所示為一個(gè)具有N個(gè)節(jié)點(diǎn)的星型網(wǎng)絡(luò)。網(wǎng)絡(luò)有一個(gè)中心節(jié)點(diǎn)，其余N-1個(gè)節(jié)點(diǎn)都只與這個(gè)中心節(jié)點(diǎn)相連，且它們彼此之間不連接。網(wǎng)絡(luò)的平均路徑長(zhǎng)度：L-2-2(N-1)-2(N—8)N(N-1)(2-10)網(wǎng)絡(luò)的簇系數(shù)為：N-1C-1(N—8)N(2-11)網(wǎng)絡(luò)的度分布為：…(K=1)N(2-12)P(K)=4-L(K=N-1)(2-12)N_0其它規(guī)定：如果一個(gè)節(jié)點(diǎn)只有一個(gè)鄰居，那么該節(jié)點(diǎn)的簇系數(shù)為1。也有些文獻(xiàn)規(guī)定只有一個(gè)鄰居的節(jié)點(diǎn)的簇系數(shù)為0，若依此定義，則星型網(wǎng)絡(luò)的簇系數(shù)為0。模型的優(yōu)點(diǎn)：能反映實(shí)際網(wǎng)絡(luò)的小世界特性和稀疏特性。模型的缺點(diǎn)：不能反映實(shí)際網(wǎng)絡(luò)的大聚類(lèi)特性。ER隨機(jī)網(wǎng)絡(luò)(randomnetwork)該模型由匈牙利數(shù)學(xué)家Edds和Renyi在上世紀(jì)50年代最先提出，所以被人們稱為ER隨機(jī)網(wǎng)絡(luò)模型。ER隨機(jī)網(wǎng)絡(luò)的構(gòu)造有兩種方法。第一種方法：定義有標(biāo)記的N個(gè)節(jié)(網(wǎng)絡(luò)中的節(jié)點(diǎn)總數(shù))，并且給出整個(gè)網(wǎng)絡(luò)的邊數(shù)n,這些邊的選取采用從所有可能的N(N-1)/2種情況中隨機(jī)選取。第二種方法：給定有標(biāo)記的N個(gè)節(jié)點(diǎn)，以一定的隨機(jī)概率p連接所有可能出現(xiàn)的N(N-1)/2種連接，假設(shè)最初有N個(gè)孤立的節(jié)點(diǎn)，每對(duì)節(jié)點(diǎn)以隨機(jī)概率p進(jìn)行連接。如圖2-4所示。圖2-4ER圖2-4ER隨機(jī)網(wǎng)絡(luò)的演化示意圖(a)p=0時(shí)，給定10個(gè)孤立節(jié)點(diǎn)；(b)?(c)p=0.1,0.15時(shí)，生成的隨機(jī)圖ER隨機(jī)網(wǎng)絡(luò)模型具有如下基本特性：(1)涌現(xiàn)或相變

如果當(dāng)N時(shí)產(chǎn)生一個(gè)具有性質(zhì)Q的ER隨機(jī)圖的概率為1,那么幾乎每一個(gè)ER隨機(jī)圖都具有性質(zhì)Q。以連通性為例，若當(dāng)連接概率p達(dá)到某個(gè)臨界值pc-（lnN）/N時(shí)，整個(gè)網(wǎng)絡(luò)連通起來(lái)，那么以概率p生成的每一個(gè)網(wǎng)絡(luò)幾乎都是連通的，否則，當(dāng)p如果當(dāng)N（2）度分布對(duì)于一個(gè)給定連接概率為p的隨機(jī)網(wǎng)絡(luò)，若網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)N充分大，則網(wǎng)絡(luò)的度分布接近泊松（Poission）分布，如圖2-5所示。(k〉k(2-13)P(k)=Ckpk(1-p)N-1-kXl^e—〈(2-13)N-1k!式中＜k式中＜k＞=p（N-1）PN表示ER隨機(jī)網(wǎng)絡(luò)的平均度。圖2-5ER隨機(jī)網(wǎng)絡(luò)的度分布（取自文獻(xiàn)［］）（3）平均路徑長(zhǎng)度假定網(wǎng)絡(luò)的平均路徑長(zhǎng)度為L(zhǎng)，從網(wǎng)絡(luò)的一端走到網(wǎng)絡(luò)的另一端，總步數(shù)大概為L(zhǎng)。由于ER隨機(jī)網(wǎng)絡(luò)的平均度為＜k"對(duì)于任意一個(gè)節(jié)點(diǎn)，其一階鄰居的數(shù)目為＜k＞,二階鄰居的數(shù)目為＜k＞2,以此類(lèi)推，當(dāng)經(jīng)過(guò)L步后遍歷了網(wǎng)絡(luò)的所有節(jié)點(diǎn)，因此對(duì)于規(guī)模為N的隨機(jī)網(wǎng)絡(luò)，有＜k＞l=N。由此可以得到網(wǎng)絡(luò)的平均路徑長(zhǎng)度為：lnNlnN(2-14)L(2-14)ln(pN)l爪k〉

由于lnN的值隨N增長(zhǎng)較慢，所以規(guī)模很大的ER隨機(jī)網(wǎng)絡(luò)具有很小的平均路徑長(zhǎng)度，如圖2-6所示。圖2-6ER圖2-6ER隨機(jī)網(wǎng)絡(luò)的平均路徑長(zhǎng)度與網(wǎng)絡(luò)規(guī)模的關(guān)系（取自文獻(xiàn)［］）sTHU2WJTHSUJQvsdLUAB（4）簇系數(shù)在ER隨機(jī)網(wǎng)絡(luò)中，由于任何兩個(gè)節(jié)點(diǎn)之間的連接概率p都相等，所以ER隨機(jī)網(wǎng)絡(luò)的聚類(lèi)系數(shù)為：（2-15）可見(jiàn)，當(dāng)網(wǎng)絡(luò)規(guī)模N固定時(shí)，簇系數(shù)隨著網(wǎng)絡(luò)節(jié)點(diǎn)平均度＜k＞的增加而增加，如圖2-7所示。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)平均度＜k＞固定時(shí)，簇系數(shù)隨著網(wǎng)絡(luò)規(guī)模N的增加而下降，如圖2-8和所示。顯然，當(dāng)N較大時(shí)，ER隨機(jī)網(wǎng)絡(luò)的簇系數(shù)很小。

卜白iKjornnetwork圖2-7(N=104)卜白iKjornnetwork圖2-7(N=104)ER隨機(jī)網(wǎng)絡(luò)的簇系數(shù)與連接概率的關(guān)系(取自文獻(xiàn)[])randomnetwork1001DMSIZEOFTHENF?ORKS(N)圖2-8(p=0.0015)ER隨機(jī)網(wǎng)絡(luò)的簇系數(shù)與網(wǎng)絡(luò)規(guī)模的關(guān)系(取自文獻(xiàn)[])模型的優(yōu)點(diǎn)：能反映實(shí)際網(wǎng)絡(luò)的小世界特性。模型的缺點(diǎn)：不能反映實(shí)際網(wǎng)絡(luò)的大聚類(lèi)特性。小世界網(wǎng)絡(luò)(small-worldnetwork)作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)網(wǎng)絡(luò)的過(guò)渡，美國(guó)學(xué)者Watts和Strogatz于1998年設(shè)計(jì)了一個(gè)具有小的平均路徑長(zhǎng)度和大的聚類(lèi)系數(shù)的小世界網(wǎng)絡(luò)模型(small-worldnetwork),簡(jiǎn)稱WS小世界網(wǎng)絡(luò)模型。WS小世界網(wǎng)絡(luò)模型的構(gòu)造算法：(1)從規(guī)則網(wǎng)絡(luò)開(kāi)始：考慮一個(gè)含有N個(gè)節(jié)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個(gè)環(huán)，其中每一個(gè)節(jié)點(diǎn)都與它左右相鄰的各K/2個(gè)節(jié)點(diǎn)相連，K是偶數(shù)。(2)隨機(jī)化重連：以概率p隨機(jī)地重新連接網(wǎng)絡(luò)中的每一條邊，即將連邊的一個(gè)端點(diǎn)保持不變，而另一個(gè)端點(diǎn)取為網(wǎng)絡(luò)中隨機(jī)選擇的一個(gè)節(jié)點(diǎn)。其中規(guī)定，任意兩個(gè)不同的節(jié)點(diǎn)之間至多只能有一條邊，并且每個(gè)節(jié)點(diǎn)不能有邊與自身相連。為了保證網(wǎng)絡(luò)具有稀疏性，要求N>>K，這樣構(gòu)造出來(lái)的網(wǎng)絡(luò)模型具有較高聚類(lèi)系數(shù)。而隨機(jī)化重連過(guò)程大大減小了網(wǎng)絡(luò)的平均路徑長(zhǎng)度，使網(wǎng)絡(luò)模型具有小世界特性。當(dāng)p取值較小時(shí)，重連過(guò)程對(duì)網(wǎng)絡(luò)的聚類(lèi)系數(shù)影響不大。當(dāng)p=0時(shí)，模型退化為規(guī)則網(wǎng)絡(luò)，當(dāng)p=l時(shí)，模型退化為隨機(jī)網(wǎng)絡(luò)。通過(guò)調(diào)節(jié)p的值就可以控制模型從完全規(guī)則網(wǎng)絡(luò)到完全隨機(jī)網(wǎng)絡(luò)的過(guò)渡，如圖2-9所示.隨機(jī)枇重連圖2-9WS小世界網(wǎng)絡(luò)模型(取自文獻(xiàn)[])WS小世界網(wǎng)絡(luò)模型的其聚類(lèi)系數(shù)和平均路徑長(zhǎng)度可以看作是重連概率p的函數(shù)，分別記為C(p)和L(p)，它們的變化規(guī)律如圖2-10所示。在某個(gè)p值范圍內(nèi)，WS網(wǎng)絡(luò)模型可以得到既有較短的平均路徑長(zhǎng)度(小世界特性)，又有較高聚類(lèi)系數(shù)(高聚集特性)。圖2-10中p值在0.0l附近的網(wǎng)絡(luò)即兼具這兩方一面的特征。

too.a0.0*lttoo.a0.0'-□口

□?口C(pi/CM}??醐?口C(pi/CM}??醐L⑼|口1E-4EE-3。010.1圖2-10WS小世界網(wǎng)絡(luò)模型的簇系數(shù)和平均路徑長(zhǎng)度隨p的變化關(guān)系（取自文獻(xiàn)［］）由于在WS小世界網(wǎng)絡(luò)模型的隨機(jī)化重連過(guò)程中有可能破壞網(wǎng)絡(luò)的連通性。為了避免出現(xiàn)因重連而造成的孤立子網(wǎng)，美國(guó)學(xué)者Newman與Watts合作于1999年提出了用“隨機(jī)化加邊”取代“隨機(jī)化重連”的小世界網(wǎng)絡(luò)模型，稱“NW小世界模型”。NW小世界網(wǎng)絡(luò)模型的構(gòu)造算法：（1）從規(guī)則網(wǎng)絡(luò)開(kāi)始：考慮一個(gè)含有N個(gè)節(jié)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們圍成一個(gè)環(huán)，其中每一個(gè)節(jié)點(diǎn)都與它左右相鄰的各K/2個(gè)節(jié)點(diǎn)相連，K是偶數(shù)。（2）隨機(jī)化加邊：以概率p在隨機(jī)選取的一對(duì)節(jié)點(diǎn)之間加上一條邊。其中規(guī)定，任意兩個(gè)不同的節(jié)點(diǎn)之間至多只能加一條邊，并且每個(gè)節(jié)點(diǎn)不能有邊與自身相連。當(dāng)p=0時(shí)，模型退化為規(guī)則網(wǎng)絡(luò)，當(dāng)p=1時(shí)，模型退化為隨機(jī)網(wǎng)絡(luò)。通過(guò)調(diào)節(jié)p的值就可以控制模型從完全規(guī)則網(wǎng)絡(luò)到完全隨機(jī)網(wǎng)絡(luò)的過(guò)渡，如圖2-11所示。在p較小時(shí)，NW模型具有與WS模型類(lèi)似的特性。

規(guī)則網(wǎng)絡(luò)小世界網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò)隨機(jī)化加邊規(guī)則網(wǎng)絡(luò)小世界網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò)隨機(jī)化加邊圖2-11NW小世界網(wǎng)絡(luò)模型（取自文獻(xiàn)［］）小世界網(wǎng)絡(luò)模型具有如下基本特性：（1）簇系數(shù)WS小世界網(wǎng)絡(luò)的聚類(lèi)系數(shù)為:3(K—2)3(K—2)4(K—1)(1一p)3(2-16)NW小世界網(wǎng)絡(luò)的聚類(lèi)系數(shù)為:C(p)C(p)=3(K一2)4(K-1)+4Kp(p+2)(2-17)(2-18)(2-19)(2-18)(2-19)（2）平均路徑長(zhǎng)度至今為止，還沒(méi)有人得到關(guān)于WS小世界網(wǎng)絡(luò)模型的平均路徑長(zhǎng)度的精確解析表達(dá)式，Newman，Moore和Watts分別用重整化群和序列展開(kāi)方法得到如下近似公式：2NL(p)=--f(NKp/2)K式中f（u）為一普適標(biāo)度函數(shù)，且滿足:Iconstu<<1f(u)=\I(Inu)/uu>>1目前為止，還沒(méi)有f（u）的精確表達(dá)式，Newman等人基于平均場(chǎng)方法給出了如下的近似表達(dá)式：

——,arctanh——,arctanh2X22+2x(2-20)(3)度分布對(duì)于WS小世界網(wǎng)絡(luò)，當(dāng)k三K12時(shí)有:"K/2)"'一"e"K/2)"'一"e-節(jié)(k-K/2-n)!(2-21)P(k)="CK/2(1—p)npK-nnn=0當(dāng)k<K/2時(shí)，P(k)=0。對(duì)于NW小世界網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)的度至少為K,因此當(dāng)k三K時(shí)，一個(gè)隨機(jī)選取的節(jié)點(diǎn)的度為k的概率為：P(kP(k)=CN-K[Nk-K(2-22)當(dāng)k<K時(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ò)被稱為均勻網(wǎng)絡(luò)(homogeneousnetwork)或指數(shù)網(wǎng)絡(luò)(exponentialnetwork)。2.3.4無(wú)標(biāo)度網(wǎng)絡(luò)(scale-freenetwork)近年來(lái)，大量的實(shí)證研究表明，許多大規(guī)模真實(shí)網(wǎng)絡(luò)(如WWW、Internet以及新陳代謝網(wǎng)絡(luò)等)的度分布函數(shù)都是呈冪律分布的形式：P(k)8k-oY在這樣的網(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)度，故稱為“無(wú)標(biāo)度網(wǎng)絡(luò)”。為了解釋實(shí)際網(wǎng)絡(luò)中冪律分布產(chǎn)生的機(jī)理，BarabWsi和Albert在1999年提出了一個(gè)無(wú)標(biāo)度網(wǎng)絡(luò)模型，稱為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ò)中己有m0個(gè)節(jié)點(diǎn)，在以后的每一個(gè)時(shí)間步長(zhǎng)中，增加一個(gè)連接度為m的節(jié)點(diǎn)（mWm0）,新增節(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相連的概率■i與節(jié)點(diǎn)i的度ki成正比：n=Xk^（2-23）i乙kjj經(jīng)過(guò)t步后，這種算法能夠產(chǎn)生一個(gè)含有N=t+m0個(gè)節(jié)點(diǎn)、mt條邊的網(wǎng)絡(luò)。如圖2-12所示的是m=m0=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)相連。*.4??****n?,??=??Q???g????■.?■■■圖2-12BA無(wú)標(biāo)度網(wǎng)絡(luò)的演化過(guò)程（取自文獻(xiàn)［］）/