復(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ú)向網(wǎng)絡(luò)(undirectednetworks),否則為有向網(wǎng)絡(luò)(directednetworks)0如果給每條邊都賦予相應(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ò)類型示例(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ò)(regularn

2、etworks),如圖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)0(a)(b)圖 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 平均

3、路徑長(zhǎng)度(averagepathlength定義網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)i和j之間的距離lij為從其中一個(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=maxlj(2-1)i,j定義網(wǎng)絡(luò)的平均路徑長(zhǎng)度L為網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間距離的平均值。即其中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ò)的傳輸效率。New 簇系數(shù)(clusteringefficient)假設(shè)網(wǎng)絡(luò)中白一個(gè)節(jié)點(diǎn)i有k條邊將它與其

4、它節(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。即G=4ki(ki-1)L=N(N-1)NN-liji1jT1(2-2)(2-3)整個(gè)網(wǎng)絡(luò)的聚類系數(shù)定義為網(wǎng)絡(luò)中所有節(jié)點(diǎn)i的聚類系數(shù)Ci的平均值，記N1CkGNi1顯然，0C&1之間。當(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ò)。New 度分布(degreedistribution)網(wǎng)

5、絡(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))平均度，記為。即,1VN.k)=T乙ki(2-5)Ni=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的概率。即1NP(k)=(k-ki)(2-6)NiT通常，一個(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表示。即為C

6、o即(2-4)Bi=-gminm,nri,m#n(2-7)m,ngmn式中g(shù)mn為節(jié)點(diǎn)m與節(jié)點(diǎn)n之間的最短路徑數(shù)，gmin為節(jié)點(diǎn)m與節(jié)點(diǎn)n之問(wèn)經(jīng)過(guò)節(jié)點(diǎn)i的最短路徑數(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ò)的行為。下面介紹幾類基本的網(wǎng)絡(luò)模型。2.3.1 規(guī)則網(wǎng)絡(luò)(r

7、egularnetwork)常見(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ò)圖2-3(a)所示為一個(gè)含有N個(gè)節(jié)點(diǎn)的全局耦合網(wǎng)絡(luò)。條邊，其平均路徑長(zhǎng)度L=1(最小)，簇系數(shù)C=1(最大)。度分布P(k)為以N-1為中心的6函數(shù)。模型的優(yōu)點(diǎn)：能反映實(shí)際網(wǎng)絡(luò)的小世界特性和大聚類特性。(a)全局耦合網(wǎng)絡(luò)(b)最近鄰耦合網(wǎng)絡(luò)(c)星型網(wǎng)絡(luò)網(wǎng)絡(luò)中共有N(N-1)/2(b)模型的缺點(diǎn)：不能反映實(shí)際網(wǎng)

8、絡(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ù))。NL-二(N)2K3(K-2)3C=-一4(K-1)4度分布P(k)為以K為中心的6函數(shù)。模型的優(yōu)點(diǎn)：能反映實(shí)際網(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ò)的平均路徑長(zhǎng)度：2(

9、N-1)L=22(N，)N(N-1)網(wǎng)絡(luò)的簇系數(shù)為：八N-1C1(N：)N網(wǎng)絡(luò)的度分布為：對(duì)于固定的K值,網(wǎng)絡(luò)的平均路徑長(zhǎng)度為:(2-8)對(duì)于較大的K值,最近鄰耦合網(wǎng)絡(luò)的簇系數(shù)為:(2-9)(2-10)(2-11)-4(K=1)P(K)=1(K=N一1)10其它規(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ò)的大聚類特性。ER 隨機(jī)網(wǎng)絡(luò)(randomnetwork)該模型由匈牙利數(shù)學(xué)家Ed?s和Renyi在上世紀(jì)50年代最先提出

10、，所以被人們稱為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所示。(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)或相變(2-12)圖 2-4ER 隨機(jī)網(wǎng)絡(luò)的演化示意圖如果當(dāng)N一刈寸產(chǎn)生一個(gè)具有性質(zhì)Q的ER隨

