algorithm - 友情関係追跡アルゴリズム

Question

ソーシャル ネットワークの一部である一連のユーザーを使用して、「 6 段階の分離」理論を証明しようとするアプリケーションを考えています。

私はそれらの要素を持っています:

1. 6度理論を証明したい2人のユーザー
2. 各ユーザーについて、ソーシャル ネットワークの友達のリストを知っている

2 人のユーザーがどの程度接続されているかを確認し、接続の最終的な手順を表示するのに最適なアルゴリズムはどれですか?

Answer 1

ソーシャル ネットワークで 2 人の距離を見つけることは、グラフの 2 点間の最短経路を見つける特殊なケースにすぎません。最も一般的なアプローチはダイクストラのアルゴリズムですが、最短経路の問題についてのより長い説明も参照してください。

さらに、All-pairs 最短パス アルゴリズムを実行することで、ネットワーク全体の分離度の最小、最大、および平均数を見つけることができます。

Answer 2

いくつかの追加の背景資料:

この問題を一般的に解決するには、特定のソーシャル ネットワークに固有の Web スクレイピングやその他のアドホックな手法を避ける必要があります。 代わりに、ハイパーリンクの rel="" 属性を使用して、そのハイパーリンクのターゲットと自分との関係を示す方法であるXHTML Friends Network (XFN)を調べることをお勧めします。RDFを使用するFOAFと呼ばれる競合する標準もあります。

これらのマイクロフォーマットはしばらく前から存在していましたが、それらのサポートは最近になって大幅に増加しました。StackOverflow は、プロフィール ページのリンクで「me」を使用します。WordPress ブログは、ブログロールがこれらのタグを追加するための編集インターフェースで簡単な方法を提供します。多くのソーシャル サイトでは、友人間のリンクでこれらを使用して関係を示しています。

このため、Google はこれに関心を持ち、このデータのマイニングを開始しています。XFN と FOAF の両方のデータをマイニングして、やりたいことを正確に実行できるソーシャル グラフ APIがあります。そこから始めることをお勧めします。Google の API の良いところは、ウェブ全体でこれをマイニングしているため、考えていた特定のソーシャル ネットワークを超えて検索範囲を広げることができることです。