collective dynamics of small

“小世界”網絡的集體動力學

Duncan J. Watts ， Steven H. Strogatz

美國紐約（14853）伊薩卡,康奈爾大學,Kimball學院理論與應用力學系

（）

NATURE | VOL 393 | 4 JUNE 1998 pp.440—442

（譯者 王恒山 上海理工大學管理學院、系統工程研究所 上海 200093）

....... ........... ............ ............ ............ ........... .........

1-45-67

連結動力系統的網絡已被用于為生物振蕩器

、約瑟夫森結陣列、應激介質、神經網

8-101112

絡、時空博弈、基因控制網絡以及許多其它自組織系統建立模型。通常，這些模型的

拓撲結構被假定為完全規則網，或完全隨機網。但許多生物網絡、技術網絡和社會網絡卻

介于這兩種極端的網絡之間。在這里我們探究能夠直達兩種極端網絡中間地帶的簡單網絡

模型：即通過重新連接規則網絡中結點之間的連線來增加該網絡的無規則性。我們發現這

些網絡能夠像規則網那樣具有高度的集群性，又像隨機網那樣具有短的特征路徑長度。由

1513-14

于具有類似小世界現象（即眾所周知的六度分離

），我們把它們稱為“小世界”網絡。

蠕線蟲的神經網絡、美國西部的電力網絡以及電影演員的協作網絡已被證明是小世界網絡。

具有小世界連接的動力系統模型顯示出能增強信號的傳播速度、計算能力和同步能力。尤

其是，傳染性疾病在小世界網絡中傳播比在規則網絡中要容易得多。

為在規則網絡和隨機網絡之間生成新的網絡，我們考慮以下隨機重新連線過程（圖1）。

從一個有

nkp

個頂點以及每個頂點有條邊的環形網絡開始，以概率隨機給每條邊重新連線。

這一連線過程允許我們在規則網(=0)和隨機網(=1) 之間生成各種網絡，因此就能探查我

pp

們還知之甚少的中間區域（0<<1）網絡的特性。我們用特征路徑長度()和集群系數 ()

PLpCp

來量化這些網絡的結構特性，如圖2所示。這里()度量圖中兩頂點之間的特征距離（一種

Lp

整體特性），而()度量鄰域之間的特征集群性（一種局部特性）。我們所關心的是這一網絡

Cp

具有許多稀疏連接的頂點，但卻沒有稀疏到使網絡圖面臨失去連通的危險。具體來說，我們

16

需要

nknkn

>>>>ln()>>1,其中 >>ln() 保證隨機網絡圖是連通的。在這種狀態下，我們發現

當→0時，～/2>>1以及～3/4，而當→1時，≈～ln()/ln()以及≈ ～

pLnkCpLLnkCC

randomrandom

knpLn

/<<1。這樣，當=0時的規則網絡是一種高度集群的大世界網絡，此時 隨 線性增長，

而當

p Ln

=1時的隨機網絡是一種低度集群的小世界網絡，此時僅隨成對數增長。這些有限

的例子可能導致人們推測大

C LCL

總是與大關聯，小總是與小關聯。

相反地，圖2揭示出有一個的廣闊區間,在這個區間上()幾乎與一樣小，但

pLpL

random

CpCLp

()>>。這些小世界網絡是通過引入幾條長距離的邊造成()的直接下降所致。這樣

random

的“捷徑”連線會以比方式不同方式連接更遠離得多的頂點。對于小,每個捷徑對有

LpL

random

一個高度非線性作用，不但縮小了它連結的一對點之間的距離，而且也縮小了它們所處的鄰

域之間的距離，以及鄰域的鄰域之間的距離等。相比之下，從一個集群鄰域中移去一條邊以

建立一個捷徑最多對

CLpPCp

有線性作用；因此，即使()急速下降，對于小來說，()仍然幾乎

不變。 這里的重要意義是在局部層次(由()反映)上向小世界網絡的轉變幾乎是無法覺察

Cp

的。為檢驗這些結果的穩定性，我們已經試驗了許多不同種類的原始規則網絡圖，還有隨機

重新連接的不同算法，所有都給出了質量相似的結果。唯一的要求是改寫連線邊的方式必須

會比

L

random

方式連接更遠離得多的頂點。

以上理想化的結構揭示了捷徑的關鍵作用。它暗示小世界現象可能在有許多點的稀疏網

絡中普遍存在，甚至捷徑只占一個微小比例就足夠了。為驗證這一觀點，我們計算了以下三

個網絡的

LC

和值，它們是特色電影（來自網站的數據）中演員的合作圖，

1

