復(fù)雜網(wǎng)絡(luò)理論

文章編號:100124098

(

2005

)

復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用研究概述

劉 濤,陳 忠,陳曉榮

(上海交通大學(xué)安泰管理學(xué)院,上海 200030

)

摘 要:從統(tǒng)計(jì)特性、結(jié)構(gòu)模型和網(wǎng)絡(luò)上的動(dòng)力學(xué)行為三個(gè)層次簡述復(fù)雜網(wǎng)絡(luò)相關(guān)研究,并著

重介紹了網(wǎng)絡(luò)上的傳播行為,認(rèn)為它代表了復(fù)雜網(wǎng)絡(luò)在社會經(jīng)濟(jì)系統(tǒng)中的重要應(yīng)用。

關(guān)鍵詞:復(fù)雜網(wǎng)絡(luò);小世界;無標(biāo)度網(wǎng)絡(luò);疾病傳播

中圖分類號:

O

173 文獻(xiàn)標(biāo)識碼:

A

1 引言

結(jié)構(gòu)決定功能是系統(tǒng)科學(xué)的基本觀點(diǎn)[1]。如果我們將

系統(tǒng)內(nèi)部的各個(gè)元素作為節(jié)點(diǎn),元素之間的關(guān)系視為連

接,那么系統(tǒng)就構(gòu)成了一個(gè)網(wǎng)絡(luò),例如神經(jīng)系統(tǒng)可以看作

大量神經(jīng)細(xì)胞通過神經(jīng)纖維相互連接形成的網(wǎng)絡(luò)、計(jì)算機(jī)

網(wǎng)絡(luò)可以看作是計(jì)算機(jī)通過通信介質(zhì)如光纜、雙絞線、同

軸電纜等相互連接形成的網(wǎng)絡(luò),類似的還有電力網(wǎng)絡(luò)、社

會關(guān)系網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等等[2,3]。強(qiáng)調(diào)系統(tǒng)的結(jié)構(gòu)并從結(jié)構(gòu)

角度分析系統(tǒng)的功能正是復(fù)雜網(wǎng)絡(luò)的研究思路,所不同的

是這些抽象出來的真實(shí)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)性質(zhì)不同于以前

研究的網(wǎng)絡(luò),且節(jié)點(diǎn)眾多,故稱其為復(fù)雜網(wǎng)絡(luò)(

complex

networks

)。近年來,大量關(guān)于復(fù)雜網(wǎng)絡(luò)的文章在

Science

、

Nature

、

PRL

、

PNAS

等國際一流的刊物上發(fā)表,從一個(gè)側(cè)

面反映了復(fù)雜網(wǎng)絡(luò)已經(jīng)成為國際學(xué)術(shù)界一個(gè)新興的研究

熱點(diǎn)。

復(fù)雜網(wǎng)絡(luò)的研究可以簡單概括為最新電視劇有哪些 三方面密切相關(guān)卻

又依次深入的內(nèi)容:通過實(shí)證方法度量網(wǎng)絡(luò)的統(tǒng)計(jì)性質(zhì);

構(gòu)建相應(yīng)的網(wǎng)絡(luò)模型來理解這些統(tǒng)計(jì)性質(zhì)何以如此;在已

知網(wǎng)絡(luò)結(jié)構(gòu)特征及其形成規(guī)則的基礎(chǔ)上,預(yù)測網(wǎng)絡(luò)系統(tǒng)的

行為[3]。

2 復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)性質(zhì)

用網(wǎng)絡(luò)的觀點(diǎn)描述客觀世界起源于1736年德國數(shù)學(xué)

家

Eular

解決哥尼斯堡七橋問題。復(fù)雜網(wǎng)絡(luò)研究的不同之

處在于首先從統(tǒng)計(jì)角度考察網(wǎng)絡(luò)中大規(guī)模節(jié)點(diǎn)及其連接

之間的性質(zhì),這些性質(zhì)的不同意味著不同的網(wǎng)絡(luò)內(nèi)部結(jié)

構(gòu),而網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)的不同導(dǎo)致系統(tǒng)功能有所差異。所以,

對這些統(tǒng)計(jì)性質(zhì)的描述和理解是我們進(jìn)行復(fù)雜網(wǎng)絡(luò)相關(guān)

研究的第一步,下面簡述之。

2.1 平均路徑長度(

Theaveragepathlength

)

網(wǎng)絡(luò)研究中,一般定義兩節(jié)點(diǎn)間的距離為連接兩者的

最短路徑的邊的數(shù)目;網(wǎng)絡(luò)的直徑為任意兩點(diǎn)間的最大距

離;網(wǎng)絡(luò)的平均路徑長度

l

則是所有節(jié)點(diǎn)對之間距離的平

均值,它描述了網(wǎng)絡(luò)中節(jié)點(diǎn)間的分離程度,即網(wǎng)絡(luò)有多小。

復(fù)雜網(wǎng)絡(luò)研究中一個(gè)重要的發(fā)現(xiàn)是絕大多數(shù)大規(guī)模真實(shí)

網(wǎng)絡(luò)的平均路徑長度比想象的小得多,稱之為“小世界效

應(yīng)”[2]。這一提法來源于著名的

Milgram

“小世界”試驗(yàn)[4],

試驗(yàn)要求參與者把一封信傳給他們熟悉的人之一,使這封

信最終傳到指定的人,籍此來探明熟人網(wǎng)絡(luò)中路徑長度的

分布,結(jié)果表明平均傳過人數(shù)僅為六,這一試驗(yàn)也正是流

行的“六度分離”概念的起源[5]。

2.2 聚集系數(shù)(

Theclusteringcoefficient

)

聚集系數(shù)

C

