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

1、第二章復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)知識(shí)2.1 網(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ǎng)絡(luò)(undirected networks),否則為有向網(wǎng)絡(luò)(directed networks)。如果給每條邊都賦予相應(yīng)的權(quán) 值，那么該網(wǎng)絡(luò)就為加權(quán)網(wǎng)絡(luò) (weighted networks),否則為無權(quán)網(wǎng)絡(luò)(unweighted networks),如圖 2-1 所示。圖2-1網(wǎng)絡(luò)類型示例(a)無權(quán)無向網(wǎng)絡(luò) (b)加權(quán)網(wǎng)絡(luò) (c)無權(quán)有向網(wǎng)絡(luò)如果節(jié)點(diǎn)按照確定的規(guī)則連邊，所得到的網(wǎng)絡(luò)就稱為“規(guī)則

2、網(wǎng)絡(luò)" (regularnetworks),如圖2-2所示。如果節(jié)點(diǎn)按照完全隨機(jī)的方式連邊，所得到的網(wǎng)絡(luò)就稱為“隨機(jī)網(wǎng)絡(luò)” (random networks) 0如果節(jié)點(diǎn)按照某種(自)組織原則的方式連邊，將演化成各種不同的網(wǎng)絡(luò)，稱為“復(fù)雜網(wǎng)絡(luò)"(complex networks)0圖2-2(b)二維無限規(guī)則網(wǎng)絡(luò)(a) 一維有限規(guī)則網(wǎng)絡(luò)2.2 復(fù)雜網(wǎng)絡(luò)的基本特征量描述復(fù)雜網(wǎng)絡(luò)的基本特征量主要有：平均路徑長度(average path length)、簇系數(shù)(clustering efficient)、度分布(degree distribution)、介數(shù)(betweennes

3、s 等，下面介紹它們的定義。2.2.1 平均路徑長度 (average path length定義網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)i和j之間的距離lij為從其中一個(gè)節(jié)點(diǎn)出發(fā)到達(dá) 另一個(gè)節(jié)點(diǎn)所要經(jīng)過的連邊的最少數(shù)目。定義網(wǎng)絡(luò)的直徑( diameter)為網(wǎng)絡(luò) 中任意兩個(gè)節(jié)點(diǎn)之間距離的最大值。即D max lij(2-1)i, j定義網(wǎng)絡(luò)的平均路徑長度L為網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間距離的平均值。即N(N 1) i 1 j i 1l,ij(2-2)其中N為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，不考慮節(jié)點(diǎn)自身的距離。網(wǎng)絡(luò)的平均路徑長度L又稱為特征路徑長度(characteristic path length)。網(wǎng)絡(luò)的平均路徑長度L和直徑D主要用來

4、衡量網(wǎng)絡(luò)的傳輸效率。2.2.2 簇系數(shù)(clustering efficient)假設(shè)網(wǎng)絡(luò)中白一個(gè)節(jié)點(diǎn)i有ki條邊將它與其它節(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ù)，記為Ci。即(2-3)2Nki(ki 1)整個(gè)網(wǎng)絡(luò)的聚類系數(shù)定義為網(wǎng)絡(luò)中所有節(jié)點(diǎn) i的聚類系數(shù)Ci的平均值，記(2-4)C -CiN i i顯然，0 <C &1之間。當(dāng)C=0時(shí)，說明網(wǎng)絡(luò)中所有節(jié)點(diǎn)均為孤立節(jié)點(diǎn)，即 沒有任何連邊。當(dāng)C=1時(shí)，說

5、明網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)都直接相連，即網(wǎng)絡(luò)是全 局耦合網(wǎng)絡(luò)。2.2.3 度分布(degree distribution)網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)i的度ki定義為與該節(jié)點(diǎn)相連接的其它節(jié)點(diǎn)的數(shù)目，也就是 該節(jié)點(diǎn)的鄰居數(shù)。通常情況下，網(wǎng)絡(luò)中不同節(jié)點(diǎn)的度并不相同，所有節(jié)點(diǎn)i的度ki的的平均值稱為網(wǎng)絡(luò)的（節(jié)點(diǎn)）平均度，記為<k>。即(2-5)網(wǎng)絡(luò)中節(jié)點(diǎn)的分布情況一般用度分布函數(shù)在網(wǎng)絡(luò)中任意選取一節(jié)點(diǎn)，該節(jié)點(diǎn)的度恰好為P（k）來描述。度分布函數(shù) k的概率。即P（k）表示P(k) - N (kN i 1ki)(2-6)通常，一個(gè)節(jié)點(diǎn)的度越大，意味著這個(gè)節(jié)點(diǎn)屬于網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)， 在某種 意義上也越“重要”。2

