在社交網路中，如何去計算中兩個人之間的最短路徑？

12-18

騰訊朋友最近有新增這樣一個「六度人脈」功能，可以查看到你和一個陌生人之間可以通過哪幾個人認識，大概也就是所說的六度關係。

回歸到技術本身，個人覺得這個功能非常強大，因為計算量非常大。像朋友網這種是如何在海量的數據中，去找到兩個看似完全沒有關係的人之間的最短路徑呢？

Graph Database？抑或是MapReduce？或者是推薦引擎？

--
補充，本人其實不精演算法，只是好奇這一功能的實現，希望大家分享一下自己的看法。

個人天真的認為，是不是應該需要藉助於Graph Database，預先將每一個User分布在圖的位置，然後再通過A*等尋路演算法去查找？

無邀自答。

我們實驗室跟linkedin有合作，提出了最短路徑的近似演算法，大大提高了計算效率，後來也部署在linkedin相關係統中，現在google、人人、Zynga應該也在使用相關的系統。

具體可參考如下兩篇paper：
http://www.cs.ucsb.edu/~ravenben/publications/pdf/rigel-collab11.pdf
http://www.cs.ucsb.edu/~ravenben/publications/pdf/vicinity-wosn12.pdf

項目主頁和源碼可參考：
Rigel: Fast and Scalable Analysis of Massive Social Graphs

簡單來說，我們的方法藉助了網路坐標（network coordinates)相關的理論，將用戶間最短路徑的計算，近似轉化為坐標系統中的距離計算，因此大大提高了計算效率。

這個計算開銷非常高，距離大於3以後是很難算出的。我知道Facebook里似乎已經實現這個功能。微軟因為和Facebook有合作關係，他們也實現了這種計算，據說比Facebook自己的要快一些。

我記得聽微軟亞洲研究院的一個報告講過基於這種大規模圖的計算，如最短距離，pagerank等，他們做的框架叫Trinity，利用了GraphDB和Pregel，這兩個的細節可以google到。

Facebook最近的工作提出「四度分離」，計算了所有用戶之間的最短距離，論文可以看：http://arxiv.org/pdf/1111.4570，其中介紹了他們使用的演算法，你可以參考看看。

先佔坑寫些基本思路：

首先這個問題先簡化成六度計算，也就是，假設人與人之間關係最深為6，不計算超過6的。
然後，六度計算可以轉化成先用離線計算出3度人脈，然後再在需要查詢時，在線從兩端查3度人脈里有沒有對方三度人脈里出現的人，所以問題就轉化成了3度人脈計算。

3度人脈計算就是求稀疏矩陣的三次方：

遍歷所有邊，建立鄰接表。
然後再遍歷一遍所有邊，對每個邊上的點都需要遍歷該點上的所有一度邊，建立二度鄰接矩陣。按每個人有100個好友來算，大約計算量是100 * 邊數這個量級的。
然後再遍歷一遍由二度算出三度，由於二度邊大約每個點有100*100=10000條邊，所以計算量大約是10000 * 邊數這個量級。
邊數大約應該等於100倍的點數，這裡按100億來算，所以最終是
100萬億這個量級= =

按一台機器每秒1億計算量來算，大約需要100萬秒，大約不超過12天即可得出結果。

單機就能在不算長的時間裡算出來啊= =

暫時沒去算內存佔用情況之類的，不知道有沒算錯。
=======================================

前面的假設是平均一個人100個好友，如果要是每人1000好友，計算量就要大個1000倍了，耗時就不可接受了。
估計如果真到這個數量級，就只能想辦法把前面過程分散式化了

感謝朋友網這個驚艷的功能。以下僅為個人猜測，估計都是錯的，拋磚引玉獻醜了
假設朋友網的每一個人都能獲得300個直接人脈，那麼要計算甲到乙的路徑，需要遍歷甲的六度人脈300^6的確很可怕。。

不過實際上，查找甲和乙2個人的關係，那麼只要計算甲的三度內人脈300^3=2700w人，和乙的三度內人脈2700w人是否有相同的就可以了，這個數量級會比較小一點。實際上個人查詢過，和某個人沒法建立聯繫，說明朋友網實際上應該是控制了N度關係，計算量太大的7度關係八度空間之類的應該是不考慮了。
實際操作中，還可以根據地區，職業，年齡，學校，等因素進行預判縮小範圍。

