ソーシャルネットワークグラフはどのように実装されていますか？隣接リストや隣接行列

Question

具体的には、私の質問はFacebookのようなソーシャルネットワークがどのように関係グラフを実装するのかということです。

クエリ関係には多くの操作があるので、隣接行列が良い考えです。しかし、新しい人が口座を開けるにつれて、グラフは毎日急速に成長しています。そのため、隣接行列は多くの空間を無駄にする可能性があります。

Answer 1

私はあなたと同じ質問をしました。私が見つけたほとんどすべてのリソースは、グラフの「密度」に依存していると言いました。密なグラフの隣接関係リストを使用して、密なグラフの隣接行列を作成します。 wikipediaによると、無向簡単なグラフの密度は次のとおりです。

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

私が得たFacebookのデータの小さなセットから、密度は私が推測する比較的疎である約0.008です。だから、多分隣接関係のリストは、Facebook（無向グラフ）のようなソーシャルネットワークで優れています。