用來描述網(wǎng)絡(luò)中節(jié)點(diǎn)的聚集情況,即網(wǎng)

絡(luò)有多緊密,比如在社會網(wǎng)絡(luò)中,你朋友的朋友可能也

是你的朋友或者你的兩個(gè)朋友可能彼此也是朋友。其計(jì)算

方法為:假設(shè)節(jié)點(diǎn)

i

通過

ki條邊與其它

ki個(gè)節(jié)點(diǎn)相連接,

如果這

ki

個(gè)節(jié)點(diǎn)都相互連接,它們之間應(yīng)該存在

ki(

ki-

1

)2條邊,而這

ki個(gè)節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)只有

Ei的

話,則它與

ki(

ki-1

)2之比就是節(jié)點(diǎn)

i

的聚集系數(shù)。網(wǎng)絡(luò)

第23卷第6期(總第138期) 系 統(tǒng) 工 程Vol.23,No.6

2005年6月 SystemsEngineering Jun.,2005

收稿日期:2005203225

基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(

70401019

)

;高等學(xué)校博士點(diǎn)科研基金資助項(xiàng)目(

2002048020

)

作者簡介:劉濤(

19782)

,男,湖北襄樊人,上海交通大學(xué)安泰管理學(xué)院博士研究生,研究方向:復(fù)雜網(wǎng)絡(luò),金融復(fù)雜性;陳忠

(

19432)

,男,上海交通大學(xué)安泰管理學(xué)院教授,博士生導(dǎo)師,研究方向:復(fù)雜性理論,智能管理;陳曉榮(

19722)

,女,上海交通大學(xué)安泰管

理學(xué)院講師,博士,研究方向:復(fù)雜網(wǎng)絡(luò)。

的聚集系數(shù)就是整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的聚集系數(shù)的平均。

顯然,只有在全連通網(wǎng)絡(luò)(每個(gè)節(jié)點(diǎn)都與其余所有的節(jié)點(diǎn)

相連接)中,聚集系數(shù)才能等于1,一般均小于1。在完全隨

機(jī)網(wǎng)絡(luò)中,

C

:

N-1,然而實(shí)證結(jié)果卻表明大部分大規(guī)模真

實(shí)網(wǎng)絡(luò)中的節(jié)點(diǎn)傾向于聚集在一起,盡管聚集系數(shù)

C

遠(yuǎn)

遠(yuǎn)小于1,但都遠(yuǎn)比

N-1大[2]。

2.3 度分布(

Thedegreedistribution

)

圖論中節(jié)點(diǎn)

i

的度

ki

為節(jié)點(diǎn)

i

連接的邊的總數(shù)目,所

有節(jié)點(diǎn)

i

的度

ki

的平均值稱為網(wǎng)絡(luò)的平均度,定義為<

k

>。網(wǎng)絡(luò)中節(jié)點(diǎn)的度分布用分布函數(shù)

p

(

k

)來表示,其含義

為一個(gè)任意選擇的節(jié)點(diǎn)恰好有

k

條邊的概率,也等于網(wǎng)絡(luò)

中度數(shù)為

k

的結(jié)點(diǎn)的個(gè)數(shù)占網(wǎng)絡(luò)結(jié)點(diǎn)總個(gè)數(shù)的比值。

2.4 其它性質(zhì)

上述三種統(tǒng)計(jì)特性是復(fù)雜網(wǎng)絡(luò)研究的基礎(chǔ),隨著研究

的深入,人們逐漸發(fā)現(xiàn)真實(shí)網(wǎng)絡(luò)還具有一些其它重要的統(tǒng)

計(jì)性質(zhì),例如:

(

1

)網(wǎng)絡(luò)彈性(

NetworkResilience

)

網(wǎng)絡(luò)的功能依賴其節(jié)點(diǎn)的連通性,我們稱網(wǎng)絡(luò)節(jié)點(diǎn)的

刪除對網(wǎng)絡(luò)連通性的影響為網(wǎng)絡(luò)彈性,其分析有兩種方式

——隨機(jī)刪除和有選擇的刪除,前者稱為網(wǎng)絡(luò)的魯棒性分

析,后者稱為網(wǎng)絡(luò)的脆弱性分析。

Albert

等人分別對度分

布服從指數(shù)分布的隨機(jī)網(wǎng)絡(luò)模型和度分布服從冪律分布

的

BA

網(wǎng)絡(luò)模型進(jìn)行了研究[6],結(jié)果顯示:隨機(jī)刪除節(jié)點(diǎn)

基本上不影響

BA

網(wǎng)絡(luò)的平均路徑長度,相反,有選擇的

刪除節(jié)點(diǎn)后,

BA

網(wǎng)絡(luò)的平均路徑長度較隨機(jī)網(wǎng)絡(luò)的增長

快得多。這表明,

BA

模型相對隨機(jī)網(wǎng)絡(luò)具有較強(qiáng)的魯棒

性和易受攻擊性。出現(xiàn)上述現(xiàn)象的原因在于冪律分布網(wǎng)絡(luò)

中存在的少數(shù)具有很大度數(shù)的節(jié)點(diǎn)在網(wǎng)絡(luò)連通中扮演著

關(guān)鍵角色,一般也稱它們?yōu)?/p>

Hub

節(jié)點(diǎn)。

(

2

)介數(shù)(

betweeness

)

介數(shù)分為邊介數(shù)和節(jié)點(diǎn)介數(shù)[7]。節(jié)點(diǎn)的介數(shù)為網(wǎng)絡(luò)中

所有的最短路徑中經(jīng)過該節(jié)點(diǎn)的數(shù)量比例;邊的介數(shù)含義

類似。介數(shù)反映了相應(yīng)的節(jié)點(diǎn)或者邊在整個(gè)網(wǎng)絡(luò)中的作用

