11

私はいくつかのことをいじっていて、 Kevin Baconの数を理解しようとするアイデアを思いつきました。この目的のためにソーシャルネットワークと見なすことができるサイトのデータがあります。Facebook だとしましょう (議論を簡単にするため)。私には人々がいて、彼らの友達のリストを持っているので、彼らの間のつながりがあります。ある人から別の人への距離 (基本的には、ケビン ベーコン数) を計算するにはどうすればよいですか?

私の最善のアイデアは、深さ制限のある双方向検索です（計算の複雑さを制限し、グラフで接続できない人々の問題を回避するため）が、これはかなり力ずくであることに気付きました。

小さなサブグラフ (Facebook のグループに相当するようなもの) を作成し、それらの間の最短距離を (おそらく前もって) 計算してから、THOSE を使用してリンクを見つけようとする方がよいでしょうか? これには事前計算が必要ですが、より少ないノードを検索できる可能性があります (ノードは個人ではなくグループである可能性があり、グラフがはるかに小さくなります)。ただし、これは依然として双方向検索になります。

また、特定の目的地の個人に接続する可能性が最も高い可能性があるため、最初に「人気のある」人々のノードを検索して、個人が接続している人の数を事前に計算することもできます。これは、可能な最短経路に対する速度のトレードオフになることを認識しています。他のケースで使用する予定の幅優先検索の代わりに、深さ優先検索も使用したいと思います。

誰かがこれを行うためのより簡単で高速な方法を考えられますか? 2 人の間の最短の長さを見つけられるようにしたいので、終点が常に同じであるほど簡単ではありません (Kevin Bacon の問題など)。

200人のチェーンを取得できるなどの問題があることは認識していますが、検索する深さに制限があるため、それは解決できます。

4

4 に答える 4

17

これは標準的な最短経路の問題です。Dijkstra のアルゴリズムやBellman-Fordなど、多くのソリューションがあります。A* アルゴリズムを調べて、特定のノードの次数の逆数に関連するコスト関数でどのように機能するかを確認することに特に関心があるかもしれません。アイデアは、より人気のあるノード (次数の高いノード) を最初に訪問することです。

于 2009-03-23T20:31:11.867 に答える
4

ダイクストラのアルゴリズムの仕事のように 聞こえます。

ED: ああ、そんなに早く引き金を引くべきじゃなかった。Dijkstra (および Bellman-Ford) は、重みが 1 の場合、幅優先検索に縮小されるため、これはあまり役に立ちません。しかたがない。

tvanfosson によって言及されたA* アルゴリズムは、これに最適な場合があります。アイデアは、要素がツリーの各レベル (開始点または終了点に根ざしている) にある順序で検索して再帰するのではなく、ヒューリスティックを使用して、最初に試行する要素を決定するというものです。あなたの場合、良い賭けはおそらくノードの程度（「友達」の数）ですが、特定の人（つまり、 3 人の友人がいて、それぞれに 100 人の友人がいる人は、部外者を避ける派閥で 20 人の友人を持つ人よりも優れたノードになる可能性があります)。ヒューリスティックとして使用できるものは他にもあります (友達は 2 ポイント、友達の友達は 1 ポイントを獲得します。なんでも実験してみてください)。

これを深さ制限 (6 度の分離後にカットオフするなど) と組み合わせると、平均的なケースを大幅に改善できます (最悪のケースでも基本的な BFS と同じです)。

于 2009-03-23T20:30:31.273 に答える
0

(各エンドポイントから) 両方向で幅優先検索を実行し、接続があるか、深さの制限に達したときに停止します

于 2009-03-23T20:32:52.143 に答える
0

こちらの方が全体的に良いかもしれませんが、フロイド・ワーズは全ペア最短距離です。

于 2009-03-23T20:37:38.013 に答える