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

1、第二章復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)知識2.1 網(wǎng)絡(luò)的概念所謂“網(wǎng)絡(luò)”(networks),實際上就是節(jié)點(node)和連邊(edge)的集合。 如果節(jié)點對(i, j)與(j, i)對應(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é)點按照確定的規(guī)則連邊，所得到的網(wǎng)絡(luò)就稱為“規(guī)則

2、網(wǎng)絡(luò)" (regularnetworks),如圖2-2所示。如果節(jié)點按照完全隨機的方式連邊，所得到的網(wǎng)絡(luò)就稱為“隨機網(wǎng)絡(luò)” (random networks) 0如果節(jié)點按照某種(自)組織原則的方式連邊，將演化成各種不同的網(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ò)中任何兩個節(jié)點i和j之間的距離lij為從其中一個節(jié)點出發(fā)到達 另一個節(jié)點所要經(jīng)過的連邊的最少數(shù)目。定義網(wǎng)絡(luò)的直徑( diameter)為網(wǎng)絡(luò) 中任意兩個節(jié)點之間距離的最大值。即D max lij(2-1)i, j定義網(wǎng)絡(luò)的平均路徑長度L為網(wǎng)絡(luò)中所有節(jié)點對之間距離的平均值。即N(N 1) i 1 j i 1l,ij(2-2)其中N為網(wǎng)絡(luò)節(jié)點數(shù)，不考慮節(jié)點自身的距離。網(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ò)中白一個節(jié)點i有ki條邊將它與其它節(jié)點相連，這ki個節(jié)點稱為 節(jié)點i的鄰居節(jié)點，在這ki個鄰居節(jié)點之間最多可能有ki(ki 1)/2條邊。節(jié)點i 的ki個鄰居節(jié)點之間實際存在的邊數(shù) Ni和最多可能有的邊數(shù)ki(ki 1)/2之比就 定義為節(jié)點i的簇系數(shù)，記為Ci。即(2-3)2Nki(ki 1)整個網(wǎng)絡(luò)的聚類系數(shù)定義為網(wǎng)絡(luò)中所有節(jié)點 i的聚類系數(shù)Ci的平均值，記(2-4)C -CiN i i顯然，0 <C &1之間。當(dāng)C=0時，說明網(wǎng)絡(luò)中所有節(jié)點均為孤立節(jié)點，即 沒有任何連邊。當(dāng)C=1時，說

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

6、.2.4 介數(shù)（betweenness節(jié)點i的介數(shù)定義為網(wǎng)絡(luò)中所有的最短路徑中，經(jīng)過節(jié)點 i的數(shù)量。用Bi 表示。即gminBi m, n i, m n（2-7）m,n gmn式中g(shù)mn為節(jié)點m與節(jié)點n之間的最短路徑數(shù)，gmin為節(jié)點m與節(jié)點n之問經(jīng)過節(jié)點i的最短路徑數(shù)。節(jié)點的介數(shù)反映了該節(jié)點在網(wǎng)絡(luò)中的影響力。描述網(wǎng)絡(luò)結(jié)構(gòu)的特征量還有很多， 這里就不一一介紹，在使用到它們的地 方再給出詳細的說明。2.3 復(fù)雜網(wǎng)絡(luò)的基本模型人們在對不同領(lǐng)域內(nèi)的大量實際網(wǎng)絡(luò)進行廣泛的實證研究后發(fā)現(xiàn)：真實網(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)系，進而考慮改善網(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)所示為一個含有N個節(jié)點的全局耦合網(wǎng)絡(luò)。網(wǎng)絡(luò)中共有N(N 1)/2 條邊，其平均路徑長度L=1 (最小)，簇系數(shù)

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

9、際網(wǎng)絡(luò)的大聚類特性和稀疏特性。模型的缺點：不能反映實際網(wǎng)絡(luò)的小世界特性。圖2-3 (c)所示為一個具有N個節(jié)點的星型網(wǎng)絡(luò)。網(wǎng)絡(luò)有一個中心節(jié)點, 其余N 1個節(jié)點都只與這個中心節(jié)點相連，且它們彼此之間不連接。網(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ī)定：如果一個節(jié)點只有一個鄰居，那么該節(jié)點的簇系數(shù)為1。也有些文獻規(guī)定只有一個鄰居的節(jié)點的簇系數(shù)為 0,若依此定義，則星型網(wǎng)絡(luò)的簇系數(shù) 為00模型的優(yōu)點：能反映實際網(wǎng)絡(luò)的小世界特性和稀疏特性。模型的缺點：不能反映

