導語
1998年，一篇名為“小世界網絡的集體動力學”（Collective dynamics of ‘small-world’ networks）的文章發表於 Nature，首次提出“小世界網絡”的數學模型，並引起了來自社會科學、信息科學和自然科學等領域對這一模型的關注和應用。目前，該論文已經有超過 42000 次的引用量。本文是對這篇經典論文的簡要介紹。
原文主要從數學上定義了小世界網絡，對模型的全局性質和局部性質進行定量分析，並將其特徵與現實生活中的例子聯繫。作者還通過分析簡化的傳染病傳播模型，試圖推廣這一數學模型在動力學過程研究中的應用。
論文題目： Collective dynamics of ‘small-world’ networks論文地址：https://www.nature.com/articles/30918 從六度分隔到小世界網絡
小世界現象的概念最早大概出現於匈牙利作家考林蒂（Frigyes Karinthy）的短篇小說《鏈條》中，發表於 1929 年。
在《鏈條》這部小說中，一個人可以通過其認識的網球冠軍、網球冠軍的球友瑞典國王、瑞典國王又是諾貝爾獎的頒獎者這一路徑，以簡單明瞭的方式與一個諾貝爾獎的獲得者連接上。考林蒂的關於人與人之間最多需要 5 層關係就能聯繫起來的推斷，可以說是六度分隔假說的最早表述，也是“小世界網絡”概念的雛形。
20世紀60年代，美國哈佛大學心理學教授斯坦利·米爾格拉姆（Stanley·Milgram）組織了連鎖信件實驗，也被稱為小世界實驗（Small world experiment），並於1967年將此實驗的過程和結果發表於Psychology Today期刊：
一開始從Kansas和Nebraska兩個州招募了一批志願者，請他們分別將一封信轉寄給一個住在Cambridge的哈佛大學某學生的妻子和一個住在Boston郊區的股票經紀人。儘管志願者有寄信目標的相關信息，但是如果不是私人關係，不能把信直接寄給目標人，所以志願者每次只能把信寄給最有可能知道這個人的熟人。在哈佛大學的研究人員通過原始信封裡的追蹤卡片追蹤信函的路徑。
結果表明，信件經過約6次轉發後到達了目標收信人手中，後人稱為六度分隔理論（Six degree of seperation）。
隨後的幾十年中，人們發現小世界現象廣泛存在於各種社會網絡、電力網絡、生物神經網絡中。1998年，康奈爾大學的博士生的Duncan Watts與他的導師Steve Strogatz首次提出小世界網絡的概念和數學模型，嘗試解釋這一系列現象背後的原因。
關於小世界網絡的集智百科：
小世界網絡就在你身邊，你瞭解嘛？| 集智百科
小世界實驗：六度分隔理論的來源 | 集智百科
小世界網絡模型簡介：從規則網絡演化而來
Watts和Strogatz提出的小世界網絡模型，圖像上介於規則網絡（regular networks）和隨機網絡（random networks）之間——既表現出與規則網絡類似的高聚集性，又像隨機網絡一樣節點之間存在“捷徑”。
什麼是規則網絡？用n表示網絡的節點數，k表示網絡的連邊數，可以給出規則網絡的數學定義。以圖為例，有n=12，k=4的規則網絡由每個節點與之最近鄰的4個節點相連接而形成。
圖1：規則網絡
但真實世界的網絡不會這麼規則。於是 Watts 和 Strogatz 引入隨機性，重新設計了連接的規則。在規則網絡的基礎上，對每條連邊進行重新連接演化。
重新連接的規則是：從一個節點順時針方向的最近鄰連邊開始，此節點為出發點，連邊與其餘節點連接的概率為p。若還是與最近鄰節點相連，此連接保持不變。按此規則順時針方向遍歷所有節點的最近鄰連邊後，對每個節點的次近鄰連邊進行同樣的操作。
圖2：規則網絡演化為小世界網絡
當p=0時，原規則網絡不變。當0
圖3：規則網絡→小世界網絡→隨機網絡
其中，網絡的全局特徵和局部特徵，分別由結構參數特徵路徑長度L和聚集係數C來描述。
圖4：網絡特徵路徑長度示意
特徵路徑長度L 指的是，在網絡中任選兩個節點，連通這兩個節點的最少邊數，定義為這兩個節點的路徑長度(或長度)，如圖4中A到D的路徑長度為2（A→C→D）；網絡中所有節點對應的路徑長度的平均值，定義為網絡的特徵路徑長度L 。特徵路徑長度反映的是網絡的全局特徵。
對應到連鎖信件實驗（或小世界實驗）中，特徵路徑長度，即志願者將信寄給目標人物所需要的平均轉發次數。
聚集係數C 是指，假設某個節點有k條邊，則這k條邊連接的節點（k個）之間最多可能存在的邊的條數為k(k-1)/2，用實際存在的邊數除以最多可能存在的邊數得到的分數值，定義為這個節點的聚集係數。所有節點的聚集係數的均值定義為網絡的聚集係數。某個節點的聚集係數，反映了網絡在該點附近位置的局部特徵。
在社交網絡中，某個點聚集係數大，說明這個點代表的人有許多朋友，反之說明他的朋友少。
小世界網絡的結構特點
接著，作者分析此演變過程中特徵路徑長度、聚集係數隨重連接概率p的變化關係。
圖5：特徵路徑長度、聚集係數隨重連接概率 p 的變化
圖中的數據來源於對20個規則網絡（n=20，k=4）到隨機網絡演變做平均而得。其中L(0),C(0)分別是規則網絡的特徵路徑長度、聚集係數，L(p),C(p)分別對應重新連接概率為p時的特徵路徑長度、聚集係數。L=L(p)/L(0),C=C(p)/C(0)是以初始規則網絡為標準對所有數據進行歸一化。
研究者重點研究節點連接稀疏但不至於分離的小世界網絡。為了保證隨機圖是連接的，需要滿足n≫k≫ln(n)≫1。此條件下，研究者發現，當p趨於零時，L～n/2k，C～3/4；當p趨於1時，L≈Lrandom～ln(n)/ln(k) , C≈Crandom~k/n。其中，Lrandom定義為節點數為n，連接數為k的隨機網絡的特徵路徑長度，即p=1時的L；Crandom定義與Lrandom類似，即p=1時的C。
此時的規律是，規則網絡高度聚集，L隨n線性增長；隨機網絡聚集較弱，L隨n的對數增長。對這兩個極值情況的分析會讓人們誤以為聚集係數大的網絡特徵路徑長度的值大，聚集係數小的網絡特徵路徑長度的值小。
然而在p介於0和1的很長一段區間內，L趨於Lrandom時，C(p)遠大於Crandom。這種L(p)急劇變小的小世界網絡是少量的長連邊或捷徑（long-range edges /'short cuts'）的形成導致的 。長連邊接指對兩節點的連接長度小於Lrandom。當p很小的時候，每條捷徑的形成對L 會產生很強的非線性影響，除了被連接的節點被影響，還會影響到節點周圍的節點。
相比之下，移走一個聚集區域的節點而產生的捷徑，對C 產生線性的影響更明顯。因此，當p 很小的時候C(p) 基本上保持不變，但是L(p) 迅速變小。這意味著小世界中局部的變化是不明顯的。在經過重連接後形成捷徑的前提下，研究者對多種不同的起始網絡圖經過不同規則演化後進行了定量分析，都驗證了這一觀點。
小世界網絡的實例
作者從這一現象推測，在有許多節點的稀疏網絡中， 小世界效應或許非常普遍。通過計算演員合作網絡圖、美國西部電力輸送網圖和C. elegans線蟲的神經網絡圖，作者驗證了這一觀點: L≳Lrandom但是C≫Crandom。這也說明，小世界網絡並不僅存在於社交網絡中，而且很可能在自然界大型的稀疏網絡中普遍存在。
表1：三個生活中的小世界網絡例子
表中，Lactual指實際網絡結構的特徵路徑長度，Lrandom定義為節點數為n，連接數為k的隨機網絡的特徵路徑長度；Cactual與Crandom定義類似。
電影明星合作網絡中，每位明星為一個節點，若兩位明星共同出演過一部電影即可建立連接關係（數據來源http://us.imdb.com，數據統計截止於1997年4月）；在電力網絡中，每個發電機為一個節點，連邊表示與之連接輸電站和變電站的高壓輸電線；線蟲的神經網絡中，神經元為節點，連接神經元的突出或者間隙連接為連邊。所有連邊都是無向無權重的。
小世界網絡中的動力學：疾病傳播
研究者通過研究簡易化的傳播病傳染模型揭示了小世界網絡的動力學性質。
在上文所述小世界網絡模型（圖3）的基礎上，網絡上的疾病傳播，可以簡化為：t=0時刻，其中一個人（網絡中一個節點）被感染，其餘人健康。患病者在一段時間（記為單位時間1）後因死亡或被隔離而永久離開網絡。在這段時間中，病毒感染者傳染引起其餘健康個體患病的可能性為r。在接下來的時間中，病毒不斷在人群中傳播，直到整個群體被感染或者病毒滅亡。
圖6：全體感染所需時間T與概率p的變化關係，同圖5對數值進行重新標度
此簡化模型做小世界網絡演化後得到兩個結果。
- 傳染病感染一半群體所需的時間rhalf隨p的增大而減小（見圖6a）；
- 不管群體的網絡結構如何，全體感染所需要的時間T與p的關係T(p)與之前（圖5）L(p)相似（見圖6b）。
儘管網絡中只形成了少量的捷徑，小世界網絡模型全體感染所需的時間與隨機圖被全體感染的時間十分接近，即傳染病在小世界網絡中迅速傳染。研究者強調了他們的傳染病傳播模型與前人研究工作的不同。文中的模型將網絡的動力學性質T(p)描述為網絡結構的顯函數，不是關注某些隨機圖、散點或者鏈中特定的拓撲結構，而其他網絡模型只強調網絡的結構會影響傳染病傳播的速度和程度。文中的網絡圖皆為連接圖，所以所預測的動力學性質受微小的圖結構變化影響比不連接程度的影響更大。
結語
1998年時，小世界網絡的結構和動力性質方面的研究還沒有得到其他領域的關注。隨後的二十多年中，現實生活中出現越來越多的小世界網絡，其動力學性質應用於解釋導航（搜索）、同步、傳播以及博弈等複雜問題中。比如同步問題，因小世界網絡具有較大的局部群聚特性，同時又具有較短的 特徵路徑長度，所以小世界網絡實現同步的能力遠遠高於其對應的規則網絡。
至今，原文引用已達4萬多次。基於原文兩位作者的姓氏，這個小世界網絡模型後來被命名為Watts-Strogatz模型（或W-S模型）。
審校：劉培源
閱讀更多 集智俱樂部 的文章
