復雜網絡的基礎知識

第二章復雜網絡的根底知識

2.1網絡的概念

所謂“網絡”(networks),實際上就是節(jié)點(node)和連邊(edge)的集合。如果節(jié)

點對(/,J)與(j,i)對應為同一條邊，那么該網絡為無向網絡(undirectednetworks),

否那么為有向網絡(directednetworks)。如果給每條邊都賦予相應的權值，那么該網絡就為

加權網絡(weightednetworks),否那么為無權網絡(unweightednetworks),如圖2-1所示。

圖2-1網絡類型例如

(a)無權無向網絡(b)加權網絡(c)無權有向網絡

如果節(jié)點按照確定的規(guī)那么連邊，所得到的網絡就稱為“規(guī)那么網絡〃(regular

networks),如圖2-2所示。如果節(jié)點按照完全隨機的方式連邊，所得到的網絡就稱為“隨

機網絡"(randomnetworks)°如果節(jié)點按照某種(自)組織原那么的方式連邊，將演化成

各種不同的網絡，稱為“復雜網絡”(complexnetworks)<,

圖2-2規(guī)那么網絡例如

(a)一維有限規(guī)那么網絡(b)二維無限觀那么網絡

2.2復雜網絡的根本特征量

描述復雜網絡的根本特征量主要有：平均路徑長度(averagepathlength),簇系數

(clusteringefficient)>度分布(degreedistribution)s介數(betweenness)等，下面介紹它

們的定義。

平均路徑長度(averagepathlength)

定義網絡中任何兩個節(jié)點i和/之間的距離力為從其中一個節(jié)點出發(fā)到達另一個節(jié)點

所要經過的連邊的最少數目。定義網絡的直徑(diameter)為網絡中任意兩個節(jié)點之間距

離的最大值。即

D=max{1^}(2-1)

定義網絡的平均路徑長度L為網絡中所有節(jié)點對之間距離的平均值。即

2N-lN

JN(N—1)ZZ%⑵2)

'M/=1j=i+]

其中N為網絡節(jié)點數，不考慮節(jié)點自身的距離。網絡的平均路徑長度L又稱為特征

路徑長度(characteristicpathlength)(,

網絡的平均路徑長度L和直徑D主要用來衡量網絡的傳輸效率。

2.2.2簇系數(clusteringefficient)

假設網絡中的一個節(jié)點i有左條邊將它與其它節(jié)點相連，這h個節(jié)點稱為節(jié)點i的鄰

居節(jié)點，在這k個鄰居節(jié)點之間最多可能有奴心-1)/2條邊。節(jié)點，的k個鄰居節(jié)點之間

實際存在的邊數M和最多可能有的邊數版心1)/2之比就定義為節(jié)點i的簇系數，記為

Ci.即

二2乂

整個網絡的聚類系數定義為網絡中所有節(jié)點i的聚類系數。的平均值，記為C。即

1N

。=萬斗(2-4)

顯然，0W仁1之間。當c=o時，說明網絡中所有節(jié)點均為孤立節(jié)點，即沒有任何連邊。

當時，說明網絡中任意兩個節(jié)點都直接相連，即網絡是仝局耦合網絡。

2.2.3度分布(degreedistribution)

網絡中某個節(jié)點i的度h定義為與該節(jié)點相連接的其它節(jié)點的數目，也就是該節(jié)點的

鄰居數。通常情況下，網絡中不同節(jié)點的度并不相同，所有節(jié)點i的度h的的平均值稱為

網絡的(節(jié)點)平均度，記為4＞。即

(2-5)

網絡中節(jié)點的分布情況一般用度分布函數Pe)來描述。度分布函數Pe)表示在網絡中

任意選取一節(jié)點，該節(jié)點的度恰好為女的概率。即

1Z

