私は 2,000 万人のユーザーのデータベースとそれらの人々の間のつながりを持っています。プログラミングで 最も効率的な方法で「6度の分離」の概念を証明するにはどうすればよいですか?
4297 次
4 に答える
4
おそらく、グラフをメモリに収めることができます (各頂点がその近傍のリストを知っているという表現で)。
次に、各頂点nから、(キューを使用して) 深さ 6 まで幅優先検索を実行し、アクセスした頂点の数をカウントできます。すべての頂点が訪問されていない場合は、定理が反証されたことになります。それ以外の場合は、次の頂点nに進みます。
これは O(N*(N + #edges)) = N*(N + N*100) = 100N^2 であり、ユーザーが平均で 100 の接続を持っている場合、これは N=2000 万には理想的ではありません。上記のライブラリがより良い時間複雑度で直径を計算できるかどうか疑問に思います (一般的なアルゴリズムは O(N^3) です)。
個々の頂点の計算は独立しているため、並行して実行できます。
少しヒューリスティック: 最も低い次数を持つ頂点から始めます (定理を反証する可能性が高くなります)。
于 2009-06-12T21:14:38.703 に答える
2
より良い答えは既に与えられていますが、頭のてっぺんから、O(n^3)であるFloyd-Warshallの全ペア最短パス アルゴリズムを使用していたでしょう。グラフの直径アルゴリズムの複雑さはわかりませんが、これも O(n^3) のように「聞こえます」。誰かが知っているなら、私はこれについて説明したいと思います。
余談ですが、本当にそのようなデータベースを持っていますか? 怖い。
于 2009-06-15T10:18:59.780 に答える
2
最も効率的な方法 (最悪の場合) はほぼ N^3 だと思います。隣接行列を作成し、その行列 ^2、^3、^4、^5、および ^6 を取得します。マトリックスからマトリックス ^6 までの 0 であるグラフ内のエントリを探します。
ヒューリスティックに、サブグラフ (比較的少数の「ブリッジ」ノードによって他の塊にのみ接続されている人々の大きな塊) を選び出すことを試みることができますが、それがあるという保証は絶対にありません。
于 2009-06-12T21:30:07.433 に答える