和影響力,具有很強(qiáng)的現(xiàn)實(shí)意義。例如,在告知書怎么寫 社會關(guān)系網(wǎng)絡(luò)或

技術(shù)網(wǎng)絡(luò)中,介數(shù)的分布特征反映了不同人員、資源和技

術(shù)在相應(yīng)生產(chǎn)關(guān)系中的地位,這對于在網(wǎng)絡(luò)中發(fā)現(xiàn)和保護(hù)

關(guān)鍵資源和技術(shù)具有重要意義。

(

3

)度和聚集系數(shù)之間的相關(guān)性

網(wǎng)絡(luò)中度和聚集系數(shù)之間的相關(guān)性被用來描述不同

網(wǎng)絡(luò)結(jié)構(gòu)之間的差異[8],它包括兩個(gè)方面——不同度數(shù)節(jié)

點(diǎn)之間的相關(guān)性和節(jié)點(diǎn)度分布與其聚集系數(shù)之間的相關(guān)

性。前者指的是網(wǎng)絡(luò)中與高度數(shù)(或低度數(shù))節(jié)點(diǎn)相連接的

節(jié)點(diǎn)的度數(shù)偏向于高還是低;后者指的是高度數(shù)節(jié)點(diǎn)的聚

集系數(shù)偏向于高還是低。實(shí)證表明,在社會網(wǎng)絡(luò)(演員合作

網(wǎng)絡(luò)、公司董事網(wǎng)絡(luò)、電子郵箱網(wǎng)絡(luò))中節(jié)點(diǎn)具有正的度的

相關(guān)性,而節(jié)點(diǎn)度分布與其聚集系數(shù)之間卻具有負(fù)的相關(guān)

性;其它類型的網(wǎng)絡(luò)(信息網(wǎng)絡(luò)、技術(shù)網(wǎng)絡(luò)、生物網(wǎng)絡(luò))則相

反[9]。正因?yàn)槿绱?這兩種相關(guān)性被認(rèn)為是社會網(wǎng)絡(luò)區(qū)別

于其他類型網(wǎng)絡(luò)的重要特征,在社會網(wǎng)絡(luò)研究中引起了高

度重視[10]。

3 復(fù)雜網(wǎng)絡(luò)模型

最簡單的網(wǎng)絡(luò)模型為規(guī)則網(wǎng)絡(luò),其特點(diǎn)是每個(gè)節(jié)點(diǎn)

的近鄰數(shù)目都相同,如一維鏈、二維晶格、完全圖等。20

世紀(jì)50年代末

PaulErdos

和

AlfredRnyi

提出了一種完

全隨機(jī)的網(wǎng)絡(luò)模型[11],它由

N

個(gè)節(jié)點(diǎn)構(gòu)成的圖中以概率

p

隨機(jī)連接任意兩個(gè)節(jié)點(diǎn)而成,其平均度<

k

>=

p

(

N

-

1

)≈

pN

;平均路徑長度

l

:

lnN

ln

(

<

k

>

)

;聚集系數(shù)

C

=

p

;當(dāng)

N

很大時(shí),節(jié)點(diǎn)度分布近似為泊松分布:

P

(

k

)≈

e-<

k

>k

k

!.隨機(jī)網(wǎng)絡(luò)模型的提出是網(wǎng)絡(luò)研究中的重

大成果,但它仍不能很好的刻畫實(shí)際網(wǎng)絡(luò)的性質(zhì),人們又

相繼提出了一些新的網(wǎng)絡(luò)模型。

3.1 小世界網(wǎng)絡(luò)(

Small

2

worldnetworks

)

實(shí)證結(jié)果表明,大多數(shù)的真實(shí)網(wǎng)絡(luò)具有小世界性(較

小的最短路徑)和聚集性(相對較大的聚集系數(shù))[2],見表

1所示。然而,規(guī)則網(wǎng)絡(luò)雖具有聚集性,平均最短路徑卻較

大;隨機(jī)圖則正好相反,具有小世界性,但聚集系數(shù)卻相當(dāng)

小。

可見規(guī)則網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)并不能很好展現(xiàn)真實(shí)網(wǎng)絡(luò)

的性質(zhì),這說明現(xiàn)實(shí)世界既不是完全確定的也不是完全隨

機(jī)的。

Watts

和

Strogatz

在1998年提出了一個(gè)兼具小世

界性和高聚集性的網(wǎng)絡(luò)模型[12],它是復(fù)雜網(wǎng)絡(luò)研究中的

重大突破!他們通過將規(guī)則網(wǎng)絡(luò)中的每條邊以概率

p

隨

機(jī)連接到網(wǎng)絡(luò)中的一個(gè)新節(jié)點(diǎn)上,構(gòu)造出一種介于規(guī)則網(wǎng)

絡(luò)和隨機(jī)網(wǎng)絡(luò)之間的網(wǎng)絡(luò)(簡稱

WS

網(wǎng)絡(luò))

,它同時(shí)具有較

小的平均路徑長度和較大的聚集系數(shù),而規(guī)則網(wǎng)絡(luò)和隨機(jī)

網(wǎng)絡(luò)則分別是

WS

網(wǎng)絡(luò)在

p

為0和1時(shí)的特例。模型構(gòu)造

過程如圖1所示。

2

系 統(tǒng) 工 程 2005年

表1 實(shí)際網(wǎng)絡(luò)的

Small

2

world

現(xiàn)象[2]

NetworkSize

<

k

>

l

lrandC

Crand

WWW

,

sitelevel

153,12735.213.13.350.10780.00023

Internet

,

domainlevel

3015～62093.52～4.113.7～3.766.36～6.180.18～0.30.001

Movieactors

225,226613.652.990.790.00027