難道路由器不是干這個的嗎？
每個註冊用戶模擬成一個路由器如何，伺服器就清閑了。

BFS可解，當然你可以限制一個最大RAM消耗，超過此值認為無解，或者你用分散式等手段突破RAM制約，不過那已經和演算法本身沒關係了。
也可以用點啟發式方法，兩側BFS然後選取順序依照相關性之類的。這個就看要求到什麼程度了。

我們是從兩端的用戶向中間遍歷的，每一級都是廣度優先遍歷。
算出的路徑不一定是最短路徑，同時最短路徑也不一定是最優路徑。
我個人在這個應用上的使用需求，是熟人優先。所以如果要產品化，我會設計讓用戶介入選擇。

計算方法有在線和離線兩種
1、先說離線。
離線的好處是查詢速度快，查詢量大的時候省伺服器資源。做兩個庫，一個庫用來查詢，一個庫做離線計算，算出來兩兩距離之後，兩個庫切換，然後另一個庫繼續計算。缺點是存儲消耗較大，實效性不強。

floyd演算法就是專門算矩陣任意兩點之間最短路徑的演算法，這是最完全樸素的演算法，複雜度是O(n^3)，
但實際產品的話肯定不能這麼幹了，計算量太大了，所以一般我們可以用很多不完全演算法，就是說大部分時候它比較準確，允許部分誤差。
比如說我們可以做6度假設，也就是說，假設絕大部分人之間的距離不超過6，那麼這樣計算量可以小很多。
聚類也可以減小很大計算量，把很相關的人聚在一起，簇的空間比較小，怎麼計算都行，再對簇外圍節點做一些特殊處理，提高準確度。
計算的時候可以使用很多現成的分散式框架，比如hadoop等，單機就別想玩了。

2、再說在線
在線的好處省空間，不用費很多資源保存計算結果，但計算的時候比較耗資源，人一上來搞不好就把伺服器撐爆了，另外比較耗資源。
在線就簡單了，直接雙向廣度優先搜索就行了，也可以做一些最大6度的限制，以免無限搜索。

個人推薦離線計算，比較穩定，實效性其實用戶也不關心也看不出來。

沒有專門搞過這個，所以只是大概想了一下，僅供參考。

……
說直接用某某輪子的，我覺得未免太背離題目本意。
1E+的節點，別說O(n^2)了，O(n)的話高並發之下我覺得都蠻暴力的……只是一個小功能，能分多少計算量啊。

從Linkedin之類的網站上來看，我個人的猜測是這樣的
離線：
計算每個用戶的所有1度鄰居、2度鄰居、……K度鄰居並保存。
在線：
當查詢用戶A和B之間的距離時，枚舉A用戶的1~K度鄰居，檢查其是否在B的1~K度鄰居之中。具體實現時，可以選擇1~K度鄰居中更少的那個。

這樣的話超過2K度的用戶關係都無法正確檢測，但是如果AB的距離在2K之內，單次查詢的時間是AB中鄰居數，這個比O(n)還是低了個量級的。完全load到內存的話也是可做的。
另外，離線部分也可以只在最開始做一次，之後在線地更新（每建立一個新的好友關係，也只需要在兩邊的K度鄰居之中各更新一遍）。

我的問題是，如果它是離線計算好的，那麼存儲運算結果是不可以接受的。如果任意兩個用戶都要存最短路徑，最終的矩陣肯定是稠密的。我們先不算它兩兩用戶要存下所有最短路徑的具體路徑。僅僅是兩兩用戶存一個int，我覺得複雜度就是不可以接受的。

我有一個idea，如果我們離線存儲最短路徑小於等於三的用戶網路圖，那麼在線我們就可以拿到路徑為6，9，12的。我看linkedin在提供長度超過3的路徑時，只提供了我認識人中誰和目標人物有路徑相連。

用 Neo4j

1.創建節點

create (p3:User {name:"張三"}), (p4:User {name:"李四"}), (p5:User {name:"王五"}), (p6:User {name:"趙六"}), (p7:User {name:"錢七"}), (p8:User {name:"孫八"}), (p9:User {name:"楊九"}), (p10:User {name:"吳十"});

2.創建關係

match (p3),(p4) where p3.name="張三" and p4.name="李四" create (p3)-[:HAS_FRIEND]-&>(p4);


match (p3),(p5)

where p3.name="張三" and p5.name="王五"

