小世界網絡與Watts的小手段

有個有趣的實驗大家一定聽過，就是一個人在美國西岸，寄信給美國東岸的陌生人，平均只需要經過六步，就可以送達。這個「六度分隔實驗」背後的概念就是「小世界」。


小世界的概念簡單來說，就是世界上的人們各自群聚，大家分裂成東一塊、西一塊的，但是隨意的兩個人之間，卻能透過很短的步數連結起來。以送信的實驗為例子，美國的每個郡裡面的人民各自群聚，有很多的連結；而郡跟其他郡之間的人很少有連結，但是美國的任意兩個人，卻還是能透過六步的距離連起來。



不過，小世界要怎麼「證明」呢？除了上面那個看起來相當粗糙、容易出錯的實驗，還有什麼方法？Watts發明了一個模型，透過電腦模擬證明了小世界的普遍存在。

這個模型如上。它是一個有n個點的環形，且每個點與最鄰近的k個點相連接（k需為偶數），然後每條線有p的機率進行重連(0<p<1)，至於重連的點則是隨機的。在上面的圖例為n=20、k=4；當p=0時，此網絡為一個完全規律的網絡。當p=1時，此網絡為一個完全隨機的網絡。

為何要重連網絡？在當p=0時，網絡呈現支離破碎，各自群聚的樣態，而重連就是在模擬像下面的虛線，那些跨越團體的連帶。

接著，這邊要在講Watts用的兩個網絡的指標：clustering coefficient與path length，clustering coefficient代表「群聚係數」、path length代表「平均路徑長」。群聚係數的計算方式，是每個點它所連到的點之間，有多%少相連；用白話說「我的朋友，他們之間彼此認識的比例」，那所有點的平均即群聚係數。而平均路徑長則是網絡中任意兩個點，平均需要走幾步。

小世界網絡的特性，就是clustering coefficient很大，但path length很小。下圖就是Watts模擬出來的結果。Watts的模擬設定n=1000、k=10，他用完全規律的模型(p=0)作為對照組，可以發現群聚係數在p<0.1之前，幾乎不會有任何下降；但是平均路徑長已經迅速下降到1/10了。

好了，這邊就來講個Watts研究的小八卦。他這篇研究發表在世界頂級期刊Nature上，只有短短3頁但至今已經被引用3.6萬次以上。前陣子我用R寫了同樣的小世界網絡做模擬，發現了Watts在圖表上做了一點小手段。理論上模擬結果應該如下圖。

但實際上的結果通常是下圖：

原來，平均路徑長在低機率的網絡重連時，結果具有一定的隨機性，p<10^-3時，整張網絡重連的線不過十幾條。很容易因為這十幾條線，剛好連到很好的位置，讓path length大幅下降；或是很不幸的連到很爛的位子，path length還是很高。但重連的線一旦多起來，就會逼近常態，path length下降就會較為穩定。

所以Watts那張圖其實是做20次的平均結果。但，手段不只如此，我模擬了20次做平均的結果，還是相當起伏：

Watts為了讓曲線看起來更圓滑，他大概還三個點平均成一個點。這我從他圖片的刻度猜測的啦。

不過這並不影響論文的結論或權威性，只是有時候抓到學者為了讓數據看起來更漂亮，使了一點小手段，滿有趣的呢。


參考資料：
DJ Watts, SH Strogatz, 1998, "Collective dynamics of 'small-world' networks". Nature 393(04): 440–442