MEDLINEco

2

authorship

1,520,25118.14.64.910.066

1.110-5

Math

.

co

2

authorship

709753.99.58.20.59

5.410-5

E

.

coli

,

reactiongraph

31528.32.621.980.590.09

SilwoodParkfoodweb

1544.753.403.230.150.03

Workds

,

synonyms

22,31113.484.53.840.70.0006

Powergrid

4,9412.6718.712.40.080.005

C

.

Elegans

282142.652.250.280.05

注:下標(biāo)

rand

為隨機(jī)網(wǎng)絡(luò)模型下的計(jì)算,通過對比實(shí)際網(wǎng)絡(luò)與相應(yīng)隨機(jī)網(wǎng)絡(luò)(相同的節(jié)點(diǎn)數(shù)和邊數(shù))的性質(zhì),可以發(fā)現(xiàn)真實(shí)網(wǎng)絡(luò)

具有小世界和較高聚集系數(shù)的性質(zhì)。

圖1

WS

小世界網(wǎng)絡(luò)模型的構(gòu)造[12]

WS

模型提出后,很多學(xué)者在此基礎(chǔ)作了進(jìn)一步改

進(jìn)[13],其中應(yīng)用最多的是

Newman

和

Watts

提出的所謂

NW

小世界模型[14]。

NW

模型不同于

WS

模型之初在于

它不切斷規(guī)則網(wǎng)絡(luò)中的原始邊,而是以概率

p

重新連接

一對節(jié)點(diǎn)。

NW

模型的優(yōu)點(diǎn)在于其簡化了理論分析,因?yàn)?/p>

WS

模型可能存在孤立節(jié)點(diǎn),但

NW

不會。事實(shí)上,當(dāng)

p

很

小而

N

很大的時(shí)候,這兩個(gè)模型理論分析的結(jié)果是相同

的,現(xiàn)在我們統(tǒng)稱它們?yōu)樾∈澜缒Ｐ汀?/p>

3.2 無標(biāo)度網(wǎng)絡(luò)(

Scale

2

freenetworks

)

盡管小世界模型能很好的刻畫現(xiàn)實(shí)世界的小世界性

和高聚集性,但對小世界模型的理論分析表明其節(jié)點(diǎn)的度

分布仍為指數(shù)分布形式[15]。實(shí)證結(jié)果卻表明對于大多數(shù)

大規(guī)模真實(shí)網(wǎng)絡(luò)用冪率分布來描述它們的度分布更加精

確[2],即

P

(

k

)∶

k-,見表2所示。

3

第6期 劉濤,陳忠等:復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用研究概述

表2 實(shí)際網(wǎng)絡(luò)的

Scale

2

free

現(xiàn)象[2]

NetworkSize

<

k

>outinlreallrandlpow

WWW

,

site

325,7294.512.452.111.28.324.77

Internet

,

router

150,0002.662.42.41112.87.47

Movieactors

212,25028.782.32.34.543.654.01

Co

2

authors

,

SPIRES

56,6271731.21.242.121.95

Co

2

authors

,

math

.70,9751202.52.59.58.26.53

Sexualcontacts

2,8103.43.4

Metabolic

,

E

.

coli

7787.42.22.23.23.322.89

Protein

,

S

.

cerev

.18702.392.42.4

Citation

783,3398.573

Phonecall

531063.162.12.1

Words

,

co

2

occurrence

460,90270.132.72.7

注:下標(biāo)

out

、

in

分別表示出度和入度的冪率分布指數(shù),可見很多網(wǎng)絡(luò)的度分布具有冪率特征。下標(biāo)

real

、

rand

和

pow

分別表示真

實(shí)網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò)模型和

Scale

2

free

網(wǎng)絡(luò)模型中計(jì)算的平均路徑長度。

冪率分布相對于指數(shù)分布其圖形沒有峰值,大多數(shù)節(jié)

點(diǎn)僅有少量連接,而少數(shù)節(jié)點(diǎn)擁有大量連接,不存在隨機(jī)

網(wǎng)絡(luò)中的特征標(biāo)度,于是

Barabsi

等人稱這種度分布具

有冪率特征的網(wǎng)絡(luò)為

Scale

2

free

網(wǎng)絡(luò)[16]。為解釋

Scale

2

free

網(wǎng)絡(luò)的形成機(jī)制,

Barabsi

和

Albert

提出了著名的

BA

模型[17],他們認(rèn)為以前的網(wǎng)絡(luò)模型沒有考慮真實(shí)網(wǎng)絡(luò)

的兩個(gè)重要性質(zhì)——增長性和擇優(yōu)連接性,前者意味著網(wǎng)

絡(luò)中不斷有新的節(jié)點(diǎn)加入進(jìn)來,后者則意味著新的節(jié)點(diǎn)進(jìn)

來后優(yōu)先選擇網(wǎng)絡(luò)中度數(shù)大的節(jié)點(diǎn)進(jìn)行連接。他們不僅給

出了

BA

模型的生成算法并進(jìn)行了模擬分析[17],而且還

利用統(tǒng)計(jì)物理中的平均場方法給出了模型的解析解[18],

結(jié)果表明:經(jīng)過充分長時(shí)間的演化后,

BA

網(wǎng)絡(luò)的度分布

不再隨時(shí)間變化,度分布穩(wěn)定為指數(shù)為3的冪律分布。

BA

模型的提出是復(fù)雜網(wǎng)絡(luò)研究中的又一重大突破,

標(biāo)志著人們對客觀網(wǎng)絡(luò)世界認(rèn)識的深入。之后,許多學(xué)者

對這一模型進(jìn)行了改進(jìn),如非線性擇優(yōu)連接[19]、加速增

