「6つの分離度」概念をプログラムで証明するにはどうすればよいですか？

私は2000万人のユーザーとその人のつながりのデータベースを持っています。どのように私は "6度の分離"概念の概念を証明することができます最も効率的な方法でプログラミングの？「6つの分離度」概念をプログラムで証明するにはどうすればよいですか？

は、あなただけのこのグラフで最も遠くに接続されたノード間の別離を見つけるために、正確に計量されdiameter of the graph. を測定したいです。

Googleでのアルゴリズムはたくさんありますが、Boost graphもあります。

2009-06-12 20:41:38 SPWorley

6度は最大か平均か？私が読んだ実際の分析のほとんどは、最大値ではなく平均値を使用しています。 –

"6度の分離"という共通の概念は最大であるということです。もちろん、実際にはそうではありません。そのように言うと反例を見つけるのは難しいです。 –

おそらくグラフをメモリに入れることができます（各頂点がその隣人のリストを知っているという表現で）。

次に、各頂点nから、深さ6までの幅優先探索（キューを使用）と訪問した頂点の数をカウントすることができます。すべての頂点が訪問されていない場合、あなたは定理を反証しています。それ以外の場合は、次の頂点nに進みます。

ユーザが平均100接続を持つ場合、これはO（N *（N + #edges））= N *（N + N * 100）= 100N^2です。私は、上記のライブラリがより良い時間複雑さ（一般的なアルゴリズムはO（N^3））で直径を計算できるのだろうかと思います。

個々の頂点の計算は独立しているため、並列で実行できます。

少しヒューリスティック：最も低い次数を持つ頂点から始めます（定理を反証する可能性が高くなります）。

2009-06-12 21:14:38

これはO（n^2）よりもかなり悪いと思います。各ノードが3つの他のノードに接続されていると仮定しても、深さ6のスタックトレースは3 * 2^0 + 3 * 2^1 + 3 * 2^2 + 3 * 2^3 + 3 * 2^4 + 3 * 2^5。指数関数的成長 – patros

各頂点については、各頂点をたかだか1回しか訪問しないため、1つの頂点の実行にはO（N）が必要です。 –

ああ、それは限界です。私はこれがまだO（N^3）だと思いますが、そうではありませんか？頂点Aから頂点Bまでのパスを見つけることはO（N）であり、このO（N^2）回行う必要があります。 – patros

最も効率的な方法（最悪の場合）はほぼN^3だと思います。隣接行列を構築し、その行列^ 2、^ 3、^ 4、^ 5、^ 6を取ります。グラフ中の行列から行列^ 6までの0のエントリを探します。

経験則的に、サブグラフ（比較的少数の「ブリッジ」ノードによって他のクランプにのみ接続されている人の大きな塊）を単一のものにしようとすることはできますが、絶対に保証するものはありません。

2009-06-12 21:30:07 patros

メモリに20x20 millionのサイズの隣接行列を構築することはできません。また、乗算はO（N^3）であり、Nは2000万である。 –

strassenのアルゴリズムでは、正方形の行列なので、おおよそn^2.8です。あなたは積極的に乗算している部分だけを記憶に残す必要はありません。残りの部分をディスクに貼り付けます。 – patros

純粋なアプローチのためには400TBですが、多くのディスクが必要です。しかし、圧縮のための部屋の多く。 – patros

もう少し良い答えが出ましたが、私の頭の上から私はFloyd-Warshallすべてのペアの最短経路アルゴリズムO（n^3）に行きました。私はグラフの直径アルゴリズムの複雑さを確信していますが、これはO（n^3）のような "音"です。もし誰かが知っていれば、私はこれについて明確にしたいと思います。

このようなデータベースが実際にありますか？恐ろしい。

2009-06-15 10:18:59

答えて