6、.2.4 介數(shù)（betweenness節(jié)點(diǎn)i的介數(shù)定義為網(wǎng)絡(luò)中所有的最短路徑中，經(jīng)過節(jié)點(diǎn) i的數(shù)量。用Bi 表示。即gminBi m, n i, m n（2-7）m,n gmn式中g(shù)mn為節(jié)點(diǎn)m與節(jié)點(diǎn)n之間的最短路徑數(shù)，gmin為節(jié)點(diǎn)m與節(jié)點(diǎn)n之問經(jīng)過節(jié)點(diǎn)i的最短路徑數(shù)。節(jié)點(diǎn)的介數(shù)反映了該節(jié)點(diǎn)在網(wǎng)絡(luò)中的影響力。描述網(wǎng)絡(luò)結(jié)構(gòu)的特征量還有很多， 這里就不一一介紹，在使用到它們的地 方再給出詳細(xì)的說明。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)出小世界特性、無標(biāo)度特性和高聚集特性。為了解釋這些現(xiàn)象， 人們構(gòu)造了各種各樣的網(wǎng)絡(luò)模型，以便從理

7、論上揭示網(wǎng)絡(luò)行為與網(wǎng)絡(luò)結(jié)構(gòu)之間 的關(guān)系，進(jìn)而考慮改善網(wǎng)絡(luò)的行為。下面介紹幾類基本的網(wǎng)絡(luò)模型。2.3.1 規(guī)則網(wǎng)絡(luò)(regular network)常見的規(guī)則網(wǎng)絡(luò)有三種：全局耦合網(wǎng)絡(luò)(globally coupled network) 最近 鄰耦合網(wǎng)絡(luò)(nearest-neighbor coupled network 和星型網(wǎng)絡(luò)模型(star coupled network),如圖 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 條邊，其平均路徑長度L=1 (最小)，簇系數(shù)

8、C=1 (最大)。度分布P(k)為以N 1 為中心的6函數(shù)。模型的優(yōu)點(diǎn)：能反映實(shí)際網(wǎng)絡(luò)的小世界特性和大聚類特性。模型的缺點(diǎn)：不能反映實(shí)際網(wǎng)絡(luò)的稀疏特性。因?yàn)橐粋€(gè)具有N個(gè)節(jié)點(diǎn)的全局耦合網(wǎng)絡(luò)的邊的數(shù)目為 O(N2),而實(shí)際網(wǎng)絡(luò)的邊的數(shù)目一般是 O(N)圖2-3 (b)所示為一個(gè)含有N個(gè)節(jié)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)。網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)只和它周圍的鄰居節(jié)點(diǎn)相連，其中每個(gè)節(jié)點(diǎn)都與它左右各K/2個(gè)鄰居節(jié)點(diǎn)相連(K為偶數(shù))。對(duì)于固定的K值，網(wǎng)絡(luò)的平均路徑長度為:N2K(N )(2-8)對(duì)于較大的K值，最近鄰耦合網(wǎng)絡(luò)的簇系數(shù)為:3(K2)34(K 1)4(2-9)度分布P(k)為以K為中心的6函數(shù)。模型的優(yōu)點(diǎn)：能反映實(shí)