長[20]、重繞邊的局域事件[21]、逐漸老化[22]、適應(yīng)性競爭[23]

等等。需要注意的是,絕大多數(shù)而不是所有的真實(shí)網(wǎng)絡(luò)都

是

Scale

2

free

網(wǎng)絡(luò),如有的真實(shí)網(wǎng)絡(luò)度分布為指數(shù)分布截

斷形式[24]等等。

3.3 其它網(wǎng)絡(luò)模型

除了經(jīng)典的小世界模型、無標(biāo)度網(wǎng)絡(luò)模型之外,學(xué)者

們也提出了一些其它的網(wǎng)絡(luò)模型來描述真實(shí)世界的網(wǎng)絡(luò)

結(jié)構(gòu)。

(

1

)局域世界演化模型

李翔和陳關(guān)榮認(rèn)為擇優(yōu)連接機(jī)制不可能在整個(gè)網(wǎng)絡(luò)

上都起作用而只會在某個(gè)局域世界里被遵守,通過將局域

世界的概念引入

BA

模型對其作了推廣,提出了所謂的局

域世界演化網(wǎng)絡(luò)模型[25],其度分布介于指數(shù)網(wǎng)絡(luò)和無標(biāo)

度網(wǎng)絡(luò)的度分布之間。該模型表明,隨著局域世界的擴(kuò)大,

網(wǎng)絡(luò)演化越不均勻,越接近于

BA

模型,即:局域世界的規(guī)

模決定了網(wǎng)絡(luò)演化的非均勻性。

(

2

)權(quán)重演化網(wǎng)絡(luò)模型

上述研究均將網(wǎng)絡(luò)看作無權(quán)網(wǎng),然而現(xiàn)實(shí)網(wǎng)絡(luò)大多為

有權(quán)網(wǎng),即網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接強(qiáng)度是有區(qū)別的。

Yook

等

人提出了一種權(quán)重演化模型[26]:假定節(jié)點(diǎn)權(quán)重正比于節(jié)

點(diǎn)的度數(shù),也即度數(shù)大的節(jié)點(diǎn)擁有更大的權(quán)數(shù)。結(jié)果表明,

其度分布也符合冪律特征。

(

3

)確定性網(wǎng)絡(luò)模型

上述所有網(wǎng)絡(luò)模型都引入了某種程度的隨機(jī)性,那么

是否一定要有隨機(jī)性才能展現(xiàn)出小世界性和無標(biāo)度特性

呢?

Barabsi

等人提出了一種具有層次結(jié)構(gòu)的網(wǎng)絡(luò)模

型[27],它在確定性機(jī)制下也能表現(xiàn)出無標(biāo)度特性,節(jié)點(diǎn)度

分布為

P

(

k

)

:

k-

ln2

ln3。

4 復(fù)雜網(wǎng)絡(luò)的應(yīng)用

網(wǎng)絡(luò)結(jié)構(gòu)研究固然重要,但其最終目的是通過研究結(jié)

構(gòu)來了解和解釋基于這些網(wǎng)絡(luò)之上的系統(tǒng)運(yùn)作方式,進(jìn)而

預(yù)測和控制網(wǎng)絡(luò)系統(tǒng)的行為。一般將這種建立在網(wǎng)絡(luò)上的

系統(tǒng)動(dòng)態(tài)性質(zhì)稱為網(wǎng)絡(luò)上的動(dòng)力學(xué)行為,其涉及面非常之

廣,如系統(tǒng)的滲流[28]、同步[29]、相變[30]、網(wǎng)絡(luò)搜索[31]和網(wǎng)

絡(luò)導(dǎo)航[32]等等。上述研究理論性較強(qiáng),有一瀟灑走一回吉他譜 類應(yīng)用性很強(qiáng)

4

系 統(tǒng) 工 程 2005年

的網(wǎng)絡(luò)行為研究已經(jīng)日益引起人們的興趣,如計(jì)算機(jī)病毒

在計(jì)算機(jī)網(wǎng)絡(luò)上的蔓延、傳染病在人群中的流行、謠言在

社會中的擴(kuò)散等等,實(shí)際上它們都是一種服從某種規(guī)律的

網(wǎng)絡(luò)上的傳播行為。傳統(tǒng)的網(wǎng)絡(luò)傳播模型大都是基于規(guī)則

網(wǎng)絡(luò)的,復(fù)雜網(wǎng)絡(luò)研究的深入使我們重新審視這一問題。

下面我們著重介紹這類應(yīng)用研究。

網(wǎng)絡(luò)傳播行為的研究最初且仍是主要的目的之一是

為了了解疾病的傳播機(jī)制。一般用節(jié)點(diǎn)表示疾病傳染或感

染的個(gè)體,如果兩個(gè)個(gè)體之間可以通過某種方式直接發(fā)生

傳染與被傳染關(guān)系,就認(rèn)為這兩個(gè)個(gè)體之間存在連接,這

樣就得到了傳播網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),進(jìn)而可以建立相關(guān)模型

來研究這種傳播行為。顯然,網(wǎng)絡(luò)傳播模型研究的關(guān)鍵是

傳播規(guī)則的制定和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的選擇。

經(jīng)典的疾病傳播模型為

SIS

模型和

SIR

模型[33],它

們都將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)簡單的假定為規(guī)則網(wǎng)絡(luò)或者充分混

合均勻網(wǎng)絡(luò),區(qū)別在于傳播規(guī)則的不同。在

SIS

模型中,每

個(gè)節(jié)點(diǎn)處于兩種狀態(tài)——健康易受感染的和已被感染而

具有傳染性的;在

SIR

模型中,節(jié)點(diǎn)還可以處于另一種

“免疫”狀態(tài),這種狀態(tài)下的節(jié)點(diǎn)既不會被感染也不會感染

