如何設計數據結構和演算法，計算並存儲六度好友關係？

01-01

假設用戶總數是一千萬，平均有好友 25 個。如何能夠計算任意兩個用戶是否為六度之內的好友，度數是多少？
此外，以下要求哪些容易實現，哪些無法實現：

1. 能否快速獲取任意兩個用戶的好友關係度數（最大為六）

1a. 是否能夠將度數最大為六的限制任意提高？如計算得到某兩個用戶的關係度數是 100，兩個完全不連通的用戶關係度數可定義為正無窮。

2. 能否存儲或快速獲取任意兩個用戶之間的最短路徑？

2a. 能否同時存儲多條最短路徑？（最短距離為 2 時，即為快速獲取全部共同好友；最短距離為 3 時，路徑數量的上升應該會非常快）

3. 當用戶好友關係發生變化時，是否能增量更新之前的計算結果？抑或全局重新計算的效率比增量更新的效率更高？

4. 「進階」對於單向好友關係（如關注），六度理論的表述應該是什麼？

4a. 如果對於兩個關注方向，分別計算關係度數，演算法應該如何設計？

我在其他網站見過相似的問題，但是沒有令人滿意的回答，希望可以和大家在這裡討論一下。
上面第 4 點中的單向關係可能需要對模型做較大修改，如果需要的話，可以分離出來單獨提問。

不請自來，趁畢業論文間歇答一下這個問題。

先說一下幾個高票答主演算法存在的問題。

私以為目前最高票答主的回答並沒有實質的解決問題，只是在闡述這個問題基於矩陣的運算模型，諸位若是想要深入了解這個演算法不妨看看《演算法導論》第25章「所有頂點最短路徑問題（APSP）」第一節的內容，即計算「兩點之間有多少距離不超過m的路徑」這樣問題的原理，不再贅述。矩陣計算模型的時間複雜度無疑是 $O(V^3)$ ，空間複雜度也達到了 $O(V^2)$ ，在此基礎上做優化很難達到理想的效果。順便說一句，這個矩陣乘法做路徑統計還是很有趣的，還可以利用矩陣乘的結合律加速矩陣的冪運算。

另一個高票回答里，緩存三度好友列表存在一個潛在的問題：三度好友的數量真的只有 $25^3$ 個嗎？注意 $25$ 這個值只是節點的平均度數，而非最高度數。事實上，社交網路中用戶的好友數量基本上是符合zipf定律，用戶的好友數量和用戶在社交網路中的排名（好友數量的排名）成反比。注意到這個問題之後，就會明白這個列表的長度並不會如答主之願，只有不到 $15625$ 個；相反，這個數字可能會到幾萬甚至幾十萬。

再者，計算三度好友列表並存儲，如果遇到修改操作很難做出實時的反饋，因為修改一條邊，會影響到幾萬人的三度好友列表。

=====================================================================

其實這個問題並不複雜，三度好友列表不需要存儲，因為重新計算和修改都會很麻煩。

請不要用鄰接矩陣，使用鄰接表吧。

搜索可以使用雙向迭代加深搜索，演算法如下：

詢問起點和終點之間距離： 1. 初始總搜索深度限制C = 0，起點搜索深度限制A = 0，終點搜索深度限制B = 0，初始化一個當前時間戳標記。 2. 從終點開始深度優先搜索，搜索深度 &> B則跳出，在所有遍歷過的節點打時間戳標記。 3. 從起點開始深度優先搜索，搜索深度 &> A則跳出，如果遍歷到時間戳為當前時間戳的節點，跳6。 4. C = C + 1；若C &> 6，跳6。 5. 從起點出發遍歷過的節點數量 &> 從終點出發遍曆數量，則B = B + 1，否則A = A + 1。 6. 返回距離C。

幾個工程上可行的優化：

1. 把每個用戶的好友列表按照他們各自的好友數量排序。

2. 緩存2-限制搜索樹以及 3-限制搜索樹。（3-限制搜索樹的子樹顯然是2-限制搜索樹）

3. 緩存兩棵搜索樹之間是否存在交。

4. 深度優先搜索時不必判斷該點是否已經訪問過，這一條可以保證2中以任意點為根的k-限制搜索樹完全同構，又不影響演算法正確性。

當然，只是一些小trick，具體還要看實現。

==============================================================

說完演算法，就可以正面回答題主的問題了：