9、際網(wǎng)絡(luò)的大聚類特性和稀疏特性。模型的缺點(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ò)的平均路徑長度:2(N 1)N(N 1)(N )(2-10)網(wǎng)絡(luò)的簇系數(shù)為:(N )(2-11)網(wǎng)絡(luò)的度分布為:1 N (K 1)(2-12)P(K) N (K N 1)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ù) 為00模型的優(yōu)點(diǎn)：能反映實(shí)際網(wǎng)絡(luò)的小世界特性和稀疏特性。模型的缺點(diǎn)：不能反映

10、實(shí)際網(wǎng)絡(luò)的大聚類特性。2.3.2 ER 隨機(jī)網(wǎng)絡(luò)(random network)該模型由匈牙利數(shù)學(xué)家Ed?s和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-4 ER隨機(jī)網(wǎng)絡(luò)的演化示意圖(a) p=0時(shí)，給定10個(gè)孤立節(jié)點(diǎn)；(b

11、)(c) p=0.1 , 0.15時(shí)，生成的隨機(jī)圖ER隨機(jī)網(wǎng)絡(luò)模型具有如下基本特性：(1)涌現(xiàn)或相變?nèi)绻?dāng)N一刈寸產(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ò)連通起來，那么以概率p生成的每一個(gè)網(wǎng)絡(luò)幾 乎都是連通的，否則，當(dāng)p小于該臨界值時(shí)，幾乎每一個(gè)網(wǎng)絡(luò)都是非連通的。(2)度分布對(duì)于一個(gè)給定連接概率為p的隨機(jī)網(wǎng)絡(luò)，若網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)N充分大，則網(wǎng) 絡(luò)的度分布接近泊松(Poission)分布，如圖2-5所示。kk k N 1 k k kP(k) Cn ip (1 p)e(2-13)k

12、!式中<k>=p(N 1)即N表示ER隨機(jī)網(wǎng)絡(luò)的平均度圖2-5 ER隨機(jī)網(wǎng)絡(luò)的度分布(取自文獻(xiàn) )(3)平均路徑長度假定網(wǎng)絡(luò)的平土§路徑長度為L,從網(wǎng)絡(luò)的一端走到網(wǎng)絡(luò)的另一端，總步數(shù) 大概為L。由于ER隨機(jī)網(wǎng)絡(luò)的平均度為< k>,對(duì)于任意一個(gè)節(jié)點(diǎn)，其一階鄰 居的數(shù)目為< k>,二階鄰居的數(shù)目為< k>2,以此類推，當(dāng)經(jīng)過L步后遍歷 了網(wǎng)絡(luò)的所有節(jié)點(diǎn)，因此對(duì)于規(guī)模為N的隨機(jī)網(wǎng)絡(luò)，有<k> L=N。由此可以得 到網(wǎng)絡(luò)的平均路徑長度為：(2-14)ln N ln Nln(pN) ln k由于lnN的值隨N增長較慢，所以規(guī)模很大的E

13、R隨機(jī)網(wǎng)絡(luò)具有很小的平 均路徑長度，如圖2-6所示。圖2-6 ER隨機(jī)網(wǎng)絡(luò)的平均路徑長度與網(wǎng)絡(luò)規(guī)模的關(guān)系(取自文獻(xiàn) )S 工 1SNU H.Lqx由 9Vaa/w(4)簇系數(shù)在ER隨機(jī)網(wǎng)絡(luò)中，由于任何兩個(gè)節(jié)點(diǎn)之間的連接概率 p都相等，所以ER隨機(jī)網(wǎng)絡(luò)的聚類系數(shù)為:(2-15)可見，當(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ù)很 小。t.o-卜Ml cm nelwgrK joa-一金口號(hào) 68 6LI-ssrlFQ.Q -1j -1'

14、i t r0.Q O.Z 0,4 Q5 0,e1.，Gonnectod probabflty)圖2-7(N=104) ER隨機(jī)網(wǎng)絡(luò)的簇系數(shù)與連接概率的關(guān)系(取自文獻(xiàn)0.1 二陽汕。e netwodclooioodSIZE OF THE NETWORKS(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ò)的大聚類特性。2.3.3 小世界網(wǎng)絡(luò)(small-world network)作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)網(wǎng)絡(luò)的過渡，美國學(xué)者Watts和Strogatz于1998年設(shè)計(jì)了一個(gè)具有小的平均路徑長

