復雜網絡的基礎知識

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

iji,j(2-1)定義網絡的平均路徑長度L為網絡中所有節(jié)點對之間距離的平均值。即L.2七iniN(N—1)ji=1j=i+1(2-2)其中N為網絡節(jié)點數(shù)，不考慮節(jié)點自身的距離。網絡的平均路徑長度L又稱為特征路徑長度(characteristicpathlength)。網絡的平均路徑長度L和直徑D主要用來衡量網絡的傳輸效率。2.2.2簇系數(shù)(clusteringefficient)假設網絡中的一個節(jié)點i有勺條邊將它與其它節(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ù)，記為C.。即「2N.C=1——ik.(k.-1)ii(2-3)整個網絡的聚類系數(shù)定義為網絡中所有節(jié)點i的聚類系數(shù)Ci的平均值，記為。。即(2-4)廠1T廠

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

如果當N時產生一個具有性質Q的ER隨機圖的概率為1,那么幾乎每一個ER隨機圖都具有性質Q。以連通性為例，若當連接概率p達到某個臨界值pc-（lnN）/N時，整個網絡連通起來，那么以概率p生成的每一個網絡幾乎都是連通的，否則，當p如果當N（2）度分布對于一個給定連接概率為p的隨機網絡，若網絡的節(jié)點數(shù)N充分大，則網絡的度分布接近泊松（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隨機網絡的平均度。圖2-5ER隨機網絡的度分布（取自文獻［］）（3）平均路徑長度假定網絡的平均路徑長度為L，從網絡的一端走到網絡的另一端，總步數(shù)大概為L。由于ER隨機網絡的平均度為＜k"對于任意一個節(jié)點，其一階鄰居的數(shù)目為＜k＞,二階鄰居的數(shù)目為＜k＞2,以此類推，當經過L步后遍歷了網絡的所有節(jié)點，因此對于規(guī)模為N的隨機網絡，有＜k＞l=N。由此可以得到網絡的平均路徑長度為：lnNlnN(2-14)L(2-14)ln(pN)l爪k〉

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

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

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

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

規(guī)則網絡小世界網絡隨機網絡隨機化加邊規(guī)則網絡小世界網絡隨機網絡隨機化加邊圖2-11NW小世界網絡模型（取自文獻［］）小世界網絡模型具有如下基本特性：（1）簇系數(shù)WS小世界網絡的聚類系數(shù)為:3(K—2)3(K—2)4(K—1)(1一p)3(2-16)NW小世界網絡的聚類系數(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）平均路徑長度至今為止，還沒有人得到關于WS小世界網絡模型的平均路徑長度的精確解析表達式，Newman，Moore和Watts分別用重整化群和序列展開方法得到如下近似公式：2NL(p)=--f(NKp/2)K式中f（u）為一普適標度函數(shù)，且滿足:Iconstu<<1f(u)=\I(Inu)/uu>>1目前為止，還沒有f（u）的精確表達式，Newman等人基于平均場方法給出了如下的近似表達式：

——,arctanh——,arctanh2X22+2x(2-20)(3)度分布對于WS小世界網絡，當k三K12時有:"K/2)"'一"e"K/2)"'一"e-節(jié)(k-K/2-n)!(2-21)P(k)="CK/2(1—p)npK-nnn=0當k<K/2時，P(k)=0。對于NW小世界網絡，每個節(jié)點的度至少為K,因此當k三K時，一個隨機選取的節(jié)點的度為k的概率為：P(kP(k)=CN-K[Nk-K(2-22)當k<K時，P(k)=0。類似ER隨機網絡模型，WS小世界網絡模型也是所有節(jié)點的度都近似相等的均勻網絡。綜上所述，ER隨機網絡、WS小世界網絡和NW小世界網絡的度分布可近似用Poisson分布來表示，該分布在度的平均值<k>處有一峰值，然后按指數(shù)快速衰減。這類網絡被稱為均勻網絡(homogeneousnetwork)或指數(shù)網絡(exponentialnetwork)。2.3.4無標度網絡(scale-freenetwork)近年來，大量的實證研究表明，許多大規(guī)模真實網絡(如WWW、Internet以及新陳代謝網絡等)的度分布函數(shù)都是呈冪律分布的形式：P(k)8k-oY在這樣的網絡中，大部分節(jié)點的度都很小，但也有一小部分節(jié)點具有很大的度，沒有一個特征標度。由于這類網絡的節(jié)點的連接度并沒有明顯的特征標度，故稱為“無標度網絡”。為了解釋實際網絡中冪律分布產生的機理，BarabWsi和Albert在1999年提出了一個無標度網絡模型，稱為BA無標度模型。該模型的構造主要基于現(xiàn)實網絡的兩個內在機制：①增長機制：大多數(shù)真實網絡是一個開放系統(tǒng)，隨著時間的推移，網絡規(guī)模將不斷增大，即網絡中的節(jié)點數(shù)和連邊數(shù)是不斷增加的。②擇優(yōu)連接：新增加的節(jié)更傾向于與那些具有較高連接度的節(jié)點相連。也就是富人更富的觀點（richgetricher）。BA無標度網絡模型的構造算法：（1）增長：在初始時刻，假定網絡中己有m0個節(jié)點，在以后的每一個時間步長中，增加一個連接度為m的節(jié)點（mWm0）,新增節(jié)點與網絡中已經存在的m個不同的節(jié)點相連，且不存在重復連接。（2）優(yōu)先連接：在選擇新節(jié)點的連接點時，一個新節(jié)點與一個已經存在的節(jié)點i相連的概率■i與節(jié)點i的度ki成正比：n=Xk^（2-23）i乙kjj經過t步后，這種算法能夠產生一個含有N=t+m0個節(jié)點、mt條邊的網絡。如圖2-12所示的是m=m0=2時，BA網絡的演化過程。初始網絡有兩個節(jié)點，每次新增加的一個節(jié)點按優(yōu)先連接機制與網絡中已經存在的兩個節(jié)點相連。*.4??****n?,??=??Q???g????■.?■■■圖2-12BA無標度網絡的演化過程（取自文獻［］）/