美國西部的電力網，以及蠕線蟲的神經網絡。所有三個網絡圖都有科學價值。電影演員合

18

作圖是社會網絡的替代品，對它的說明相對比較容易。對于傳統以P. Erd?s的觀點(部分數

據來自/,～grossman/)為中心的數學合作研究

19

圖也是類似的。電力網格圖是與電力網絡

的效率和穩定性相關的。而線蟲是完全反映神經

網絡的唯一例子。

表1說明三個圖都是小世界網絡。這些例子不是精心挑選的；之所以選它們是因為它們

13，14

內在的價值以及可以得到它們的完全連線圖。這樣，小世界現象就不僅僅是社會網絡

的

奇異特性，也不是理想模型的贗像——它或許對自然界許多大型稀疏網絡是一種普遍現象。

表1 小世界網絡的實際案例

---------------------------------------------------------

L L CC

actualrandomactualrandom

……………………………………………………………………………

電影演員合作網 3.65 2.99 0.79 0.00027

電力網 18.7 12.4 0.080 0.005

線蟲 2.65 2.25 0.28 0.05

……………………………………………………………………………

三個真實網絡的特征路徑長度和集群程度，與頂點()數量相同以及每個頂點擁有邊的平均數量相同的隨

LCn

機網絡圖之比較。(演員:

nkn knk

=225,226, =61. 電力網: =4,941,=2.67. 線蟲: =282, =14.) 網絡圖定

義如下：如果兩個演員在一部電影中共同表演，就把他們用一條邊連接起來。我們把討論限定在這個網絡

圖的巨大連通分支上

16

，這個分支包括到1997年4月為止存儲在因特網電影數據庫(來自)

里所有演員的90%。對于電力網絡來說，頂點代表發電機、變壓器和變電站，邊代表它們之間的高壓傳輸

線。對于蠕線蟲來說，如果兩個神經細胞由突觸或縫隙連接來連接的話，一條邊就會把這兩個細胞連起來。

我們把所有的邊看作是無向的和無權重的，把所有的頂點看作是相同的，并承認這些假設是粗糙的近似。

所有三個網絡顯示了小世界現象：

LLCC

17

randomrandom

,但 >>。

我們現在研究動力系統的小世界連通性的功能意義。我們的試驗案例是一個故意簡化的

傳染性疾病的傳播模型。人口結構由圖1所描繪的圖的家族建模。在時間=0時，一個單一

t

的傳染性個體被引入原來健康的人群。經過一段時期的疾病傳染后，傳染性個體就會被永久

移去(由于免疫性或死亡)。在這一時期，每一個傳染性個體會有概率為

r

的機會把疾病傳染

給它的每個健康鄰居。在隨后的各時間步中，疾病沿著網絡圖的邊進行傳播，直到它傳染了

整個人群，或在傳染了部分人群后逐漸消失。

圖1 在不改變網絡圖中頂點或邊的數量的情況下，在規則環形網絡和隨機網絡之間插入隨機改寫連線過

程。我們從有

nk

個頂點的環形開始，每個頂點由無向邊連到它的個最近的鄰點。為清楚起見，在這里的

示例中

nknk

=20，=4,而大得多的和用在本文的其它地方。我們選擇一個頂點和一條邊順時針方向連到離

2

它最近的鄰點。我們以概率

p

重新連接這條邊到一個在整個環上隨機選擇的頂點，連接時不允許出現重復

的邊；如果有重復的邊，就不連接這條邊。我們重復這一改寫連線過程，順時針方向沿環移動，依次考慮

每一個點直到一圈完成。然后，我們考慮連接該頂點到離它順時針方向次近的鄰點的那些邊。像前面一樣，

我們以概率

p

隨機為這些邊的每一條重新連線，繼續這一過程，繞環旋轉并且每一圈之后考慮向外面更遠

的鄰點連接，直到原來網絡的每條邊都已經被改寫完畢。(因為在整個圖中有

nkk

/2條邊，所以/2圈之后

重新連線過程結束。)在不同

ppp

值條件下的三個連線結果如圖所示。對于=0,原始環不變；隨著值的增

加，網絡圖變得越來越紊亂直到=1,所有的邊都是隨機重新連線的。我們的一個主要結論是對于值的中

pp

間值，曲線圖是一個小世界網絡：像規則網一樣高度集群，卻像隨機網一樣有較短的特征路徑長度。(見圖

2)

圖2 圖1中所描繪的隨機重新連線的網絡圖族的特征路徑長度()和集群程度()。這里被定義為兩

LpCpL

頂點之間最短路徑邊的數量，是所有兩頂點之間最短路徑邊的平均值。集群程度

Cp

()定義如下。假定每一

個點