11、機(jī)圖的概率為1,那么幾乎每一個(gè)ER隨機(jī)圖都具有性質(zhì)Qo以連通性為例，若當(dāng)連接概率p達(dá)到某個(gè)臨界值Pc8(lnN)/N時(shí)，整個(gè)網(wǎng)絡(luò)連通起來(lái)，那么以概率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所示。kkN-1kP(k)=CNp(1-p)式中=p(N-1)即N表示ER隨機(jī)網(wǎng)絡(luò)的平均度(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ò)的平均度為,對(duì)于任意一個(gè)節(jié)點(diǎn)， 其

12、一階鄰居的數(shù)目為,二階鄰居的數(shù)目為2,以此類推，當(dāng)經(jīng)過(guò)L步后遍歷了網(wǎng)絡(luò)的所有節(jié)點(diǎn)，因此對(duì)于規(guī)模為N的隨機(jī)網(wǎng)絡(luò)，有L=N。由此可以得到網(wǎng)絡(luò)的平均路徑長(zhǎng)度為：_lnN_lnNLln(pN)ln( (2-14) )k!(2-13)圖 2-5ER 隨機(jī)網(wǎng)絡(luò)的度分布(取自文獻(xiàn))由于lnN的值隨N增長(zhǎng)較慢，所以規(guī)模很大的ER隨機(jī)網(wǎng)絡(luò)具有很小的平均路徑長(zhǎng)度，如圖2-6所示圖 2-6ER 隨機(jī)網(wǎng)絡(luò)的平均路徑長(zhǎng)度與網(wǎng)絡(luò)規(guī)模的關(guān)系(取自文獻(xiàn))(4)簇系數(shù)在ER隨機(jī)網(wǎng)絡(luò)中，由于任何兩個(gè)節(jié)點(diǎn)之間的連接概率p都相等，所以ER隨機(jī)網(wǎng)絡(luò)的聚類系數(shù)為：(2-15)可見(jiàn)，當(dāng)網(wǎng)絡(luò)規(guī)模N固定時(shí)，簇系數(shù)隨著網(wǎng)絡(luò)節(jié)點(diǎn)平均度k的增加而增

13、加，如圖2-7所示。當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)平均度4固定時(shí)，簇系數(shù)隨著網(wǎng)絡(luò)規(guī)模N的增加而下降，如圖2-8和所示。顯然，當(dāng)N較大時(shí)，ER隨機(jī)網(wǎng)絡(luò)的簇系數(shù)很小。口.口 r1r一,fIa.Q0.20 同 O,e0.8toconnectedprobability模型的優(yōu)點(diǎn)：能反映實(shí)際網(wǎng)絡(luò)的小世界特性。模型的缺點(diǎn)：不能反映實(shí)際網(wǎng)絡(luò)的大聚類特性。圖 2-7(N=104)ER 隨機(jī)網(wǎng)絡(luò)的簇系數(shù)與連接概率的關(guān)系(取自文獻(xiàn))圖 2-8(p=0.0015)ER 隨機(jī)網(wǎng)絡(luò)的簇系數(shù)與網(wǎng)絡(luò)規(guī)模的關(guān)系(取自文獻(xiàn))1NUJ1NUJ一口LLLLLL山。小世界網(wǎng)絡(luò)(small-worldnetwork)作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)網(wǎng)絡(luò)的過(guò)渡

14、，美國(guó)學(xué)者Watts和Strogatz于1998年設(shè)計(jì)了一個(gè)具有小的平均路徑長(zhǎng)度和大的聚類系數(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ò)具有稀疏性， 要求NK,這樣構(gòu)造