15、度和大的聚類系數(shù)的小世界網(wǎng)絡(luò)模 型(small-world network),簡(jiǎn)稱 WS小世界網(wǎng)絡(luò)模型。WS小世界網(wǎng)絡(luò)模型的構(gòu)造算法：(1)從規(guī)則網(wǎng)絡(luò)開始：考慮一個(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)造出來的網(wǎng)絡(luò)模型具有較 高聚類系數(shù)。而隨機(jī)化重連過程

16、大大減小了網(wǎng)絡(luò)的平均路徑長度，使網(wǎng)絡(luò)模型具有小世界特性。當(dāng)p取值較小時(shí)，重連過程對(duì)網(wǎng)絡(luò)的聚類系數(shù)影響不大。當(dāng) p時(shí)，模型退化為規(guī)則網(wǎng)絡(luò)，當(dāng) p時(shí)，模型退化為隨機(jī)網(wǎng)絡(luò)。通過調(diào)節(jié)p的值就可以控制模型從完全規(guī)則網(wǎng)絡(luò)到完全隨機(jī)網(wǎng)絡(luò)的過渡，如圖2-9所示.配則網(wǎng)絡(luò)2=口個(gè)世界網(wǎng)絡(luò)隨機(jī)化聿連圖2-9 WS小世界網(wǎng)絡(luò)模型(取自文獻(xiàn) )WS小世界網(wǎng)絡(luò)模型的具聚類系數(shù)和平均路徑長度可以看作是重連概率p的函數(shù)，分別記為C(p)和L(p),它們的變化規(guī)律如圖2-10所示。在某個(gè)p值 范圍內(nèi)，WS網(wǎng)絡(luò)模型可以得到既有較短的平均路徑長度(小世界特性)，又有較高聚類系數(shù)(高聚集特性)。圖2-10中p值在0.0l附近的網(wǎng)絡(luò)

17、即兼具這兩方 一面的特征。- rrms 口 口一力丁”,u O亡口 C(p) / C(0) L9” L(51 00,B0.B0 40.20,0IE避舊 30.01 0J1P圖2-10 WS小世界網(wǎng)絡(luò)模型的簇系數(shù)和平均路徑長度隨p的變化關(guān)系(取自文獻(xiàn))由于在 WS小世界網(wǎng)絡(luò)模型的隨機(jī)化重連過程中有可能破壞網(wǎng)絡(luò)的連通性。為了避免出現(xiàn)因重連而造成的孤立子網(wǎng)，美國學(xué)者Newman與Watts合作于1999年提出了用“隨機(jī)化加邊”取代“隨機(jī)化重連”的小世界網(wǎng)絡(luò)模型， 稱“NW小世界模型”。NW小世界網(wǎng)絡(luò)模型的構(gòu)造算法：(1)從規(guī)則網(wǎng)絡(luò)開始：考慮一個(gè)含有 N個(gè)節(jié)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們 圍成一個(gè)環(huán)，其中每

18、一個(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ò)。通過 調(diào)節(jié)p的值就可以控制模型從完全規(guī)則網(wǎng)絡(luò)到完全隨機(jī)網(wǎng)絡(luò)的過渡，如圖2-11所示。在p較小時(shí)，NW模型具有與 WS模型類似的特性。規(guī)則網(wǎng)絡(luò)小世界網(wǎng)給隨機(jī)網(wǎng)絡(luò)殖機(jī)化加邊圖2-11 NW小世界網(wǎng)絡(luò)模型(取自文獻(xiàn) )小世界網(wǎng)絡(luò)模型具有如下基本特性:(1)簇系數(shù)WS小世界網(wǎng)絡(luò)的聚類系數(shù)為:3(K 2)3C(p) 4K1)(1 p)(216

19、)NW小世界網(wǎng)絡(luò)的聚類系數(shù)為：C(p)3(K 2)4(K 1) 4Kp(p 2)(2-17)(2)平均路徑長度至今為止，還沒有人得到關(guān)于WS小世界網(wǎng)絡(luò)模型的平均路徑長度的精確 解析表達(dá)式，Newman, Moore和Watts分別用重整化群和序列展開方法得到 如下近似公式：L(p)2N ,f(NKp/2)(2-18)式中f(u)為一普適標(biāo)度函數(shù)，且滿足:f(u)const u 1(ln u)/u u 1(2-19)目前為止，還沒有f(u)的精確表達(dá)式,Newman等人基于平均場(chǎng)方法給出了如下的近似表達(dá)式:(2-20)f (x) 2、x2arctanh 2x(3)度分布對(duì)于WS小世界網(wǎng)絡(luò)，當(dāng)k&