vkvkv(kv-1)v

有個鄰點；于是在它們之間最多可以存在/2條邊 (這種情況發生在當的每一鄰點都連到

每一個

vCCvC

的其它鄰點時)。以表示實際存在的邊與允許存在的邊的比值。定義為所有的的平均值。對于

vv

朋友關系網絡，這些統計結果有直觀意義：

LC

是在連結兩個人的最短鏈中具有朋友關系的平均數量；反映

v

的是

VC

的朋友在多大程度上相互之間也是朋友；這樣度量的就是一個典型朋友關系中的集群性。數字中顯

示的數據是圖1所描繪的重新連線過程20個隨機實現的平均值，并且已經被一個規則網絡的

L C

(0)和(0)

值規范化。所有的網絡圖有

nk

=1,000個點，并且每個頂點平均有=10條邊。我們注意到一個對數水平的標

度被用于解決

L(p)

值的快速下降，相當于開始表現出小世界現象。在這一下降過程中，對于規則網絡來說

Cp

()幾乎保持不變，這標志著在局部層次上向小世界網絡的轉變幾乎是無法覺察的。

由此出現了兩種結果。第一種，在疾病傳染了一半人群時的臨界傳染性

rp

half

對于小值來

說急速下降(圖3a)。第二種，不管其結構如何，對于一種有足夠的傳染性以傳遍整個人群

的疾病，整個傳染需要的時間

TpLp

()類似于()曲線(圖3b)。這樣，傳染性疾病在小世界網

絡中預計傳播得更容易、更快；令人吃驚的和不太明白的一點是為什么使世界變小只需要少

數捷徑。

20-24

我們的模型在一些重要方面與其它疾病傳播網絡模型不同

。所有的模型顯示出網絡

結構影響疾病傳輸的速度和程度，但我們的模型卻闡明動力學過程可作為一個結構的明晰函

20-23

數(圖3),勝過一些特殊拓撲結構，比如隨機網絡圖、星型結構和鏈表結構

。在與本文緊

24

密相關的工作中，Kretschmar和Morris已經揭示出協作伙伴數量的增加能顯著加速一種沿

圖的邊傳播的性傳染疾病的傳播速度。所有這些圖都是不連通的，因為它們把每個人的合作

伙伴固定在

k

=1時的平均數。協作伙伴數量的增加通過圖的最大連通分支點數的增加而形成

更快的傳播速度。反之，我們所有的圖都是連通的；因此在傳播動力學中的預計變化是由微

妙的結構特征引起的，而不是由于連通性的變化。此外，協作伙伴數量的變化對一個個體是

顯而易見的，然而對引起小世界的轉變卻不易被發現。

3

圖3 一個簡單疾病傳播模型的模擬結果。這一群體結構是由圖1中按照隨機連線方式產生的網絡圖族的一

個。a, 當疾病傳染了人群的一半時的臨界傳染值隨值而減少。b,最大傳染性疾病(=1)傳遍整個人群

rpr

half

需要的時間

TpLp

()，與特征路徑長度()具有本質相同的函數形式。即使在原始網絡中僅有少數邊是隨機重

新連線的，全部傳染的時間也幾乎與隨機網絡圖一樣短。

我們也考察了在三個其它動力系統中小世界連通性的效果。在每種情況下，各元素都是

25

根據圖1所描繪的圖族連接的。(1)對承擔密度分類計算任務的元胞自動機

，我們發現運行

在小世界網絡圖上的簡單“多數規則”勝過運行在環型網格上所有已知的人工和遺傳算法產

生的規則。(2)在一個網絡圖上進行多人博弈“囚徒困境”的迭代時，我們發現隨著捷徑比

26

例的增加，在使用針鋒相對

策略的選手群體中很少出現協作。隨著值的增加，從原始合作

p

/非合作混合進化出合作策略的可能性也隨之下降。(3)具有耦合位相振蕩器的小世界網絡盡

2

管具有數量級較小的邊，卻幾乎與在平均場模型

中一樣容易同步。如果大腦具有小世界結

27

構似乎是真實的話，這一結果或許與在視覺皮層中觀察到的廣泛分離的神經細胞的同步是

相應的。

我們希望我們的工作能刺激小世界網絡的深入研究。小世界網絡同時具有特征路徑長度

短和集群程度高的特點，它們并不能從規則網絡或隨機網絡中推導出來。盡管小世界的體系

結構現在還沒有得到太多的關注，我們認為它可能會在生物系統、社會系統和人造系統中普

遍存在，而且通常具有重要的動力學地位。

收稿日期：1997-11-27; 接受日期：1998-04-06.

參考文獻及致謝見原文

4