15、出來(lái)的網(wǎng)絡(luò)模型具有較高聚類系數(shù)。而隨機(jī)化重連過(guò)程大大減小了網(wǎng)絡(luò)的平均路徑長(zhǎng)度，使網(wǎng)絡(luò)模型具有小世界特性。當(dāng)p取值較小時(shí)，重連過(guò)程對(duì)網(wǎng)絡(luò)的聚類系數(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所示.圖 2-9WS 小世界網(wǎng)絡(luò)模型(取自文獻(xiàn))WS小世界網(wǎng)絡(luò)模型的具聚類系數(shù)和平均路徑長(zhǎng)度可以看作是重連概率p的函數(shù)，分別記為C(p)和L(p),它們的變化規(guī)律如圖2-10所示。在某個(gè)p值范圍內(nèi)，WS網(wǎng)絡(luò)模型可以得到既有較短的平均路徑長(zhǎng)度(小世界特性)，又有較高聚類系數(shù)(高聚集特性)。 圖2-10中p值在

16、0.0l附近的網(wǎng)絡(luò)即兼具這兩方一面的特征。隨機(jī)優(yōu)重連小世界網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò)子*=1卜口口口 g 白二”口口口C(P)/C(O)口 L(p)/L口圖 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/

17、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模型類似的特性。1.00月0,60,40.20.0P圖 2-11NW 小世界網(wǎng)絡(luò)模型(取自文獻(xiàn))小世界網(wǎng)絡(luò)模型具有如下基本特性:(1)簇系數(shù)WS小世界網(wǎng)絡(luò)的聚類系數(shù)為:NW小世界網(wǎng)絡(luò)的聚類系數(shù)為:C(p)=3(K-2)4(K-1)p)3(2-16)規(guī)則網(wǎng)絡(luò)

18、小世界網(wǎng)絡(luò)隨機(jī)網(wǎng)絡(luò)P-0dp-1髓機(jī)化加邊髓機(jī)化加邊C(P)=3(K-2)4(K-1)4Kp(p2)(2-17)(2)平均路徑長(zhǎng)度至今為止， 還沒(méi)有人得到關(guān)于WS小世界網(wǎng)絡(luò)模型的平均路徑長(zhǎng)度的精確解析表達(dá)式，Newman,Moore和Watts分別用重整化群和序列展開(kāi)方法得到如下近似公式：2N,L(p)f(NKp/2)K(2-18)式中f(u)為一普適標(biāo)度函數(shù)，且滿足:f(u)=K/2時(shí)有:min(k-K-,K-)kK-nc/i、vcK/2、n4-n(pK/2)一2_與P(k)=CCK/2(1-p)np二e丁n力n(k-K/2-n)!當(dāng)kK時(shí)，一個(gè)隨機(jī)選取的節(jié)點(diǎn)的度為k的概率為：當(dāng)kK時(shí)，P(

19、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ái)表示，該分布在度的平均值處有一峰值，然后按指數(shù)快速衰減。這類網(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ò)(如WWWInternet以及新陳代謝網(wǎng)絡(luò)等)的度分布函數(shù)都是呈幕律分布的形式：P(k)8k二。在這樣的網(wǎng)絡(luò)中，大部分節(jié)點(diǎn)的度都很小，但也有一小部

20、分節(jié)點(diǎn)具有很大的度，沒(méi)有一個(gè)特征標(biāo)度。由于這類網(wǎng)絡(luò)的節(jié)點(diǎn)的連接度并沒(méi)有明顯的特征標(biāo)度，故稱為“無(wú)標(biāo)度網(wǎng)絡(luò)”。為了解釋實(shí)際網(wǎng)絡(luò)中幕律分布產(chǎn)生的機(jī)理，Barabsi和Albert在1999(2-20)(2-21)(2-22)年提出了一個(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)(m&mo),新增節(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相連的概率H與節(jié)點(diǎn)i的度ki成正比：k；口i二仁(2-23)ikj經(jīng)過(guò)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ò)的演化過(guò)程。初始網(wǎng)絡(luò)有兩個(gè)節(jié)點(diǎn)，每次新增加的一個(gè)節(jié)點(diǎn)按優(yōu)先連接機(jī)制與網(wǎng)絡(luò)中已經(jīng)存在的兩個(gè)節(jié)點(diǎn)相連。=,=t.*JI圖 2-12BA 無(wú)標(biāo)度網(wǎng)絡(luò)的演化過(guò)程