其它節(jié)點(diǎn),相當(dāng)于將它從傳播網(wǎng)絡(luò)中剔除掉。我們以

SIS

模型為例介紹其研究結(jié)果,首先隨機(jī)選擇網(wǎng)絡(luò)中一個(gè)或若

干節(jié)點(diǎn)為染病節(jié)點(diǎn),其余為健康節(jié)點(diǎn),在每一時(shí)間步,染病

節(jié)點(diǎn)的鄰近節(jié)點(diǎn)以概率

變成染病節(jié)點(diǎn),

稱為傳染率,

同時(shí)每個(gè)染病節(jié)點(diǎn)都依某個(gè)事先設(shè)定的痊愈率

變成健

康節(jié)點(diǎn),上述演化規(guī)則在整個(gè)網(wǎng)絡(luò)中被同時(shí)執(zhí)行。顯然,傳

染率越大,痊愈率越小,疾病就越有可能感染更多的人,一

般定義傳染率和痊愈率的比值為傳染強(qiáng)度

.研究表明,經(jīng)

典

SIS

模型存在一個(gè)傳染強(qiáng)度閾值

c

>0,如果

≥

c

,疾病

傳染將一直持續(xù)下去達(dá)到一個(gè)穩(wěn)定的范圍,此時(shí)稱染病節(jié)點(diǎn)

數(shù)占總節(jié)點(diǎn)數(shù)的比例為疾病傳染的波及范圍;相反,如果

<

c,疾病持續(xù)傳染一段時(shí)間后最終將全部被治愈。

然而,將疾病接觸網(wǎng)絡(luò)簡單抽象為規(guī)則均勻連接網(wǎng)絡(luò)

并不符合實(shí)際情況。

Moore

等人研究了小世界網(wǎng)絡(luò)中的疾

病傳播行為[34],發(fā)現(xiàn)疾病在小世界網(wǎng)絡(luò)中的傳播閾值明

顯比在規(guī)則網(wǎng)絡(luò)中小,相同的傳染強(qiáng)度下,經(jīng)歷相同時(shí)間

后,疾病在小世界網(wǎng)絡(luò)中的傳染范圍明顯大于其在規(guī)則網(wǎng)

絡(luò)中的傳染范圍,即:相對于規(guī)則網(wǎng)絡(luò),疾病在小世界網(wǎng)絡(luò)

中更適宜傳染;

Paster

2

Satorras

等研究了在無標(biāo)度網(wǎng)絡(luò)上

的傳染行為[35],結(jié)果令人震驚:無論是規(guī)則網(wǎng)絡(luò)還是小世

界網(wǎng)絡(luò),總存在正的傳染強(qiáng)度閾值,而無標(biāo)度網(wǎng)絡(luò)中疾病

傳染的閾值卻非常接近于零,如圖2所示。對

SIR

模型的

分析也可以得到類似的結(jié)果[36]。

圖2 規(guī)則網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)、無標(biāo)度網(wǎng)絡(luò)的疾病傳播波及范圍與傳染強(qiáng)度關(guān)系示意圖

由于大量的實(shí)證研究表明真實(shí)世界網(wǎng)絡(luò)既具有小世

界性又具有無標(biāo)度特性,上述結(jié)論是相當(dāng)令人沮喪的。所

幸的是,生活中無論是疾病還是計(jì)算機(jī)病毒的傳染強(qiáng)度都

非常小(=1

)

,危害不至于太大。然而,一旦疾病或病毒的

傳染強(qiáng)度較大時(shí)就必須高度重視其危害,對其的控制措施

也不能完全依賴于醫(yī)療衛(wèi)生條件的提高,而只能采取隔離

保護(hù)某些節(jié)點(diǎn)、強(qiáng)行切斷相關(guān)連接進(jìn)而中斷傳染途徑的方

法來改變傳播網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。事實(shí)上,我們也正是采用

上述方法成功的戰(zhàn)勝了2003年春夏之交席卷全國的

SARS

災(zāi)害。

疾病傳播機(jī)制的研究并非問題的全部,我們的最終目

的是研究如何有效控制疾病傳播。

Pastor

2

Satorras

等的研

究表明,在資源有限的情況下,優(yōu)先保護(hù)節(jié)點(diǎn)度數(shù)比較大

的節(jié)點(diǎn)比隨機(jī)選擇節(jié)點(diǎn)進(jìn)行保護(hù)效果要好得多[37]。然而

實(shí)際應(yīng)用中,節(jié)點(diǎn)的度,即:傳染期間與某個(gè)體有可能接觸

的個(gè)體數(shù)目,往往是很難統(tǒng)計(jì)的。比如在對性傳播疾病的

研究中,研究人員只能通過問卷和口頭詢問的方式獲知患

病者或高危人群的情況,但他們回答的可信度很低,有鑒

于此,一些學(xué)者依據(jù)上述思想提出了一些具有實(shí)際意義的

免疫策略,如“熟識者免疫”[38]、“接觸免疫”[39]、“環(huán)狀免

疫”[40]等等。

網(wǎng)絡(luò)傳播行為的研究不僅在于分析疾病傳播現(xiàn)象,而

5

第6期 劉濤,陳忠等:復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用研究概述

且可以用來分析其它許多事物的傳播行為。例如,我們可

以將其應(yīng)用于社會網(wǎng)絡(luò)上傳播行為的研究,基本思路如

下:首先從復(fù)雜網(wǎng)絡(luò)理論出發(fā)抽象出社會網(wǎng)絡(luò)的拓?fù)浣Y(jié)

構(gòu),然后按照一定的傳播規(guī)則分析其傳播機(jī)制,最后分析

如何通過一定措施影響這種傳播。事實(shí)上,這類研究工作

