2018年4月29日 星期日

小世界網絡與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 

沒有留言:

張貼留言