10、實際網(wǎng)絡(luò)的大聚類特性。2.3.2 ER 隨機網(wǎng)絡(luò)(random network)該模型由匈牙利數(shù)學(xué)家Ed?s和Renyi在上世紀(jì)50年代最先提出，所以被 人們稱為ER隨機網(wǎng)絡(luò)模型。ER隨機網(wǎng)絡(luò)的構(gòu)造有兩種方法。第一種方法：定義有標(biāo)記的N個節(jié)(網(wǎng)絡(luò)中的節(jié)點總數(shù))，并且給出整個 網(wǎng)絡(luò)的邊數(shù)n,這些邊的選取采用從所有可能的 N(N 1)/2種情況中隨機選取。第二種方法：給定有標(biāo)記的N個節(jié)點，以一定的隨機概率p連接所有可能 出現(xiàn)的N(N 1)/2種連接，假設(shè)最初有N個孤立的節(jié)點，每對節(jié)點以隨機概率 p進行連接。如圖2-4所示。圖2-4 ER隨機網(wǎng)絡(luò)的演化示意圖(a) p=0時，給定10個孤立節(jié)點；(b

11、)(c) p=0.1 , 0.15時，生成的隨機圖ER隨機網(wǎng)絡(luò)模型具有如下基本特性：(1)涌現(xiàn)或相變?nèi)绻?dāng)N一刈寸產(chǎn)生一個具有性質(zhì) Q的ER隨機圖的概率為1,那么幾乎 每一個ER隨機圖都具有性質(zhì)Q。以連通性為例，若當(dāng)連接概率 p達到某個臨 界值pc”(lnN)/N時，整個網(wǎng)絡(luò)連通起來，那么以概率p生成的每一個網(wǎng)絡(luò)幾 乎都是連通的，否則，當(dāng)p小于該臨界值時，幾乎每一個網(wǎng)絡(luò)都是非連通的。(2)度分布對于一個給定連接概率為p的隨機網(wǎng)絡(luò)，若網(wǎng)絡(luò)的節(jié)點數(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隨機網(wǎng)絡(luò)的平均度圖2-5 ER隨機網(wǎng)絡(luò)的度分布(取自文獻 )(3)平均路徑長度假定網(wǎng)絡(luò)的平土§路徑長度為L,從網(wǎng)絡(luò)的一端走到網(wǎng)絡(luò)的另一端，總步數(shù) 大概為L。由于ER隨機網(wǎng)絡(luò)的平均度為< k>,對于任意一個節(jié)點，其一階鄰 居的數(shù)目為< k>,二階鄰居的數(shù)目為< k>2,以此類推，當(dāng)經(jīng)過L步后遍歷 了網(wǎng)絡(luò)的所有節(jié)點，因此對于規(guī)模為N的隨機網(wǎng)絡(luò)，有<k> L=N。由此可以得 到網(wǎng)絡(luò)的平均路徑長度為：(2-14)ln N ln Nln(pN) ln k由于lnN的值隨N增長較慢，所以規(guī)模很大的E

13、R隨機網(wǎng)絡(luò)具有很小的平 均路徑長度，如圖2-6所示。圖2-6 ER隨機網(wǎng)絡(luò)的平均路徑長度與網(wǎng)絡(luò)規(guī)模的關(guān)系(取自文獻 )S 工 1SNU H.Lqx由 9Vaa/w(4)簇系數(shù)在ER隨機網(wǎng)絡(luò)中，由于任何兩個節(jié)點之間的連接概率 p都相等，所以ER隨機網(wǎng)絡(luò)的聚類系數(shù)為:(2-15)可見，當(dāng)網(wǎng)絡(luò)規(guī)模N固定時，簇系數(shù)隨著網(wǎng)絡(luò)節(jié)點平均度 k的增加而增加，如圖2-7所示。當(dāng)網(wǎng)絡(luò)節(jié)點平均度k固定時，簇系數(shù)隨著網(wǎng)絡(luò)規(guī)模 N的 增加而下降，如圖2-8和所示。顯然，當(dāng)N較大時，ER隨機網(wǎng)絡(luò)的簇系數(shù)很 小。t.o-卜Ml cm nelwgrK joa-一金口號 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隨機網(wǎng)絡(luò)的簇系數(shù)與連接概率的關(guān)系(取自文獻0.1 二陽汕。e netwodclooioodSIZE OF THE NETWORKS(N)圖2-8 (p=0.0015) ER隨機網(wǎng)絡(luò)的簇系數(shù)與網(wǎng)絡(luò)規(guī)模的關(guān)系(取自文獻)模型的優(yōu)點：能反映實際網(wǎng)絡(luò)的小世界特性。模型的缺點：不能反映實際網(wǎng)絡(luò)的大聚類特性。2.3.3 小世界網(wǎng)絡(luò)(small-world network)作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機網(wǎng)絡(luò)的過渡，美國學(xué)者Watts和Strogatz于1998年設(shè)計了一個具有小的平均路徑長

15、度和大的聚類系數(shù)的小世界網(wǎng)絡(luò)模 型(small-world network),簡稱 WS小世界網(wǎng)絡(luò)模型。WS小世界網(wǎng)絡(luò)模型的構(gòu)造算法：(1)從規(guī)則網(wǎng)絡(luò)開始：考慮一個含有 N個節(jié)點的最近鄰耦合網(wǎng)絡(luò)，它們 圍成一個環(huán)，其中每一個節(jié)點都與它左右相鄰的各 K/2個節(jié)點相連，K是偶數(shù)。(2)隨機化重連：以概率p隨機地重新連接網(wǎng)絡(luò)中的每一條邊，即將連 邊的一個端點保持不變，而另一個端點取為網(wǎng)絡(luò)中隨機選擇的一個節(jié)點。其中 規(guī)定，任意兩個不同的節(jié)點之間至多只能有一條邊，并且每個節(jié)點不能有邊與自身相連。為了保證網(wǎng)絡(luò)具有稀疏性，要求 N>>K,這樣構(gòu)造出來的網(wǎng)絡(luò)模型具有較 高聚類系數(shù)。而隨機化重連過程

16、大大減小了網(wǎng)絡(luò)的平均路徑長度，使網(wǎng)絡(luò)模型具有小世界特性。當(dāng)p取值較小時，重連過程對網(wǎng)絡(luò)的聚類系數(shù)影響不大。當(dāng) p時，模型退化為規(guī)則網(wǎng)絡(luò)，當(dāng) p時，模型退化為隨機網(wǎng)絡(luò)。通過調(diào)節(jié)p的值就可以控制模型從完全規(guī)則網(wǎng)絡(luò)到完全隨機網(wǎng)絡(luò)的過渡，如圖2-9所示.配則網(wǎng)絡(luò)2=口個世界網(wǎng)絡(luò)隨機化聿連圖2-9 WS小世界網(wǎng)絡(luò)模型(取自文獻 )WS小世界網(wǎng)絡(luò)模型的具聚類系數(shù)和平均路徑長度可以看作是重連概率p的函數(shù)，分別記為C(p)和L(p),它們的變化規(guī)律如圖2-10所示。在某個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)系(取自文獻)由于在 WS小世界網(wǎng)絡(luò)模型的隨機化重連過程中有可能破壞網(wǎng)絡(luò)的連通性。為了避免出現(xiàn)因重連而造成的孤立子網(wǎng)，美國學(xué)者Newman與Watts合作于1999年提出了用“隨機化加邊”取代“隨機化重連”的小世界網(wǎng)絡(luò)模型， 稱“NW小世界模型”。NW小世界網(wǎng)絡(luò)模型的構(gòu)造算法：(1)從規(guī)則網(wǎng)絡(luò)開始：考慮一個含有 N個節(jié)點的最近鄰耦合網(wǎng)絡(luò)，它們 圍成一個環(huán)，其中每

18、一個節(jié)點都與它左右相鄰的各 K/2個節(jié)點相連，K是偶數(shù)。(2)隨機化加邊：以概率p在隨機選取的一對節(jié)點之間加上一條邊。其 中規(guī)定，任意兩個不同的節(jié)點之間至多只能加一條邊，并且每個節(jié)點不能有邊與自身相連。當(dāng)p=0時，模型退化為規(guī)則網(wǎng)絡(luò)，當(dāng)p=1時，模型退化為隨機網(wǎng)絡(luò)。通過 調(diào)節(jié)p的值就可以控制模型從完全規(guī)則網(wǎng)絡(luò)到完全隨機網(wǎng)絡(luò)的過渡，如圖2-11所示。在p較小時，NW模型具有與 WS模型類似的特性。規(guī)則網(wǎng)絡(luò)小世界網(wǎng)給隨機網(wǎng)絡(luò)殖機化加邊圖2-11 NW小世界網(wǎng)絡(luò)模型(取自文獻 )小世界網(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ò)模型的平均路徑長度的精確 解析表達式，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)的精確表達式,Newman等人基于平均場方法給出了如下的近似表達式:(2-20)f (x) 2、x2arctanh 2x(3)度分布對于WS小世界網(wǎng)絡(luò)，當(dāng)k&