Pg=F)(k-Q(2.6)

???1

r=l

通常，一個節(jié)點的度越大，意味著這個節(jié)點屬于網絡中的關鍵節(jié)點，在某種意義上也

越“重要”。

2.2.4介數(betweenness)

節(jié)點，?的介數定義為網絡中所有的最短路徑中，經過節(jié)點，?的數量。用應表示。即

nX1g”】in,?

Bj=乙----m^n(2-7)

m,ng〃?”

式中gm為節(jié)點m與節(jié)點〃之間的最短路徑數，gmin為節(jié)點m與節(jié)點〃之間經過節(jié)

點，?的最短路徑數。

節(jié)點的介數反映了該節(jié)點在網絡中的影響力。

描述網絡結構的特征量還有很多，這里就不一一介紹，在使用到它們的地方再給出

詳細的說明。

23復雜網絡的根本模型

人們在對不同領域內的大量實際網絡進行廣泛的實證研究后發(fā)現：真實網絡系統往

往表現出小世界特性、無標度特性和高聚集特性。為了解釋這些現象，人們構造了各種

各樣的網絡模型，以便從理論上揭示網絡行為與網絡結構之間的關系，進而考慮改善網

絡的行為。下面介紹幾類根本的網絡模型。

2.3.1規(guī)那么網絡(regularnetwork)

常見的規(guī)那么網絡有三種：全局耦合網絡(globallycouplednetwork)最近鄰耦合網

絡(nearesi-neighborcouplednetwork)和星型網絡模型(starcouplednetwork),如圖2-3

所示。

圖2-3三種典型的規(guī)那么網絡

(a)全局耦合網絡(b)最近鄰耦合網絡(c)星型網絡

圖2-3(a)所示為一個含有N個節(jié)點的全局耦合網絡。網絡中共有MN-D/2條邊，

其平均路徑長度L=1(最小)，簇系數C=1(最大)。度分布P(L)為以N-1為中心的&函

數，

模型的優(yōu)點：能反映實際網絡的小世界特性和大聚類特，生。

模型的缺點：不能反映實際網絡的稀疏特性。因為一個具有N個節(jié)點的全局耦合網

絡的邊的數目為0(M),而實際網絡的邊的數目一般是0(N)。

圖2-3(b)所示為一個含有N個節(jié)點的最近鄰耦合網絡。網絡中的每個節(jié)點只和它

周圍的鄰居節(jié)點相連，其中每個節(jié)點都與它左右各K/2個鄰居節(jié)點相連(K為偶數)。

對于固定的K值，網絡的平均路徑長度為：

N

5777f8(N-8)(2-8)

2A

對于較大的K值，最近鄰耦合網絡的簇系數為:

4(K-1)4----

度分布P(k)為以K為中心的8函數。

模型的優(yōu)點：能反映實際網絡的大聚類特性和稀疏特性。

模型的缺點：不能反映實際網絡的小世界特性c

圖2-3(c)所示為一個具有N個節(jié)點的星型網絡。網絡有一個中心節(jié)點，其余N-1

個節(jié)點都只與這個中心節(jié)點相連，且它們彼此之間不連接。

網絡的平均路徑長度：

(Nf8)(2-10)

網絡的簇系數為:

(Nf8)(2-11)

N

網絡的度分布為:

(K=l)

P(K)聿(K=N—I)

(2-12)

0其它

規(guī)定：如果一個節(jié)點只有一個鄰居，那么該節(jié)點的簇系數為1。也有些文獻規(guī)定只有

一個鄰居的節(jié)點的簇系數為0,假設依此定義，那么星型網絡的簇系數為0。

模型的優(yōu)點：能反映實際網絡的小世界特性和稀疏特性。

模型的缺點：不能反映實際網絡的大聚類特性。

ER隨機網絡(randomnetwork)

該模型由匈牙利數學家Edds和Renyi在上世紀50年代最先提出，所以被人們稱為

ER隨機網絡模型。ER隨機網絡的構造有兩種方法。

第一種方法：定義有標記的N個節(jié)(網絡中的節(jié)點總數并且給出整個網絡的邊數

小這些邊的選取采用從所有可能的MNT)/2種情況中隨機選取。

第二種方法：給定有標記的N個節(jié)點，以一定的隨機概率p連接所有可能出現的

MN-1)/2種連接，假設最初有N個孤立的節(jié)點，每對節(jié)點以隨機概率〃進行連接。如

圖2-4所示。

圖24ER隨機網絡的演化示意圖

〔a〕〃=0時，給定10個孤立節(jié)點；〔b〕?(c)p=0.1,0.15時，生成的隨機圖

ER隨機網絡模型具有如下根本特性：

(1)涌現或相變

如果當NTOO時產生一個具有性質Q的ER隨機圖的概率為1,那么幾乎每一個ER

隨機圖都具有性質Qo以連通性為例，假設當連接概率〃到達某個臨界值p,、8(lnN)/N

時，整個網絡連通起來，那么以概率〃生成的每一個網絡幾乎都是連通的，否那么，當〃

小于該臨界值時，兒乎每一個網絡都是非連通的。

(2)度分布

對于一個給定連接概率為的隨機網絡，假設網絡的節(jié)點數N充分大，那么網絡的

度分布接近泊松(Poission)分布，如圖2?5所示。

P(k)=Ckpk(l-p)N-"kB與丁⑹⑵⑶

kl

式中＜心二雙N-lhPN表示ER隨機網絡的平均度。

