"Kevin Bacon"の数値を計算する

Question

私はいくつかのことを試していて、Kevin Baconという数字を見つけようと考えていました。私はこの目的のためにソーシャルネットワークを考えることができるサイトのデータを持っています。議論の簡略化のためにFacebookだとふりましょう。私には人がいて、友人のリストがあるので、私はそれらの間に関係があります。一人から他の人までの距離を計算するにはどうすればよいですか（基本的には、ケビンベーコンの数）？

私のベスト・アイデアは、（計算の複雑さを制限し、グラフに接続できない人の問題を避けるために）深さの制限があるBidirectional searchですが、これはむしろ力強いことです。

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

また、個人が接続されている人の数を事前に計算して、「人気のある」人々を最初に検索することもできます。私はこれが可能な最短経路のスピードのトレードオフになることを理解しています。私は、他の場合に使う予定の幅優先検索の代わりに深さ優先の検索を使いたいと思うでしょう。

誰かがこれを行うためのより簡単で速い方法を考えることができますか？私は2人の間で最短の長さを見つけられるようにしたいので、いつも同じエンドポイント（ケビンベーコン問題など）を持つのは簡単ではありません。

私は200人などの鎖を得ることができるような問題があることを認識していますが、それは私が検索したいと思う深さに限界があることを解決することができます。

Answer 1

これは標準shortest path problemです。 Dijkstra's algorithmとBellman-Fordを含む多くのソリューションがあります。具体的には、A* algorithmを見て、特定のノードの次数の逆数に対するコスト関数でどのように実行されるかを見てみることができます。より一般的なノード（より高い程度のノード）を最初に訪問することが考えられます。

Answer 2

Dijkstra's algorithmのような音がします。

ED：私はトリガーを非常に速く引いてはいけません。 Dijkstra（とBellman-Ford）は、ウェイトが1のときに幅優先探索になりますので、あまり役に立ちません。しかたがない。

tvanfossonに記載されているA* algorithmがこれに最適です。アイデアは、要素がツリーの各レベル（開始点または終了点に根ざしています）に何らかの順序で検索および再帰するのではなく、最初に試行する要素を判断するヒューリスティックを使用することです。あなたのケースでは、おそらくノードの程度（「友人」の数）が良い賭けになるかもしれませんが、任意の人の任意の数の範囲内の人の数を使用したいと思うかもしれません（つまり、それぞれが100人の友人を持っている3人の友人が、外部者を避けるクリークに20人の友人を持つ人よりも良いノードになる可能性が高い）。ヒューリスティック（友人は2ポイント、友人は1ポイント、それは何でも、実験）として使うことができる他のあらゆるものがあります。

これを深さ制限と組み合わせる（6度の分離後に切り捨てるなど）、平均ケースを大幅に改善できます（最悪の場合は基本BFSと同じです）。

Answer 3

は（各エンドポイントからの）両方向の幅優先探索を実行し、接続を持っているか、あなたの深さの上限は、この1つは、すべてのペアの最短距離Floyd-Warshall全体的に良いかもしれない

Answer 4

に達したときに停止します。