手元にあるデータ-VKontakteを使用して、この理論を自分で確認したかったのです。 私の奇妙な考えを人生に変換するためには、さまざまな問題を解決する必要がありました。
- すべてのデータに依存します。
- このデータを取得する場所。
- このデータを保存する方法。
- 計算に使用するアルゴリズム。
現代生活におけるソーシャルネットワークの優位性により、ソーシャルコネクションに関するデータをどこで取得するかという問題はそれほど難しくありません。 もちろん、Facebookから友達に関するデータを取得するのは良いことです。なぜなら、Facebookは世界中を網羅しており、そこには多くの人がいるからです。 ただし、公開APIを使用して誰の友達リストも引き出すことはできません。ページを解析することは最も効果的なオプションではありません。Facebookはdhtmlの形式で友達リストを吐き出します。 = 52 Tbのトラフィック。 このような少量のトラフィックは、ゼロになりがちな研究予算に収まらず、Facebookオプションは捨てられました。
私の視線はVKで修正されました。 はい、それはロシアとCISのみを対象としています（そして、不均等-クラスメート、例えば年配の聴衆）。 はい、膨大な数のボットがあります。 VKontakteは完璧ではありませんが、al_friends.phpへのリクエストを介してjson形式で友人のリストを配布できます。
しかし、このデータを保存および処理する方法は？
- 真っ向から直接MySQLに書き込むことができます。クモは毎秒100人のユーザーを吐き出し、それぞれに130人の友人がいて、毎秒13,000のデータベース挿入があります。 この数字は法外なものではありませんが、クモが弱いサーバー（古いシングルコアatlon）で動作していたという事実を考えると、完全にバラ色ではありません。
- テキストダンプをディスクに書き込んでから、データベースに吸い込むことができます。 この状況では、ベースの重量はおよそ（4バイト（user_idフィールドのサイズ）+ 4バイト（friend_idフィールドのサイズ）+オーバーヘッドとインデックス用の8バイト）* VKontakteの80Mユーザー* 130フレンド= 166GBです。 多すぎます。 さらに、このようなデータベースからのすべてのユーザーの友人の選択は、非常に効率的なクエリのようには見えません。
- MySQLにハンマーをかけて、ハッシュ値ストレージを使用できます。 「user_id配列（friend_id friend_id ...）」のペアをそれに書き込むには、このようなマクロでベースが4回吹き飛ばされ、すべての友人がディスクへの1回のアクセスで選択されます。 当初、Kyoto Cabinetはストレージとして選択されましたが、大規模なベースでの奇妙なパフォーマンス異常のため、Google LevelDBに移行しました。
3日半のトラフィックの後、友人データベースが受信されました（ところで、わずか22GB）。 そして、ここで最も興味深い質問が発生します：ユーザー間の距離を計算する方法？
- Floyd-Warshallアルゴリズムを使用すると、すべてのユーザーからすべてのユーザーまでの距離を計算できます。 素晴らしいアルゴリズムですが、不快なメモリ要件があります-1バイト* 80Mユーザー* 80Mユーザー= 6400 Tbを占める正方行列user_id / user_idを保存する必要があります。 多すぎる。
- ダイクストラのアルゴリズムでは、あるユーザーから他のすべてのユーザーまでの距離を一度に見つけることができます。 かなり効果的な実装がいくつかあり、そのうちの1つは実験のために使用されました。 アルゴリズムは、ベース全体の1％の合成サンプルで素晴らしく機能しましたが、平均10％で開始すると、ベースのサンプルはかなり予期しない場所でひどくブレーキをかけ始めました-友人の大きなツリーをバイパスすることは、メモリのランダムな場所に絶えず登り、すでに弱いプロセッサーのほぼ100％CACHE_MISSをキャッチしました。 人間的には、データはプロセッサキャッシュに収まらず、魅力的なブレーキが始まりました。
- 双方向検索 。 はい、世界で最もエレガントなアルゴリズムではありませんが、乗算表のように単純です。 2人のユーザー間の最短距離を見つけることができます。 その実装は、プロセッサキャッシュにエレガントに押し込まれたビットフィールドを使用して記述されました。その結果、アルゴリズムは30分で2人の距離を見つけました。
リソースを大量に消費するタスクを解決するとき、私は控えめなネットブックでも問題なく動作し、重い砲を搭載するような実装を作成するのが好きです。 重火器として、2つの6コアX5650 xeonと32GBのメモリを備えた控えめなサーバーが使用されました。 その上で、距離はストリームごとに10秒ですでに考慮されました。 並列化を考慮して、144ユーザーペア間の距離が毎分計算されました。
それから、データで奇妙さを始めました。 ゼロ以外の数の友人を持つすべてのユーザーのほぼ50％は、外部リンク（または、クラスター全体で1つ半のリンク）のない完全に独立したクラスターに属していました。 大ざっぱに言えば、50人が互いにフレームを組み、他の誰もいなかった。 かなり奇妙な動作ではありませんか？ はい、おそらくセクタリア人であり、宗教は宗派の非メンバーであるVKontakteを友人にすることを禁じています。 しかし、ほとんどの場合、これらはボットです。
同様の予期せぬ方法でキャッチされたボットを捨てて、6773のユーザーペアが分析され、非常に興味深い結果が得られました。
ヒストグラムのx軸に沿って、見つかった最短の友人チェーンの長さがあり、 y軸に沿って、それが見つかる確率がパーセントで示されます。
したがって、 平均して、2人のランダムなVKontakteユーザーの間には5.65人の友人 （6.65人のハンドシェイク） がいます 。 この図は、最初にテストされた理論によく適合し、さらに、Microsoftで得られた結果と完全に一致します（6.6になりました）。 したがって、結果は、6つのハンドシェイクの理論のもう1つの確認と見なすことができます。