圖2-5ER隨機網絡的度分布〔取自文獻||〕

(3)平均路徑長度

假定網絡的平均路徑長度為L，從網絡的一端走到網絡的另一端，總步數大概為乙

由于ER隨機網絡的平均度為＜k＞,對于任意一個節(jié)點，其一階鄰居的數目為＜&＞,二

階鄰居的數目為〈我＞2,以此類推，當經過L步后遍歷了網絡的所有節(jié)點，因此對于規(guī)模

為N的隨機網絡，有＜45由此可以得到網絡的平均路徑長度為：

InN_\nN

-ln(pN)-ln〈Q⑵⑷

由于InTV的值隨N增長較慢，所以規(guī)模很大的ER隨機網絡具有很小的平均路徑長

度，如圖2-6所示。

圖2-6ER隨機網絡的平均路徑長度與網絡規(guī)模的關系〔取自文獻［］〕

(4)簇系數

在ER隨機網絡中，由于任何兩個節(jié)點之間的連接概率〃都相等，所以ER隨機網絡

的聚類系數為：

C=〃=當(2-15)

N

可見，當網絡規(guī)模N固定時，簇系數隨著網絡節(jié)點平均度的增加而增加，如圖

2-7所示。當網絡節(jié)點平均度4〉固定時，簇系數隨著網絡規(guī)模N的增加而卜.降，如圖2-8

和所示。顯然，當N較大時，ER隨機網絡的簇系數很小。

圖2-7〔心10。ER隨機網絡的簇系數與連接概率的關系〔取自文獻［］)

圖2-8(/7=O.OOI5］ER隨機網絡的簇系數與網絡規(guī)模的關系〔取自文獻［］〕

模型的優(yōu)點：能反映實際網絡的小世界特性。

模型的缺點：不能反映實際網絡的大聚類特性。

小世界網絡(small-worldnetwork)

作為從完全規(guī)那么網絡向完全隨機網絡的過渡，美國學者Watts和Strogatz于1998

年設計了一個具有小的平均路徑長度和大的聚類系數的小世界網絡模型(small-world

network),簡稱WS小世界網絡模型。

WS小世界網絡模型的構造算法：

(1)從規(guī)那么網絡開始：考慮一個含有N個節(jié)點的最近鄰耦合網絡，它們圍成一個

環(huán)，其中每一個節(jié)點都與它左右相鄰的各K/2個節(jié)點相連，K是偶數。

(2)隨機化重連：以概率p隨機地重新連接網絡中的每一條邊，即將連邊的一個端

點保持不變，而另一個端點取為網絡中隨機選擇的一個節(jié)點。其中規(guī)定，任意兩個不同

的節(jié)點之間至多只能有一條邊，并且每個節(jié)點不能有邊與自身相連。

為了保證網絡具有稀疏性，要求N?K,這樣構造出來的網絡模型具有較高聚類系數。

而嵬機化重連過程大大減小了網絡的平均路徑長度，使網絡模型具有小世界特性。當p

取值較小時，重連過程對網絡的聚類系數影響不大。當〃=0時，模型退化為規(guī)那么網絡，

當p=l時，模型退化為隨機網絡。通過調節(jié)〃的值就可以控制模型從完全規(guī)那么網絡到完

全隨機網絡的過渡，如圖2-9所示.

圖2-9WS小世界網絡模型〔取自文獻〕

WS小世界網絡模型的其聚類系數和平均路徑長度可以看作是重連概率〃的函數，分

別記為C(p)和〃p),它們的變化規(guī)律如圖2-10所示。在某個〃值范圍內，WS網絡模型

可以得到既有較短的平均路徑長度1小世界特性)，又有較高聚類系數(高聚集特性)。

圖2-10中〃值在0.01附近的網絡即兼具這兩方一面的特征。

圖2-I0WS小世界網絡模型的簇系數和平均路徑長度隨〃的變化關系〔取自文獻|」〕

由于在WS小世界網絡模型的隨機化重連過程中有可能破壞網絡的連通性。為了防

止出現因重連而造成的孤立子網，美國學者Newman與Watts合作于1999年提出了用“隨

機化加邊”取代”隨機化重違〃的小世界網絡模型，稱“NW小世畀模型”。

NW小世界網絡模型的構造算法：

(1)從規(guī)那么網絡開始：考慮一個含有N個節(jié)點的最近鄰耦合網絡，它們圍成一個

環(huán)，其中每一個節(jié)點都與它左右相鄰的各月2個節(jié)點相連，K是偶數。

(2)隨機化加邊：以概率〃在隨機選取的一對節(jié)點之間加上一條邊。其中規(guī)定，任

