社交網絡圖是如何實現的？鄰接列表或鄰接矩陣

Question

具體來說，我的問題是Facebook這樣的社交網絡如何實現他們的關係圖。

由於查詢關係有很多操作，鄰接矩陣是一個好主意。但是，隨着新人的記錄，這張圖日漸增長。所以鄰接矩陣會導致很多空間浪費。

Answer 1

我有和你一樣的問題。我發現的幾乎所有資源都表示它取決於圖的「密度」。使用稀疏圖的鄰接表，稠密圖的鄰接矩陣。據wikipedia，無向簡單圖的密度是：

2*|E|/|V| * (|V|-1) 

從小集Facebook的數據，我得到的，密度0.008左右是比較稀疏，我猜。所以也許鄰接列表在Facebook等社交網絡中更好（無向圖）。