已經(jīng)開展起來,如:知識或技術(shù)的擴(kuò)散[41]、網(wǎng)絡(luò)新產(chǎn)品的

擴(kuò)散[42]以及銀行金融風(fēng)險(xiǎn)的傳染[43]等,它們既有聯(lián)系又

有區(qū)別,前兩者的研究目的是為了促進(jìn)傳播;后者則是為

了盡量避免傳播。

5 小結(jié)

本文從復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性、結(jié)構(gòu)模型以及發(fā)生在網(wǎng)

絡(luò)上的動(dòng)力學(xué)行為三個(gè)逐次深入的層面簡述了最近幾年

在國際學(xué)術(shù)界引起高度重視的復(fù)雜網(wǎng)絡(luò)領(lǐng)域的相關(guān)研究。

網(wǎng)絡(luò)是許多復(fù)雜系統(tǒng)的結(jié)構(gòu)形態(tài)[44],當(dāng)前對于復(fù)雜網(wǎng)絡(luò)

研究的興起正是自20世紀(jì)80年代中期興起的復(fù)雜性科

學(xué)研究的一個(gè)拓展。正因?yàn)槿绱?復(fù)雜網(wǎng)絡(luò)的研究也已經(jīng)

受到了我國學(xué)術(shù)界的特別關(guān)注[45],分別于2004年4月在

無錫、9月在杭州召開了全國范圍的研討班,掀起了復(fù)雜

網(wǎng)絡(luò)研究的熱潮。總之,面對這一全新而富有前景的領(lǐng)域,

我們應(yīng)該把握機(jī)遇,結(jié)合相關(guān)研究領(lǐng)域?qū)⑵渖钊腴_展下

去,為推動(dòng)我國社會和經(jīng)濟(jì)的持續(xù)發(fā)展作出應(yīng)有的貢獻(xiàn)!

參考文獻(xiàn):

[1] 許國志等.系統(tǒng)科學(xué)[

M

].上海:上海科技教育出版社,2000.

[2]

AlbertR

,

BarabsiA

2

L

.

Statisticalmechanicsofcomplexnetwork

[

J

].

ReviewofModernPhysics

,2002,74

(

Jan

.

)

:47～97.

[3]

NewmanMEJ

.

Thestructureandfunctionofcomplexnetworks

[

J

].

SIAMReview

,2003,45:167～256.

[4]

MilgramS

.

Thesmallworldproblem

[

J

].

PsychologyTody

,1967,2:60～67.

[5]

GuareJ

.

Sixdegreesofparation

:

aplay

[

Z

].

NewYork

:

Vintage

,1990.

[6]

AlbertR

,

JeongH

,

BarabsiA

2

L

.

Attackanderrortoleranceincomplex求職攻略 nerworks

[

J

].

Nature

,2001,406:387～

482.

[7]

GohK

2

I

,

OhE

,

KahngB

,

KimD

.

Betweennesscentralitycorrelationinsocialnetworks

[

J

].

Phys

.

Rev

.

E

,2003,

67:017101.

[8]

NewmanMEJ

.

Assortativemixinginnetworks

[

J

].

Phys

.

Rev

.

Lett

.,2002,89:208701.

[9]

NewmanMEJ

.

Whysocialnetworksaredifferentfromothertypesofnetworks

[

J

].

Phy

.

Rev

.

E

,2003,68:

036122.

[10]

JacksonMO

,

RogersBW

.

Searchintheformationoflargenetworks

:

howrandomaresociallygenerated

networks

?[

R

].2004.

[11]

ErdosP

,

RnyiA

.

Onrandomgraphs

[

J

].

PublicationesMathematicae

,1959,6:290～297.

[12]

WattsDJ

,

StrogatzSH

.

Collectivedynamicsof

″

small

2

world

″

networks

[

J

].

Nature

,1998,393

(

June

)

:440～442.

[13]

NewmanMEJ

.

Modelsofthesmallworld

[

J

].

J

.

Stat

.

Phys

.,2000,101:819～841.

[14]

NewmanMEJ

,

WattsDJ

.

Renormalizationgroupanalysisofthesmall

2

worldnetworkmodel

[

J

].

Phys

.

Lett

.

A

,1999,263:341～346.

[15]

BarratA

,

WeightM

.

Onthepropertiesofsmall

2

worldnetworkmodels

[

J

].

Eur

.

Phys

.

J

.,2000,

B

13:547～560.

[16]

BarabsiA

2

L

,

BonabeauE

.

Scale

2

freenetworks

[

J

].

ScientificAmerican

,2003,

(

May

)

:50～59.

[17]

BarabsiA

2

L

,

AlbertR

.

Emergenceofscalinginrandomnetworks

[

J

].

Science

,1999,286

(

Oct

.

)

:509～512.

[18]

BarabsiA

2

L

,

AlbertR

,

JeongH

.

Mean

2

fieldtheoryforscale

2

freerandomnetworks

[

J

].

PhysicaA

,1999,272:

173～187.

[19]

KrapivskyPL

,

RednerS

,

LeyvrazF

.

Connectivityofgrowingrandomnetworks

[

J

].

Phys

.

Rev

.

Lett

.,2000,85

(

21

)

:4629～4632.

[20]

DorogovtvSN

,

MendesJFF

.

Scalingpropertiesofscale

2

freeevolvingnetworks

:

continuousapproach

[

J

].

Phys

.

Rev

.

E

,2001,63:056125.

[21]

AlbertR

,

BarabsiA

2

L

.

Topologyofevolvingnetworks

:

localeventsandniversality

[

J

].

Phys

.

Rev北京狗

.

Lett

.,

2000,85

(

24

)

:5234～5237.

[22]

DorogovtvSN

,

MendesJFF