意兩個不同的節(jié)點之間至多只能加一條邊，并且每個節(jié)點不能有邊與自身相連。

當〃=0時，模型退化為規(guī)那么網絡，當〃=1時，模型退化為隨機網絡。通過調節(jié)〃

的值就可以控制模型從完全規(guī)那么網絡到完全隨機網絡的過渡，如圖2-11所示。在〃較

小時，NW模型具有與WS模型類似的特性。

圖2/1NW小世界網絡模型〔取自文獻口〕

小世界網絡模型具有如下根本特性：

(1)簇系數

WS小世界網絡的聚類系數為：

C叱解"人-⑹

NW小世界網絡的聚類系數為：

.、一3(K―2)

''~4(K-\)+4Kp(p+2)(2-17)

(2)平均路徑長度

至今為止，還沒有人得到關于WS小世界網絡模型的平均路徑長度的精確解析表達

式，Newman,Moore和Walls分別用重整化群和序列展開方法得到如下近似公式：

L(p)=竺~j\NKpI"(2-18)

K

式中共")為一普適標度函數，且滿足:

constu?1

/(〃)=，

(\nu)/u)Q-19)

目前為止，還沒有.也，)的精確表達式，Newman等人基于平均場方法給出了如下的近

似表達式：

/1arctanhl-^—

fM?(2-20)

2>Jx2+2xVx+2

(3)度分布

對■于WS小世界網絡，當&2K/2時有:

min("4rf)L-^-n?

「叱gB?P)〃尸普X/.2D

當AVK/2時，P(攵)=0。

對于NW小世界網絡，每個節(jié)點的度至少為K,因此當時，一個隨機選取的節(jié)

點的度為攵的概率為：

/N、k-K,pxN-k+K

所也印(T)Q的

當&VK時，P伏)=0。

類似ER隨機網絡模型，WS小世界網絡模型也是所有節(jié)點的度都近似相等的均勻網

絡，

綜上所述,ER隨機網絡、WS小世界網絡和NW小世界網絡的度分布可近似用Poisson

分布來表示，該分布在度的平均值處有一峰值，然后按指數快速衰減。這類網絡被

稱為均勻網絡(homogeneousnework)或指數網絡(exponentialnetwork)<,

2.3.4無標度網絡(scale-freenetwork)

近年來，大量的實證研究說明，許多大規(guī)模真實網絡(如WWW、Internet以及新陳代

謝網絡等)的度分布函數都是呈嘉律分布的形式：Pg3%在這樣的網絡中，大局部節(jié)

點的度都很小，但也有一小局部節(jié)點具有很大的度，沒有一個特征標度。由于這類網絡的

節(jié)點的連接度并沒有明顯的特征標度，故稱為“無標度網絡〃。為了解釋實際網絡中塞律

分布產生的機理，Barab愈i和A由ert在1999年提出了一個無標度網絡模型，稱為BA無標

度模型。該模型的構造主要基于現實網絡的兩個內在機制：①增長機制：大多數直賣網絡

是一個開放系統，隨著時間的推移，網絡規(guī)模將不斷增大，即網絡中的節(jié)點數和連邊數是

不斷增加的。②擇優(yōu)連接：新增加的節(jié)更傾向于與那些具有較高連接度的節(jié)點相連。也就

是富人更富的觀點(richgetricher)o

BA無標度網絡模型的構造算法:

(1)增長：在初始時刻，假定網絡中己有mo個節(jié)點，在以后的每一個時間步長中,

增加一個連接度為，〃的節(jié)點新增節(jié)點與網絡中已經存在的〃?個不同的節(jié)點相

連，且不存在重復連接。

(2)優(yōu)先連接：在選擇新節(jié)點的連接點時，一個新節(jié)點與一個已經存在的節(jié)點，相

連的概率FL與節(jié)點i的度左成正比：

n「汽(2-23)

經過/步后，這種算法能夠產生一個含有2什〃W個節(jié)點、〃"條邊的網絡。

如圖2-12所示的是〃『〃加=2時，BA網絡的演化過程。初始網絡有兩個節(jié)點，每次

新增加的一個節(jié)點按優(yōu)先連接機制與網絡中已經存在的兩個節(jié)點相連。

圖2-I2BA無標度網絡的演化過程〔取自文獻［］〕

BA無標度網絡模型具有如下根本特性：

(1)平均路徑長度

BA無標度網絡的平均路徑長度為：

logN

LocloglogNQ-24)

這說明BA無標度網絡也具有小世界性。

(2)簇系數

BA無標度網絡的簇系數為：

"廣("7+l)”,(〃?+1