1. 能否快速獲取任意兩個用戶的好友關係度數（最大為六）

1a. 是否能夠將度數最大為六的限制任意提高？如計算得到某兩個用戶的關係度數是 100，兩個完全不連通的用戶關係度數可定義為正無窮。

度數超過6基本也就沒有意義了。

上述演算法獲取任意兩個用戶的好友關係度數，運算次數的階應當不超過任一用戶三度好友的數量。

2. 能否存儲或快速獲取任意兩個用戶之間的最短路徑？

2a. 能否同時存儲多條最短路徑？（最短距離為 2 時，即為快速獲取全部共同好友；最短距離為 3 時，路徑數量的上升應該會非常快）

需要注意到，深度優先搜索所遍歷的是一棵搜索樹，我們可以在遍歷搜索樹的過程中為每個節點記下它的父親節點。當以起點、終點為根的兩棵搜索樹的葉子節點x重合，那麼我們可以找到一條起點到終點的最短路徑，起點~葉子x~終點。

若想獲取所有的最短路徑，上述演算法在第3步不直接跳出即可，時間複雜度不變。

3. 當用戶好友關係發生變化時，是否能增量更新之前的計算結果？抑或全局重新計算的效率比增量更新的效率更高？

上述演算法不需要重新計算。

4. 「進階」對於單向好友關係（如關注），六度理論的表述應該是什麼？

4a. 如果對於兩個關注方向，分別計算關係度數，演算法應該如何設計？

單向好友關係相當於有向圖，依然是從終點逆向搜索，從起點正向搜索。

路徑長度限制的比較短時還是比較可做的

1：對於長度不超過六的情況，求出每個點三步可達的點集作成有序表，每個點度期望為25的話，表的大小只有25^3，比較兩個有序表是否有共同元素可以在線性時間內完成。（如果關係是有向邊，除了該點三步可達的點集，還要將邊反向求一個三步可達該點的點集）

2：存儲應該是不可行的，即時計算可能用A*比較合適，具體可以先用問題1存儲的點集嘗試建立一個非最優的初始解，迭代一下最短路徑長度的上限大概會好些。

3：與變化的關係兩端的點不存在三步可達關係的點集不需要更新。

4：六度理論的表述不清楚，不過這種情況下期望的步數似乎比十二少吧？

—————————————————————————————————————————————

似乎可以查閱一下複雜網路的相關資料

我來拋磚引玉。

以下討論同時適用於無向關係和有向關係。一般社交產品中，主動的關注關係比被動的關注關係對用戶更重要，因此以下只考慮主動關注。

如果用特徵矩陣存儲用戶的關注關係（好友關係表示相互關注，矩陣為對稱矩陣）

