Random Rewiring

之前幫SD老師簡介social network時，有個地方含糊帶過(就是最下面那張圖)，這邊再簡單說明一下好了(雖然說沒人看得到XD)。首先，什麼是regular graph: graph上有n個點，每個點只與離它最近的k個點建立edge。什麼是random graph: graph上的每一點與其它點建立edge的機率都同為p。如果世界上每個人與隨機與其它50個人建立認識的關係，那麼60億人就滿足六度分離(Six Degrees of Separation)的特性。所謂的small world會是regular還是random graph? 這個問題先擱著，我們要先知道小世界最主要的精神: network裡面，人與人建立edge的機率是不一樣的，這個機率可能同時受到時空、文化、年齡、性別等等很多因素的影響，也就是network具有群聚現象(Clustering Effect)。

接著，我們簡單定義兩個衡量network的指標: 群聚度(Degree of Clustering)與分離度(Degree of Separation)。特定一個node的群聚度指的是network中，你的朋友的朋友也會是你的朋友的程度(好像在繞口令XD)，假設某個node有k個朋友，則此k個朋友彼此間所有可能形成的edge總數為k(k-1)/2，那麼該node的群聚度為此k個朋友間真正形成edge的總數除以可能形成的edge總數，如下圖，該點的群聚度為3/6=0.5。整個network的群聚度為所有node群聚度的平均值。network中，任兩個node的分離度為此二nodes的shortest path之長度，整個network的分離度為所有node pair分離度的平均值。

OK. 回到small world，剛才提到它必須具有clustering effect，也就是說，必須兼具高群聚度與低分離度的特性，從generative model的角度來看，如何建立出符合這兩個特性的small world network呢? 所要用到的概念就是edge的random rewiring了。Edge rewiring簡單說就是edge的重連，那麼，是要對誰做rewiring呢? 回憶一下比較容易被產生出來的regular graph與random graph，套用這兩個衡量標準來看，regular graph具有的是高群聚度與高分離度，而random graph則具有低群聚度與低分離度，這樣看起來small world似乎就處於此二者之間了，因此rewiring就是在他們之間做適度的調整。

對於有n個nodes，每個node有k條edge的ring lattice(regular graph)，以機率p來rewire它的edges，當p=0，所有edges沒有改變，還是regular graph；當p=1，所有nodes彼此必定隨機重新建立edges，形成random graph；當0<p<1時network的特性，就接近small world的群聚現象囉！如下圖是由regular graph向random graph做rewiring的示意過程(可以注意到過程中node總數與和edge總數都是不變的)。

或許有人會問，rewiring具體過程是怎麼跑的呢? 就用上面這張圖來說明吧！最左邊是一個具有20個nodes(n=20)、每個node有4條edges(k=4)的regular graph。我們可以依順時針方向，隨機選一個node和一條連到這個node最接近(length=1)的node的edge，以機率值p將該node重新連接(rewire)到其他node，其中target node是以相同的機率值p在整個network中挑出來的(如果這兩個nodes彼此間早已存在edge，就不用rewire了，繼續順時針往另一個node做下去)。當處理完所有nodes都跑過一次後，接著考慮到與該node第二接近(length=2)的node的edge，rewiring的方法和之前一樣。如此隨著每回合length漸增，最後當所有的edges都被rewire過後，就可以停止了(大概是在跑了k/2個回合後會停)。

這篇寫得很亂，看看就好orz