20、gt; K/2時有: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 時，P(k)=0o對于NW小世界網(wǎng)絡(luò)，每個節(jié)點的度至少為 機選取的節(jié)點的度為k的概率為：K,因此當(dāng)k> K時,一個隨P(k) CNKkKpN，/ N k KKpN(2-22)當(dāng) k<K 時，P(k)=0o類似ER隨機網(wǎng)絡(luò)模型，WS小世界網(wǎng)絡(luò)模型也是所有節(jié)點的度都近似相 等的均勻網(wǎng)絡(luò)。綜上所述，ER隨機網(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)近年來，大量的實證研究表明，許多大規(guī)模真實網(wǎng)絡(luò)(如 WWW> Internet 以及新陳代謝網(wǎng)絡(luò)等)的度分布函數(shù)都是呈幕律分布的形式：P(k) 8 k 。在這樣的網(wǎng)絡(luò)中，大部分節(jié)點的度都很小，但也有一小部分節(jié)點具有很大的度， 沒有 一個特征標(biāo)度。由于這類網(wǎng)絡(luò)的節(jié)點的連接度并沒有明顯的特征標(biāo)度， 故稱為“無 標(biāo)度網(wǎng)絡(luò)”。為了解釋實際網(wǎng)絡(luò)中幕律分布產(chǎn)生的機理，Bara

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