20、gt; K/2時(shí)有:min( k ',.)P(k)CK/2(1n 0Kp)npTk 4 n kn (pK/2)三 。 與e(k K/2 n)!(2-21)當(dāng) k<K/2 時(shí)，P(k)=0o對(duì)于NW小世界網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)的度至少為 機(jī)選取的節(jié)點(diǎn)的度為k的概率為：K,因此當(dāng)k> K時(shí),一個(gè)隨P(k) CNKkKpN，/ N k KKpN(2-22)當(dāng) k<K 時(shí)，P(k)=0o類似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

21、t; k>處有一峰值，然后按指數(shù)快速衰減。這類網(wǎng)絡(luò)被稱為均勻網(wǎng)絡(luò)(homogeneous network)或指數(shù)網(wǎng)絡(luò)(exponential network)。2.3.4 無標(biāo)度網(wǎng)絡(luò)(scale-free network)近年來，大量的實(shí)證研究表明，許多大規(guī)模真實(shí)網(wǎng)絡(luò)(如 WWW> Internet 以及新陳代謝網(wǎng)絡(luò)等)的度分布函數(shù)都是呈幕律分布的形式：P(k) 8 k 。在這樣的網(wǎng)絡(luò)中，大部分節(jié)點(diǎn)的度都很小，但也有一小部分節(jié)點(diǎn)具有很大的度， 沒有 一個(gè)特征標(biāo)度。由于這類網(wǎng)絡(luò)的節(jié)點(diǎn)的連接度并沒有明顯的特征標(biāo)度， 故稱為“無 標(biāo)度網(wǎng)絡(luò)”。為了解釋實(shí)際網(wǎng)絡(luò)中幕律分布產(chǎn)生的機(jī)理，Bara

22、bsi和Albert在1999年提出了一個(gè)無標(biāo)度網(wǎng)絡(luò)模型，稱為BA無標(biāo)度模型。該模型的構(gòu)造主要基于現(xiàn) 實(shí)網(wǎng)絡(luò)的兩個(gè)內(nèi)在機(jī)制：增長機(jī)制：大多數(shù)真實(shí)網(wǎng)絡(luò)是一個(gè)開放系統(tǒng)， 隨著時(shí) 間的推移，網(wǎng)絡(luò)規(guī)模將不斷增大，即網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)和連邊數(shù)是不斷增加的。擇優(yōu)連接：新增加的節(jié)更傾向于與那些具有較高連接度的節(jié)點(diǎn)相連。也就是富人 更富的觀點(diǎn) (rich get richer)。BA無標(biāo)度網(wǎng)絡(luò)模型的構(gòu)造算法：(1)增長：在初始時(shí)刻，假定網(wǎng)絡(luò)中己有 m0個(gè)節(jié)點(diǎn)，在以后的每一個(gè)時(shí) 間步長中，增加一個(gè)連接度為 m的節(jié)點(diǎn)(m&m0),新增節(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相連的概率與節(jié)點(diǎn)i的度ki成正比：k(2-23) ikj經(jīng)過t步后，這種算法能夠產(chǎn)生一個(gè)含有 N=t+mo個(gè)節(jié)點(diǎn)、mt條邊的網(wǎng)絡(luò)。如圖2-12所示白是m=mo=2時(shí)，BA網(wǎng)絡(luò)的演化過程。初始網(wǎng)絡(luò)有兩個(gè)節(jié) 點(diǎn)，每次新增加的一個(gè)節(jié)點(diǎn)按