社交网络图是如何实现的？邻接列表或邻接矩阵

Question

具体来说，我的问题是Facebook这样的社交网络如何实现他们的关系图。

由于查询关系有很多操作，邻接矩阵是一个好主意。但是，随着新人的记录，这张图日渐增长。所以邻接矩阵会导致很多空间浪费。

Answer 1

我有和你一样的问题。我发现的几乎所有资源都表示它取决于图的“密度”。使用稀疏图的邻接表，稠密图的邻接矩阵。据wikipedia，无向简单图的密度是：

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

从小集Facebook的数据，我得到的，密度0.008左右是比较稀疏，我猜。所以也许邻接列表在Facebook等社交网络中更好（无向图）。