create (p3)-[:HAS_FRIEND]-&>(p5);
match (p4),(p6)

where p4.name="李四" and p6.name="趙六"

create (p4)-[:HAS_FRIEND]-&>(p6);
match (p4),(p7)

where p4.name="李四" and p7.name="錢七"

create (p4)-[:HAS_FRIEND]-&>(p7);
match (p5),(p8)

where p5.name="王五" and p8.name="孫八"

create (p5)-[:HAS_FRIEND]-&>(p8);
match (p5),(p9)

where p5.name="王五" and p9.name="楊九"

create (p5)-[:HAS_FRIEND]-&>(p9);

match (p6),(p10) where p6.name="趙六" and p10.name="吳十" create (p6)-[:HAS_FRIEND]-&>(p10);

3.查詢兩人（張三和吳十）之間最短路徑

match p = shortestPath( (p3:User {name:"張三"})-[:HAS_FRIEND*..3]-&>(p10:User {name:"吳十"}) ) return p;

結果如下圖：

美國的一個新聞分享網站Buzzfeed，它的一個致勝絕招，是一種叫Pound技術（Process for Optimizing and Understanding Network Diffusion 網路傳播優化與理解流程）：它是通過內容來分析社交網路中信息的流動方向和方式,從而去了解社交網路各個節點之間的關係，以及分析和判斷信息是在網路中那個節點引爆了網路效應。通常我們看到的一條微博，我們只能看到它的瀏覽量或點贊數，但通過這項技術我們就可以了解的更多了，for example:

在今年二月份左右，有一條信息在朋友圈廣為流傳，就是一條裙子：到底是白色和金色，還是黑色和藍色

圖中左邊部分圓圈不同顏色代表了不同的社交網站
Buzzfeed，就通過Pound技術對它進行了分析：

我覺得這項技術還是對社交網路有一定顛覆意義的，通過這項技術的應用，Buzzfeed每天都可以向用戶推薦非常有趣的內容，因為它知道什麼樣的內容讀者喜歡，什麼樣的內容，可以引爆網路效應。

對於這個技術的介紹也是Buzzfeed的創始人發的推文：Introducing Pound: Process for Optimizing and Understanding Network Diffusion

不就是跟路由選擇最近節點的原理一樣嗎…
假設從北京a到鄭州z有好多節點
路由如何選擇最短路徑，
同理，
找兩個人的中間的最短路徑和找兩個城市（mac地址）間的最短路徑不是一個道理嗎？

用neo4j可能比較好

我在neo4j中存儲了一個圖，節點大約2500-4000個，怎麼計算兩兩之間的路徑，並且對計算出來的路徑掃描一遍就可以了，怎麼實現較高效一點，採用neo4j中的Dijkstra演算法 or A*演算法？貌似不能一次得到一個點到其他所有節點的路徑，這樣的話麻煩就來了。

如果不超6就雙向廣度 floyd 笛杰特斯拉都不是很好用

MapReduce不太擅長這種類型的問題。
大概掃了一遍，發現沒人提到pregel。我這個人覺得pregel在這方面還是很有優勢的，畢竟它的思想就是「think like vertex」，生成了圖之後你想怎麼玩就怎麼玩，不過能不能在O(lg n)次迭代內完成還要看你問題和演算法。不過如果真的如題主說的，迭代六次就搞定了

一個陌生人通過哪幾個人認識難道不是2層關係而已嗎，就是這個陌生人認識我朋友中的哪幾個而已，有這麼複雜嗎？
6度關係無解，解出來也沒意義。就按每個人100個好友計算，6度關係就要計算1萬億人了，地球總共才多少人。

之前接觸過一個叫做xrime的計算框架，裡面有一系列的程序專門處理社交網路的，不能直接解決你的問題不過可以參考修改下。

不應該是雙向廣度優先搜索嗎？

根據6度理論，單機搞定地球人

我有一種想法（當然肯定不是朋友網的做法），把每個用戶的終端當作計算機網路模型中的一個路由器，然後通過類似網路層選路協議的方式進行計算，這樣似乎理論上可以分散式地計算出所有人之間的最短路徑，不過需要他們都有一定的登錄時間，並在每台機器上保存大量其他用戶的數據。

三度計算，其實就是求鄰接矩陣的三次方。facebook的量級，用spark加機器應該可以做，就是代價太大了。