小世界現象和分散式搜索 - The Small-World Phenomenon and Decentralized Search

snachina

小世界現象和分散式搜索 - The Small-World Phenomenon and Decentralized Search所謂小世界現象，或稱“六度分離（six degrees of separation）”，是社會網絡（social networks）中的基本問題，即每個人只需要很少的中間人（平均6個）就可以和全世界的人建立起聯系。在這一理論中, 每個人可看作是圖（graph）的節點，並有大量路徑連接著他們，相連接的節點表示互相認識的人。這是一個涉及社會學，數學和計算科學問題的多學科交叉問題。該問題源於社會心理學家Stanley Milgram上世紀60年代作的實驗：“追蹤美國社交網絡中的最短路徑”。他要求每個參與者寄信給一個住在波士頓附近的“目標人物”，規定每個參與者只能轉發給一個他們認識的人。Milgram發現完整的鏈平均長度為6個人。那麼為什麼社會網絡中只包含了如此短的路徑呢？

最近，應用數學家Duncan Watts和Steve Strogatz提出利用小世界性質（small-world property）來研究網絡：一個高度聚集的包含了“局部連接”節點的子網，連同一些隨機的有助於產生短路徑的長距離無規連接（random long-range shortcuts）。除了對社會、技術和生物網絡的唯象研究（empirical studies），Watts和Strogatz還考慮了以下簡單模型系統：以一個d維格點網絡開始（d-dimensional lattice network），給每個節點添加一些少量隨機長距離連接，把它們連接到隨機選擇的一些終點上。這樣構建的網絡將會有局域聚集（local clustering）現象及短的路徑，如同現實世界中發現的大多數網絡一樣。(圖1，2)






Milgram的研究有兩大發現，社交網絡中短路徑的存在僅是其一，其二是社會中的人們，他們僅知道自己認識的人，就能很快地把信件轉發到任何遠方目標。用計算術語來講，就是關於路由算法（routing algorithm）的效率問題，這一算法可完全依靠本地資訊來找到到達目的地的有效路徑。這一分散路由方案也有力地揭示了社會網絡中一些潛在的驚人特點。

模擬小世界現象的這一特點向人們提出了進一步的挑戰：我們能找到可以證明Milgram式分散路由生成的短路徑的模型系統嗎？對Watts-Strogatz模型及其變量的數學分析結果令人驚訝。首先，在一個帶均勻隨機連接（uniformly random shortcuts）的d-維網絡中，沒有找到關於搜索短路徑的分散算法；第二，這是一個具體的例子，在網絡中存在著短路徑，但本地資訊不足以構建這些路徑。

然而，更進一步研究，我們發現對Watts-Strogatz模型做一些微小改動就會使搜索更有效：不是均勻地加入長距離連接，而是按某種分布率在網絡結點間添加連接，即讓在d-維空間中節點連接的幾率隨距離的增大以d次冪衰減。實際上，隨距離的d-次冪幾率衰減統一了所有距離的“尺
度”——與一個節點距離為1 - 10節點構成連接的數目大致和它與距離為10 - 100，100 - 1000等的節點構成連接的數目一樣(圖3)。

在互聯網的點對點（P2P）文件共享系統中，這一利用連接幾率隨距離衰減的連接方式能夠建立搜索得到了證明。在P2P中，文件內容需要通過一個節點以分散方式檢索另一節點。換句話說，結點執行搜索協議時就像是在參與Milgram的實驗——令人驚奇地說明了在計算和社會科學中傳
遞資訊的方式。在計算世界里，數學模型被轉換為簡易的設計原則。
作者Jon Kleinberg是康奈爾大學電腦系的副教授。