1、第二章復雜網絡的基礎知識2.1網絡的概念所謂“網絡”(networks),實際上就是節點(node)和連邊(edge)的集合。如果節點對(i,j)與(j,i)對應為同一條邊， 那么該網絡為無向網絡(undirectednetworks),否則為有向網絡(directednetworks)0如果給每條邊都賦予相應的權值，那么該網絡就為加權網絡(weightednetworks),否則為無權網絡(unweightednetworks),如圖2-1所示。圖 2-1 網絡類型示例(a)無權無向網絡(b)加權網絡(c)無權有向網絡如果節點按照確定的規則連邊，所得到的網絡就稱為“規則網絡(regularn

2、etworks),如圖2-2所示。如果節點按照完全隨機的方式連邊，所得到的網絡就稱為“隨機網絡”(randomnetworks)如果節點按照某種(自)組織原則的方式連邊， 將演化成各種不同的網絡，稱為“復雜網絡(complexnetworks)0(a)(b)圖 2-2 規則網絡示例(a)一維有限規則網絡(b)二維無限規則網絡2.2復雜網絡的基本特征量描述復雜網絡的基本特征量主要有：平均路徑長度(averagepathlength)、簇系數(clusteringefficient)度分布(degreedistribution)、介數(betweenness等，下面介紹它們的定義。2.2.1 平均

3、路徑長度(averagepathlength定義網絡中任何兩個節點i和j之間的距離lij為從其中一個節點出發到達另一個節點所要經過的連邊的最少數目。 定義網絡的直徑(diameter)為網絡中任意兩個節點之間距離的最大值。即D=maxlj(2-1)i,j定義網絡的平均路徑長度L為網絡中所有節點對之間距離的平均值。即其中N為網絡節點數，不考慮節點自身的距離。網絡的平均路徑長度L又稱為特征路徑長度(characteristicpathlength)。網絡的平均路徑長度L和直徑D主要用來衡量網絡的傳輸效率。New 簇系數(clusteringefficient)假設網絡中白一個節點i有k條邊將它與其

4、它節點相連，這ki個節點稱為節點i的鄰居節點，在這ki個鄰居節點之間最多可能有ki(ki-1)/2條邊。節點i的ki個鄰居節點之間實際存在的邊數Ni和最多可能有的邊數ki(ki-1)/2之比就定義為節點i的簇系數，記為Ci。即G=4ki(ki-1)L=N(N-1)NN-liji1jT1(2-2)(2-3)整個網絡的聚類系數定義為網絡中所有節點i的聚類系數Ci的平均值，記N1CkGNi1顯然，0C&1之間。當C=0時，說明網絡中所有節點均為孤立節點，即沒有任何連邊。當C=1時，說明網絡中任意兩個節點都直接相連，即網絡是全局耦合網絡。New 度分布(degreedistribution)網

5、絡中某個節點i的度ki定義為與該節點相連接的其它節點的數目，也就是該節點的鄰居數。通常情況下，網絡中不同節點的度并不相同，所有節點i的度ki的的平均值稱為網絡的(節點)平均度，記為。即,1VN.k)=T乙ki(2-5)Ni=1網絡中節點的分布情況一般用度分布函數P(k)來描述。 度分布函數P(k)表示在網絡中任意選取一節點，該節點的度恰好為k的概率。即1NP(k)=(k-ki)(2-6)NiT通常，一個節點的度越大，意味著這個節點屬于網絡中的關鍵節點，在某種意義上也越“重要”。2.2.4 介數(betweenness節點i的介數定義為網絡中所有的最短路徑中，經過節點i的數量。用Bi表示。即為C

6、o即(2-4)Bi=-gminm,nri,m#n(2-7)m,ngmn式中gmn為節點m與節點n之間的最短路徑數，gmin為節點m與節點n之問經過節點i的最短路徑數。節點的介數反映了該節點在網絡中的影響力。描述網絡結構的特征量還有很多，這里就不一一介紹，在使用到它們的地方再給出詳細的說明。2.3復雜網絡的基本模型人們在對不同領域內的大量實際網絡進行廣泛的實證研究后發現：真實網絡系統往往表現出小世界特性、無標度特性和高聚集特性。為了解釋這些現象，人們構造了各種各樣的網絡模型，以便從理論上揭示網絡行為與網絡結構之間的關系，進而考慮改善網絡的行為。下面介紹幾類基本的網絡模型。2.3.1 規則網絡(r

7、egularnetwork)常見的規則網絡有三種：全局耦合網絡(globallycouplednetwork)最近鄰耦合網絡(nearest-neighborcouplednetwork和星型網絡模型(starcouplednetwork),如圖2-3所示。圖 2-3 三種典型的規則網絡圖2-3(a)所示為一個含有N個節點的全局耦合網絡。條邊，其平均路徑長度L=1(最小)，簇系數C=1(最大)。度分布P(k)為以N-1為中心的6函數。模型的優點：能反映實際網絡的小世界特性和大聚類特性。(a)全局耦合網絡(b)最近鄰耦合網絡(c)星型網絡網絡中共有N(N-1)/2(b)模型的缺點：不能反映實際網

8、絡的稀疏特性。因為一個具有N個節點的全局耦合網絡的邊的數目為O(N2),而實際網絡的邊的數目一般是O(N)圖2-3(b)所示為一個含有N個節點的最近鄰耦合網絡。網絡中的每個節點只和它周圍的鄰居節點相連，其中每個節點都與它左右各K/2個鄰居節點相連( (K為偶數)。NL-二(N)2K3(K-2)3C=-一4(K-1)4度分布P(k)為以K為中心的6函數。模型的優點：能反映實際網絡的大聚類特性和稀疏特性。模型的缺點：不能反映實際網絡的小世界特性。圖2-3(c)所示為一個具有N個節點的星型網絡。網絡有一個中心節點,其余N-1個節點都只與這個中心節點相連，且它們彼此之間不連接。網絡的平均路徑長度：2(

9、N-1)L=22(N，)N(N-1)網絡的簇系數為：八N-1C1(N：)N網絡的度分布為：對于固定的K值,網絡的平均路徑長度為:(2-8)對于較大的K值,最近鄰耦合網絡的簇系數為:(2-9)(2-10)(2-11)-4(K=1)P(K)=1(K=N一1)10其它規定：如果一個節點只有一個鄰居，那么該節點的簇系數為1。也有些文獻規定只有一個鄰居的節點的簇系數為0,若依此定義，則星型網絡的簇系數為0。模型的優點：能反映實際網絡的小世界特性和稀疏特性。模型的缺點：不能反映實際網絡的大聚類特性。ER 隨機網絡(randomnetwork)該模型由匈牙利數學家Ed?s和Renyi在上世紀50年代最先提出

10、，所以被人們稱為ER隨機網絡模型。ER隨機網絡的構造有兩種方法。第一種方法：定義有標記的N個節(網絡中的節點總數)，并且給出整個網絡的邊數n,這些邊的選取采用從所有可能的N(N-1)/2種情況中隨機選取。第二種方法：給定有標記的N個節點，以一定的隨機概率p連接所有可能出現的N(N-1)/2種連接，假設最初有N個孤立的節點，每對節點以隨機概率p進行連接。如圖2-4所示。(a)p=0 時，給定 10 個孤立節點；(b)(c)p=0.1,0.15 時，生成的隨機圖ER隨機網絡模型具有如下基本特性：(1)涌現或相變(2-12)圖 2-4ER 隨機網絡的演化示意圖如果當N一刈寸產生一個具有性質Q的ER隨

11、機圖的概率為1,那么幾乎每一個ER隨機圖都具有性質Qo以連通性為例，若當連接概率p達到某個臨界值Pc8(lnN)/N時，整個網絡連通起來，那么以概率p生成的每一個網絡幾乎都是連通的，否則，當p小于該臨界值時，幾乎每一個網絡都是非連通的。(2)度分布對于一個給定連接概率為p的隨機網絡，若網絡的節點數N充分大，則網絡的度分布接近泊松(Poission)分布，如圖2-5所示。kkN-1kP(k)=CNp(1-p)式中=p(N-1)即N表示ER隨機網絡的平均度(3)平均路徑長度假定網絡的平土路徑長度為L,從網絡的一端走到網絡的另一端， 總步數大概為L。由于ER隨機網絡的平均度為,對于任意一個節點， 其

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

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

14、，美國學者Watts和Strogatz于1998年設計了一個具有小的平均路徑長度和大的聚類系數的小世界網絡模型(small-worldnetwork),簡稱WS小世界網絡模型。WS小世界網絡模型的構造算法：(1)從規則網絡開始： 考慮一個含有N個節點的最近鄰耦合網絡， 它們圍成一個環，其中每一個節點都與它左右相鄰的各K/2個節點相連，K是偶數。(2)隨機化重連：以概率p隨機地重新連接網絡中的每一條邊，即將連邊的一個端點保持不變，而另一個端點取為網絡中隨機選擇的一個節點。其中規定，任意兩個不同的節點之間至多只能有一條邊，并且每個節點不能有邊與自身相連。為了保證網絡具有稀疏性， 要求NK,這樣構造

15、出來的網絡模型具有較高聚類系數。而隨機化重連過程大大減小了網絡的平均路徑長度，使網絡模型具有小世界特性。當p取值較小時，重連過程對網絡的聚類系數影響不大。當p=0時，模型退化為規則網絡，當p=l時，模型退化為隨機網絡。通過調節p的值就可以控制模型從完全規則網絡到完全隨機網絡的過渡，如圖2-9所示.圖 2-9WS 小世界網絡模型(取自文獻)WS小世界網絡模型的具聚類系數和平均路徑長度可以看作是重連概率p的函數，分別記為C(p)和L(p),它們的變化規律如圖2-10所示。在某個p值范圍內，WS網絡模型可以得到既有較短的平均路徑長度(小世界特性)，又有較高聚類系數(高聚集特性)。 圖2-10中p值在

16、0.0l附近的網絡即兼具這兩方一面的特征。隨機優重連小世界網絡隨機網絡子*=1卜口口口 g 白二”口口口C(P)/C(O)口 L(p)/L口圖 2-10WS 小世界網絡模型的簇系數和平均路徑長度隨 p 的變化關系(取自文獻)由于在WS小世界網絡模型的隨機化重連過程中有可能破壞網絡的連通性。為了避免出現因重連而造成的孤立子網，美國學者Newman與Watts合作于1999年提出了用“隨機化加邊”取代“隨機化重連”的小世界網絡模型，稱“NW小世界模型”。NW小世界網絡模型的構造算法：(1)從規則網絡開始： 考慮一個含有N個節點的最近鄰耦合網絡， 它們圍成一個環，其中每一個節點都與它左右相鄰的各K/

17、2個節點相連，K是偶數。(2)隨機化加邊：以概率p在隨機選取的一對節點之間加上一條邊。其中規定，任意兩個不同的節點之間至多只能加一條邊，并且每個節點不能有邊與自身相連。當p=0時，模型退化為規則網絡，當p=1時，模型退化為隨機網絡。通過調節p的值就可以控制模型從完全規則網絡到完全隨機網絡的過渡，如圖2-11所示。在p較小時，NW模型具有與WS模型類似的特性。1.00月0,60,40.20.0P圖 2-11NW 小世界網絡模型(取自文獻)小世界網絡模型具有如下基本特性:(1)簇系數WS小世界網絡的聚類系數為:NW小世界網絡的聚類系數為:C(p)=3(K-2)4(K-1)p)3(2-16)規則網絡

18、小世界網絡隨機網絡P-0dp-1髓機化加邊髓機化加邊C(P)=3(K-2)4(K-1)4Kp(p2)(2-17)(2)平均路徑長度至今為止， 還沒有人得到關于WS小世界網絡模型的平均路徑長度的精確解析表達式，Newman,Moore和Watts分別用重整化群和序列展開方法得到如下近似公式：2N,L(p)f(NKp/2)K(2-18)式中f(u)為一普適標度函數，且滿足:f(u)=K/2時有: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)!當kK時，一個隨機選取的節點的度為k的概率為：當kK時，P(

19、k)=0o類似ER隨機網絡模型，WS小世界網絡模型也是所有節點的度都近似相等的均勻網絡。綜上所述，ER隨機網絡、WS小世界網絡和NW小世界網絡的度分布可近似用Poisson分布來表示，該分布在度的平均值處有一峰值，然后按指數快速衰減。這類網絡被稱為均勻網絡(homogeneousnetwork)或指數網絡(exponentialnetwork)。2.3.4 無標度網絡(scale-freenetwork)近年來，大量的實證研究表明，許多大規模真實網絡(如WWWInternet以及新陳代謝網絡等)的度分布函數都是呈幕律分布的形式：P(k)8k二。在這樣的網絡中，大部分節點的度都很小，但也有一小部

20、分節點具有很大的度，沒有一個特征標度。由于這類網絡的節點的連接度并沒有明顯的特征標度，故稱為“無標度網絡”。為了解釋實際網絡中幕律分布產生的機理，Barabsi和Albert在1999(2-20)(2-21)(2-22)年提出了一個無標度網絡模型，稱為BA無標度模型。該模型的構造主要基于現實網絡的兩個內在機制：增長機制：大多數真實網絡是一個開放系統，隨著時間的推移，網絡規模將不斷增大，即網絡中的節點數和連邊數是不斷增加的。擇優連接： 新增加的節更傾向于與那些具有較高連接度的節點相連。 也就是富人更富的觀點(richgetricher)。BA無標度網絡模型的構造算法：(1)增長：在初始時刻，假定網絡中己有m0個節點，在以后的每一個時間步長中，增加一個連接度為m的節點(m&mo),新增節點與網絡中已經存在的m個不同的節點相連，且不存在重復連接。(2)優先連接： 在選擇新節點的連接點時， 一個新節點與一個已經存在的節點i相連的概率H與節點i的度ki成正比：k；口i二仁(2-23)ikj經過t步后，這種算法能夠產生一個含有N=t+mo個節點、mt條邊的網絡。如圖2-12所示白是m=mo=2時，BA網絡的演化過程。初始網絡有兩個節點，每次新增加的一個節點按優先連接機制與網絡中已經存在的兩個節點相連。=,=t.*JI圖 2-12BA 無標度網絡的演化過程