,

SamukhinAN

.

Structureofgrowingnetworkswithpreferentiallinking

[

J

].

Phys

.

Rev

.

Lett

.,2000,85

(

21

)

:4633～4636.

[23]

BianconiG

,

BarabsiA

2

L

.

Competitionandmultiscalinginevolvingnetworks

[

J

].

Eur

.

Phys

.

Lett

.,2001,54:

6

系 統(tǒng) 工 程 2005年

436～442.

[24]

AmaralLAN

,

ScalaA

,

BarthelemyM

,

StanleyHE

.

Classofbehaviorofsmall

2

worldnetworks

[

A

].

Proc

.

Natl

.

Acad

.

Sci

.

USA

97[

C

].2000:11149～11152.

[25]

LiX

,

ChenGR

.

Alocal

2

worldevolvingnetworkmodel

[

J

].

PhysicaA

,2003,328:274～286.

[26]

YookSH

,

JeongH

,

BarabsiA

2

L

.

Weightedevolvingnetworks

[

J

].

Phys

.

Rev

.

Lett

.,2001,86

(

25

)

;5835～

5838.

[27]

BarabsiA

2

L

,

RavaszE

,

VickT

.

Deterministicscale

2

freenetworks

[

J

].

PhysicaA

,2001,299:559～564.

[28]

CohenR

,

Ben

2

AvrahamD

,

HavlinS

.

Percolationcriticalexponentsinscale

2

freenetworks

[

J

].

PhysicalReview

E

,2002,66:036113.

[29]

WangXF

.

Complexnetworks

:

topology

,

dynamicsandsynchronization

[

J

].

Int

.

J

.

BifurcationandChaos

,

2002,12

(

5

)

:885～916.

[30]

GoltvAV

,

DorogovtvSN

,

MendesJFF

.

Criticalphenomenainnetworks

[

J

].

Phys

.

Rev

.

E

,2003,67:

026123.

[31]

KimBJ

,

YoonCN

,

HanSK

,

JeongH

.

Pathfindingstrategiesinscale

2

freenetworks

[

J

].

Phys

.

Rev

.

E

,2002,

65:027103.

[32]

KleinbergJM

.

Navigationinasmallworld

[

J

].

Nature

,2000,406:845.

[33]

HethcoteHW

.

Themathematicsofinfectiousdias

[

J

].

SIAMReview

,2000,42:599～653.

[34]

MooreC

,

NewmanMEJ

.

Epidemicsandpercolationinsmall

2

worldnetworks

[

J

].

Phys

.

Rev

.,2000,

E

61:5678

～5682.

[35]

Paster

2

SatorrasR

,

VespignaniA

.

Epidemicspreadinginscale

2

freenetworks

[

J

].

Phys

.

Rev

.

Lett

.,2001,86:

3200～3203.

[36]

MorenoY

,

Pastor

2

SatorrasR

,

VespignaniA

.

Epidemicoutbreaksincomplexheterogen

2

eousnetworks

[

J

].

Eur

.

Phys

.

J

.,2002,

B

26:521～529.

[37]

Paster

2

SatorrasR

,

VespignaniA

.

Immunizationofcomplexnetworks

[

J

].

Phys

.

Rev

.

E

,2002,65:036104.

[38]

CohenR

,

HavlinS

,

Ben

2

AvrahamD

.

Efficientimmunizationofpopulationsandcomputers

[

J

].

Phys

.

Rev

.

Lett

.,2003,91:247901.

[39]

KretzschmarM

,

VanDuynhovenYTHP

,

SeverijnenAJ

.

Modelingpreventionstrategiesforgonorrheaand

chlamydiausingstochasticnetworksimulations

[

J

].

Am

.

J

.

Epidemiol

.,1996,114:306～317.

[40]

MllerJ

,

SchonfischB

,

KirkilionisM

.

Ringvaccination

[

J

].

J

.

Math

.

Biol

.,2000,41:143～171.

[41]

CowanR

,

JonardN

.

Networkstructureandthediffusionofknowledge

[

J

].

JournalofEconomicDynamics&

Control

,2004,28:1557～1575.

[42] 段文奇,陳忠,陳曉榮.基于復(fù)雜網(wǎng)絡(luò)的新產(chǎn)品贈樣目標(biāo)優(yōu)化策略[

R

].上海:上海交通大學(xué)管理學(xué)院,2005.

[43]

WangYS

.

Twopower

2

lawdistributionmodelingofbankingnetwork

[

R

].

Shanghai

:

ShanghaiJiaotong

University

,2005.

[44]

StrogatzSH

.

Exploringcomplexnetworks

[

J

].

Nature

,2001,410

(

March

)

:268～276.

[45] 方錦清,汪小帆,劉曾榮.略論復(fù)雜性問題和非線性復(fù)雜網(wǎng)絡(luò)系統(tǒng)的研究[

J

].科技導(dǎo)報(bào),2004,

(貧富差距英文

2

)

:9～12.

ABriefReviewofComplexNetworksandItsApplication

LIUTao

,

CHENZhong

,

CHENXiao

2

rong

(

AetnaSchoolofManagement

,

ShanghaiJiaotongUniversity

,

Shanghai

200030,

China

)

Abstract

:

Inthispaperwebrieflyreviewthestudiesaboutcomplexnetworksfromthreelevels

,

statisticalproperties

,

structuremodelanddynamicalbehavior

.

Inspecially

,

weintroducethebehaviorofthespreadofinfectionover

networks

,

andwethinkitveryimportantinsocialandeconomicsystems

.

Keywords

:

ComplexNetworks

;

Small

2

world

;

Scale

2

freeNetworks

;

TheSpreadofInfection

7

第6期 劉濤,陳忠等:復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用研究概述