計算兩個用戶之間的社交距離

如何編碼能夠返回兩個用戶之間的社交「距離」的高效算法。計算兩個用戶之間的社交距離

例如，當您訪問個人資料在LinkedIn上，你可以看到什麼是你和用戶之間的距離。

- >用戶A是朋友與用戶B - 和B是朋友與C.當A將訪問C（的距離將1）

該圖是巨大的，所以我不知道如何將它表現得如此之快。

我知道，這個問題很可能被關閉，但我真的認爲這是一個編程/算法的問題 - 因爲我很感興趣這個概念我不會指定任何語言。

來源

2011-08-28 JohnJohnGa

你能否提供一個示例截圖和數據或者那些沒有LinkedIn的東西？ – Zirak

你是指大圓距離嗎？ http://en.wikipedia.org/wiki/Great-circle_distance –

@Zirak你可以看到我的例子，我編輯了帖子 – JohnJohnGa

假設你沒有要目標，即有效的最佳解決方案的距離任何heuristic function是bi-directional BFS：
算法想法：從源和目標同時做了BFS搜索：[BFS直到兩個深度1，直到兩個深度2，....]。
當您找到頂點v時，該算法將結束，該頂點v位於BFS的前面。

算法行爲：終止算法運行的頂點v將完全位於源和目標之間的中間。
這個算法在大多數情況下會產生好得多的結果，然後BFS從源頭[解釋爲什麼它比BFS更好]，並且肯定會提供一個答案，如果存在的話。

爲什麼它優於BFS從源頭？
假設源到目標之間的距離爲k，分支因子是B [每個頂點有乙邊緣。
BFS將打開：1 + B + B^2 + ... + B^k頂點。
雙向BFS將打開：2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2)頂點。

爲大B和K，第二個是明顯比第一好得多。

編輯：
注意，這種解決方案並不需要存儲在內存中的全圖，它只需要的功能實現：successor(v)它返回一個頂點的所有的接班人[所有頂點，你可以去，內1步從v]。由此，應該只存儲您打開的節點[2 + 2B + ... + 2B^(k/2)，如上所述]。爲了進一步節省內存，您可以從一個方向使用Iterative Deepening DFS而不是BFS，但它會消耗更多時間。

來源

2011-08-28 10:16:57 amit

這也意味着整個圖需要在內存中嗎？ – JohnJohnGa

@JohnJohnGa：沒有。所有你需要的是一個'繼承者（v）'函數，它可以返回v的所有後繼者[也就是說，你可以得到的所有頂點，在一步之內，從v]。只有打開的節點需要存儲在內存中。我會把這個添加到我的答案中。 – amit

接受，非常好的答案 - 這就是爲什麼我喜歡stackoverflow，我們可以得到答案，包括純粹algorthmic！ – JohnJohnGa

我會假設這可以通過應用最短路徑算法，如breadth first search到graph database來完成。但他們似乎將整個圖表存儲在內存中，至少根據this。

我確信，該算法最終歸結爲在圖結構（節點和邊）某些形式的最短路徑之一。

編輯：改變了算法按照意見。

來源

2011-08-28 10:12:04 arunkumar

是的 - 這就是爲什麼當你有大量的用戶 - 我真的不知道它是如何完成[如此快] – JohnJohnGa

爲什麼Dijkstra的算法如果圖不加權？只是BFS我猜:) –

你可以在這個案例中使用Dijkstra，使用weight = 1。但是BFS在這種情況下更好。 –

首先需要填充圖形。我不能說你如何從鏈接中獲得圖形，可能會創建節點的BFS或DFS，發現圖形並建立鏈接。要找到兩者之間的最佳距離，請從源節點創建BFS，並在找到目標時停止。如果你不暗示別的東西，我認爲這些鏈接沒有權重。

在這種情況下，當源節點不同時，您需要應用BFS來查找每對之間的距離。否則，您可以實現Floyd Warshall算法來獲取所有源所有目的地最短路徑，並且因爲每個鏈路具有相同的權重，它將獲得您想要的。在這種情況下，一旦建立了結構，對於任何來源和目的地，可以找到最短的距離。一個問題是網絡總是在變化，因此需要重新處理。所以BFS我認爲會很好。

爲了加快處理速度，您可以實現BFS並行運行。看看Design and analysis of a nondeterministic parallel breadth-first search algorithm

來源

2011-08-28 10:22:25 phoxis

計算兩個用戶之間的社交距離

回答

相關問題