$mathrm{A}: A_{ij} = left{ egin{array}{l l} 1, ext{i 關注 j} \ 0, ext{otherwise} end{array} ight .$

則使用邏輯運算求得的矩陣自乘結果就是用戶間二度關係的特徵矩陣

矩陣元素間的乘法為邏輯與運算，元素間的加法為邏輯或運算

令 D(i,j) 表示用戶 i,j 之間關係的度數（距離），再定義 $A^k, B^k$ 如下

${ A^k | A^k_{ij} = 1 ext{ 表示 } D(i,j) leq k } \ { B^k | B^k_{ij} = 1 ext{ 表示 } D(i,j) = k }$

則有

$egin{align} A^{k+1} = A^k cdot A^1 , , (k geq 1) \ B^1 = A^1 \ B^{k+1} = A^{k+1} - A^{k} = A^k cdot (A^1 - I) , , (k geq 2) end{align}$

例子如下：

設 N = 6，用戶間有雙向關注關係 (1,4) (2,4) (2,5) (3,6) (5,6) 表示成特徵矩陣即為

（用戶默認關注自己）

$A^1 = left( egin{matrix} 1 0 0 1 0 0 \ 0 1 0 1 1 0 \ 0 0 1 0 0 1 \ 1 1 0 1 0 0 \ 0 1 0 0 1 1 \ 0 0 1 0 1 1 end{matrix} ight)$

則有

$A^2 = A^1 cdot A^1 = left( egin{matrix} 1 1 0 1 0 0 \ 1 1 0 1 1 1 \ 0 0 1 0 1 1 \ 1 1 0 1 1 0 \ 0 1 1 1 1 1 \ 0 1 1 0 1 1 end{matrix} ight) \ B^2 = A^2 - A^1 = left( egin{matrix} 0 1 0 0 0 0 \ 1 0 0 0 0 1 \ 0 0 0 0 1 0 \ 0 0 0 0 1 0 \ 0 0 1 1 0 0 \ 0 1 0 0 0 0 end{matrix} ight)$

所有二度關係有 (1,2) (2,6) (3,5) (4,5)

$A^3 = A^2 cdot A^1 = left( egin{matrix} 1 1 0 1 1 0 \ 1 1 1 1 1 1 \ 0 1 1 0 1 1 \ 1 1 0 1 1 1 \ 1 1 1 1 1 1 \ 0 1 1 1 1 1 end{matrix} ight) \ B^3 = A^3 - A^2 = left( egin{matrix} 0 0 0 0 1 0 \ 0 0 1 0 0 0 \ 0 1 0 0 0 0 \ 0 0 0 0 0 1 \ 1 0 0 0 0 0 \ 0 0 0 1 0 0 end{matrix} ight)$

三度關係有 (1,5) (2,3) (4,6)

繼續計算得到 $A^4 = (1)_{6 imes 6}$ 所有人都在四度關係內相連通

對於單向關係，計算是類似的，而且不用考慮矩陣的左乘右乘問題，因為二度好友的一度好友和一度好友的二度好友都是你的三度好友，左乘與右乘是完全等價的。

對於一千萬用戶平均關注 25 人的實際問題，只需要一種數據結構，實現稀疏邏輯矩陣的高效存儲和矩陣邏輯加法、邏輯乘法、代數減法的高效計算，即可較高效的計算用戶間的關係度數。

在常用的稀疏矩陣模型(CSR/CSC)基礎之上，由於只需要做邏輯運算，數據結構顯然有巨大的優化空間。而且用戶並非隨機關注，一個圈子內的用戶會互相關注，也許可以找到合適的矩陣分區方法，簡化計算。

基於以上說明，比起重新設計數據結構，挑選一個稀疏矩陣模型做優化更可取。這一點在 @Adder 之前的回答里也提到了。

若最多計算到 k=6 則令 $C = 1A^1+2A^2+3A^3+dotsc+6A^6, C_{ij}$ 即表示用戶 i,j 之間的距離

C 仍然是一個稀疏矩陣（但不再是邏輯矩陣）存儲 C 之後即可實現用戶關係度數的快速查詢

如果讓 k 進一步提高，C 會越來越稠密，主要的瓶頸應該是存儲，計算的代價也會增加。希望能有高手給出詳細的分析。

然後是 2，計算用戶間的關係路徑

如果存儲，當用戶間的距離較大時，空間代價極高，不可取。即使只對距離為 2 的用戶預計算並存儲共同好友，代價目測也比較高，不易實現。

我特地看了一下 LinkedIn，訪問了一些明顯和我沒有交集，關係度數不會太低的用戶，但在首次訪問對方頁面時 LinkedIn 就顯示出了我們的關係路徑，頁面載入只要幾百 ms，也沒有 Ajax。如下圖

我想了一下，要實現這個效果，還是有可能的。

如前面敘述，現在我們已經有了快速獲取任意兩個用戶間距離的方法（除非用戶之間的距離太大），所以在我的好友中找到所有到目標用戶的距離是我到目標用戶距離減一的人，即可顯示出上圖中的結果。

如果只需要找一條最短路徑，每次從好友中取出到目標用戶距離比我少一的人，幾步之內就可以得出結果。這個計算應該無法在線實時進行，但是耗時應該不會太長。前提還是大部分用戶之間的距離已經事先經過計算和存儲。

所以為了實現快速獲取最短路徑的功能，在第 1 步的稀疏矩陣模型基礎上，除了單個元素的高效讀取和高效的矩陣運算之外，還需要能夠高效地基於行/列進行檢索。

接下來是 3

當新的關注關係建立時，可以增量更新受影響的節點，但是原有關係刪除時，則無法高效的增量更新。同時考慮到每個新關係建立時，需要計算和修改的關係量都會很大（ $10^3sim 10^5?$ ），增量更新也許得不償失。

最後是 4

前文說明中的所有矩陣運算，對於無向關係和有向關係都是適用的。只要選定一種關係方向作為「關注」，所有的討論都直接成立。上面的運算中應該沒有能用到矩陣對稱性的地方，所以計算複雜度也不會增加。

而且如果不做增量更新，不需要額外計算反向關係。

以上為拋磚，並沒有真正解決這個問題的核心，也就是支持邏輯運算的係數矩陣的數據結構設計，也無法確定這是不是正確的方向。希望能引得玉來。

這是一個非常有趣的問題, 現實工程中也被人實現較多, 其實不是那麼的難!

最關鍵的優化點其實是:

1. 雙向廣搜, 把六度直接降為三度, 計算量一下就減化非常非常的多了, 雖然其實還是指數級的複雜度.

2. 緩存二度/三度好友的結果, 用空間換時間

1. 能否快速獲取任意兩個用戶的好友關係度數（最大為六）

能, 假設最壞的情況, 即兩個用戶剛好是六度, (如果是三度, 四度, 更容易算出來):

一度好友是 25個, 那三度好友最多是: 15625 個好友, 由於現實數據一定有很多的交集, 可能最終是 8000, 甚至不到5000個好友. 兩個用戶都先算出他的 5000 個三度好友, 然後相交一下, 看有無交集?

如果有交集, 那就是六度好友(其實也可能是四度, 甚至二度好友, 所以要先把這種情況算出來), 如果沒有, 那一定不是六度好友.

如何求三度好友? 對於 1kw 用戶來說, 其實預計算緩存三度的結果也挺簡單的, 數據量沒有多大.

5000個用戶id, 壓縮壓縮10K肯定能搞定, 乘以1kw, 也就是不到100GB的數據.

按用戶去做hash存儲, 大多數據用不到, 緩存命中率能很高, 真這個數據規模的話, 單機已經基本能夠做到了准實時的查詢了(50ms以內返回).

預處理的時候, 確實需要一些時間.

1a. 是否能夠將度數最大為六的限制任意提高？如計算得到某兩個用戶的關係度數是 100，兩個完全不連通的用戶關係度數可定義為正無窮。

這個我的理解是不可能的, 好在這是指數的增長, 所以現實中, 超過 6度, 到 8度, 甚至更高的幾乎完全沒有意義, 幾乎一定互聯! 允許一定誤差的話, 不計算, 直接告訴互聯就OK了!

特殊場景, 或者刻意構造數據是有可能的, 但是類似孤島數據, 鏈式數據... 這個可以特殊處理, 一般線上系統就是捨棄這種精度了.

2. 能否存儲或快速獲取任意兩個用戶之間的最短路徑？

能, 類似 1. 的解法, 還是雙向廣搜, 記路徑, 存儲空間會適當增加, 或者得到中間人後, 重新算到每個中間人的最短路徑, 得到最終的最短路徑. 計算時間和存儲空間肯定要增加不少. 但是量級應該不變!

3. 當用戶好友關係發生變化時，是否能增量更新之前的計算結果？抑或全局重新計算的效率比增量更新的效率更高？

前面的方案是緩存一度, 二度, 甚至是直接緩存三度的關係, 所以一條關係改變, 修改量會放大幾千倍, 對於修改量不是特別誇張的, 也能接受, 否則的話, 不如定期重新計算效率高.

工程中更多的折衷後的結果很可能是: 緩存二度的好友關係, 三度好友實時算. 好友關係變化時, 更新一度好友列表的同時, 也立即更新二度好友.

4. 「進階」對於單向好友關係（如關注），六度理論的表述應該是什麼？

這個更多的像是一個環, 就不能直接用前面說的雙向廣搜的優化了. 因為他依賴於兩邊關係是一樣的. 但是適當變形, 其實也能做, 就是 A 關注的人列表和 B的粉絲列表去算...

雙向遍歷好友並緩存，優先遍歷好友少的那個人，如果找到共同好友或遍歷達到6次，結束。

很多答主將「人際關係距離」這個問題抽象成了無向圖上的最短路問題，題主或許也有這樣的想法。

我分兩個角度回答你的問題。

首先不考慮你給出的數據規模，僅僅在演算法複雜度上的度量。

你的1和2問題即是圖上的最短路問題，對於單個query，複雜度為 $O(V^2)$ 的Dijkstra"s algorithm演算法可以解決你的問題。同時由於圖上存在最小環為6的特性，一個最多迭代6次的廣搜演算法在這個數據規模上也是可以接受的。而對於給定圖的多個query，複雜度為 $O(V^3)$ 的Floyd"s algorithm演算法可以一次給出所有pairwise的最短路，之後的查詢即是 $O(1)$ 的。

你的3問題是fully dynamic ASAP problem, 是眾多dynamic graph問題中的一個重要部分: 最粗暴的想法是，如果在insert new edge or vertex後用Floyd暴力更新所有點對的最短路徑長，需要的時間複雜度至少是 $O(V^3)$ 的。這個問題的tight lower bound至今仍是open problem。

一個較好的approach中給出了一種動態規劃演算法，提供了 $O(|V|^2log|V|)$ 的更新複雜度（以及 $O(1)$ 的query複雜度）:stanford.edu 的頁面注意雖然我們有對於單個query $O(V^2)$ 的查詢演算法，但是對於大量query少量update的情況，一個slitly slower的更新演算法是prefer的。

當然，上述是在演算法層面做的複雜度分析，具體去做最短路，實際開發環境中還或多或少需要常數優化與稀疏矩陣等等的應用，上面的朋友們都提到了具體的步驟，不加贅述。

但是回過頭來，在千萬乃至上億規模的「大數據」背景下，將這個問題歸結到傳統演算法中的最短路問題，是否合適呢？

複雜度分析已經顯示，在大數據規模下，傳統的確定性演算法很難efficient的解決問題。 $O(|V|^{2+epsilon})$ 的演算法在千萬級別下已經會有明顯的處理延遲，這樣的時間cost是常數優化無法解決的。

題主手上的這1000萬數據，不可能僅僅只是兩兩人之間是朋友而已——這樣的數據中，往往包括了人的姓名、地址、年齡、喜好，甚至他們在社交網路上的互動，他們的特別關注，他們偷偷摸摸點開的鏈接，等等等等，非常豐富的信息。顯然，兩個上過同所學校的人很有可能是相識，兩個在同一領域工作的人或許會相互了解。這樣的數據，往往將人們「聚集成類」，比如小學同學圈，大學同學圈，職場圈子，等等等等。這時考量一個人的「人際關係距離」，可以考察他到一個「圈子」的距離，再考察跑到這個「圈子」里距離。「人」是千萬上億的，但「人」的聚類——這樣「圈子」一般的東西的規模是可接受的。上述的就是數據的聚類(cluster)思想與量化(quantization)方法。

草草找到一篇same background的文章，歡飲參考mpi-inf.mpg.de 的頁面

當然，大數據下有很多的工具可以處理你的問題。或許你也發現了，這些方法可以回答你的問題，但是他們似乎沒有精確回答你的問題：這樣的抽象不是有「誤差」嘛？然而這就需要一個思想的轉變：在大數據下，確定性的思維或許需要調整。

我是學生，如果有說的不對，不嚴謹的地方，大家幫我指出來。

1 建立無向圖，連線表示有關係，點表示每個用戶。出於存儲空間節省的考慮，使用連接表。執行寬度優先搜索即可，或迭代加深搜索。

2 估計空間撐不住，如果提前存了各個用戶之間的關係，1kw * 1kw太大了

3 可以，參考spfa演算法吧，這個具體怎麼做還是要設計。

4 用有向圖應該可以了吧？

傳贏分析得很全面了，在純演算法上這個問題沒有難度了八（因為可以有很多近似方法，不需要實時計算，圈子結構微觀上幾乎是穩定的，否則就是姜粉哈哈）。挑戰在於工程上，微博提供類似功能的API每秒的調用次數可能是5000W/s，都要保證50ms的SLA，所以用redis實現了多級cache，再者地理/ISP上也是分布的，為了保證健壯性還有更多更多考慮。。我臆測下可能有70%的代碼是這方面的。。應該讓daoru和企盼說說這部分

QQ產品團隊解讀QQ圈子：打破社交頓巴數魔咒

".......只有大部分圈子成員對某一個圈子成員都使用嚴格相同的備註名，這個備註名才會被聚合出來。而且這個備註名也僅僅只展現給這個圈子中的核心成員……"

1，既然是通過少部分核心節點鏈接的，那就用鏈表好了吧。

2，為了限制搜索量，將用戶預先按照來源（像人人那樣的學校？地區？單位？）排序好。