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

Question

＆quot; 6つの分離度を証明しようとするアプリケーションを考えています＆quot;ソーシャルネットワークの一部であるユーザーのセットを使用した理論。

これらの要素があります：

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

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

Answer 1

ソーシャルネットワーク内の2人の人物間の分離の程度を見つけることは、グラフ内の2つのポイント間の最短経路を見つける特殊なケースです。最も一般的なアプローチは Dijkstraのアルゴリズムですが、最短パスの問題。

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

Answer 2

追加の背景素材：

この問題を一般的に解決するには、1つのソーシャルネットワークに固有のWebスクレイピングやその他のアドホックな手法を避けたいと思います。代わりに、 XHTML Friends Network（XFN）を調べてください。これはrelを使用する方法です=＆quot;＆quot;そのハイパーリンクのターゲットとあなたとの関係を示すハイパーリンクの属性。また、 FOAF と呼ばれる、 RDF 。

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

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