如何搜索社會網路[HP實驗室的一篇文章的意譯]

snachina

如何搜索社會網路[HP實驗室的一篇文章的意譯]社會網路收集用戶得社會聯繫。建造一個很大得互相聯繫得社會網路，並揭示他們直接是如何互相連接得。這個模式得前提是單獨得個體離一個目標或者社會伙伴僅僅幾步得距離，但是沒有意識到這點。這些服務允許他們得用戶了解他們得朋友得朋友因此來拓展他們得朋友圈子。在一個小得範圍內，在後文將描述NEXUS在線社區，將幫助STANDFORD大學得學生組織活動並且幫助他們在他們得網路中找到有相同得愛好得人。
在線社會網路得趨勢並不像小世界力量描述得現象一樣兩個人總是可以透過很短得聯繫聯繫起來。<關於小世界理論得實踐，可以參考http://www.sociology.columbia.edu。小世界現象得最短路徑得存在並不讓人特別吃驚，主要是因為隨機得熟人網路得人數是呈指數增長得。××××如果我們取一個人得熟人大概有1000人（POOL和KOCHEN估計1978年這個值在500到1500左右），那麼，一個人有1，000，000朋友得朋友，有1,000,000,000朋友得朋友。（按中國得人數來算，一個城市得成年人大概會有這個數字得認識得人－－認識得就是朋友吧，一個人也差不多可以認識全國人了吧）。
上述得計算約定這個網路是隨機得。一個人得朋友和他朋友得朋友得交集是忽略得。在顯示生活中，社會網路離隨機還有很遠。事實上，大部分人的朋友是建立在他的住所和頭班的基礎上的，並且精密的結合成小集團。這就意味著一個人的朋友的朋友就已經是這個人的朋友的一個組成部分。但是，就像WATTS和STROGATZ描述的一樣，還是有很少隨機的聯繫在不同的頭班和住所間來創建這個最短連接來使這個世界更小。
雖然存在最短路徑並不讓人吃驚，但是問題使雖然一個人有幾百個熟人，他還是可以找到合適的人來建立下一個連接。
KILLWORTH和BERNARD發現下小世界實踐中選擇一個聯繫人大部分都是選擇地理上的相近或者使頭班上和目標相近的聯繫人。最近，建立的數學模型解釋了為什麼這些簡單的策略對建立最短路徑是有效的。WATTS的模型約定獨立的個體屬於一個組成一個更多的群的某個層次的群。如一個人屬於一個實驗室，實驗室屬於某個部門，部門屬於某個大學.兩個獨立的個體直接的聯繫可能是和EXP-AH成比例的。H是他們在這個層次中最低的那個分支點，A是衰減系數。衰減意味著同部門的人互相認識的可能性大於不同部門但是同一公司的人。
WATTS ETAL表達了一個簡單的熱切的選擇下一步的搜索策略,就是選擇一個和目標最相近的屬性如頭班或者地理位置。在整個鏈條中的每個節點有一個固定的機率，稱為磨損率（不進一步傳遞訊息）。
對人工建造的網路的多次測試結果表明在一定範圍內的網路參數的條件下，被構件的網路是可以搜索的，意味著可以找到一個最小的路徑可以找到他們的目標－－在被磨損消耗之前。
KLEINBERG提出了一個相關的問題，如和構件一個社會網路以使用一個比較簡單熱切的策略可以找到最近最優的路徑。不像WATTS.ET.AL，在整個鏈條完成之前使沒有衰減的，但是需要和實際的最短路徑一樣成比例。

原文參考http://www.hpl.hp.com/research/idl，，Lada Adamic . and Eytan Adar