2人のユーザー間の社会的距離を計算する

Question

2人のユーザー間でソーシャルな距離を返すことができる効率的なアルゴリズムをコーディングする方法。

たとえば、LinkedInのプロファイルにアクセスすると、あなたとユーザーの距離を知ることができます。

- >ユーザAがユーザBとの友人である - とCを訪問するとき、BはCとの友人である

グラフが巨大であるので、私はどのようにそれができると思いまして（距離は1になります）とても速く実行してください。

私は、この質問は閉鎖される可能性があることを知っていますが、実際にはプログラミング/アルゴリズムの問​​題だと思っています - 私はその概念に興味があるので、

Answer 1

あなたは目標物までの距離についてのheuristic functionを持っていないと仮定すると、有効で最善の解決策はbi-directionalBFSです：
アルゴリズムのアイデア：ソースとターゲットから同時にBFSの検索を実行します。[BFS両方の深さ1まで、両方の深さ2まで、....]。
BFSの前面にある頂点vを見つけると、アルゴリズムは終了します。

アルゴリズムの振る舞い：アルゴリズムの実行を終了する頂点vは、ソースとターゲットの間の真中にあります。
このアルゴリズムは、ほとんどの場合、ソースからのBFSよりもはるかに優れた結果をもたらします[なぜそれがBFSの方が優れているか説明]、存在する場合は確かに回答を提供します。

ソースからのBFSの方が良い理由は何ですか？
ソースからターゲットまでの距離をkとし、分岐係数をB [すべての頂点にBエッジがある]とします。
BFSが開きます：1 + B + B^2 + ... + B^k頂点。
双方向BFSが開きます：2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2)頂点。

大きなBとkでは、2番目の方が明らかに最初の方がずっと優れています。

EDIT：内、successor(v)頂点のすべての後継[あなたが得ることができるすべての頂点を返します。
NOTEは、このソリューションは、メモリ内のグラフ全体を保存する必要がないこと、それが唯一の機能を実装する必要がありvから1ステップ]。これで、あなたが開いたノード[上記で説明したような2 + 2B + ... + 2B^(k/2)]だけを保存する必要があります。さらにメモリを節約するには、BFSの代わりにIterative Deepening DFSを一方向から使用できますが、時間がかかります。

Answer 2

breadth first searchのような最短パスアルゴリズムをgraph databaseに適用すると仮定します。しかし、彼らは少なくともthisに従って、グラフ全体をメモリに保存するように見えます。

私はアルゴリズムが最終的にグラフ構造（ノードとエッジ）上に最短経路1の形になっていると確信しています。

編集：コメントごとにアルゴリズムを変更しました。

Answer 3

最初に、グラフを作成する必要があります。おそらくノードのBFSやDFSを作って、グラフを発見し、リンクを確立するという方法で、グラフをリンクさせる方法については言えません。いずれか2つの間の距離を見つけるには、送信元ノードからBFSを作成し、宛先が見つかると停止します。あなたが他の何かを暗示しないなら、リンクは重みを持っていない、と私は思う。

この場合、送信元ノードが異なる場合は、各ペア間の距離を見つけるためにそれぞれBFSを適用する必要があります。そうでなければ、Floyd Warshallアルゴリズムを実装して、すべての送信先の最短経路をすべて取得することができます。また、各リンクの重みが同じであるため、必要なものが得られます。この場合、一度構造が作られると、任意のソースとデスティネーションについて、最短距離を見つけることができます。 1つの問題は、ネットワークが常に変化しているため、再処理が必要であるということです。したがって、BFSは良いと思います。

処理を高速化するために、BFSを実装して並列実行することができます。ご覧くださいDesign and analysis of a nondeterministic parallel breadth-first search algorithm