インターネットマップ、またはサイト間のユーザーの移行に応じて35万サイト以上をクラスタリングした結果を紹介します。 円のサイズは、サイトのトラフィック、国籍による色、他のサイトへのリンクによる地図上の位置によって決まります。 2つのサイト間でユーザーの流れが安定している場合、それらのサイトは互いに近くに配置されるように「試行」されます。 アルゴリズムの完了後、マップ上で、一般ユーザーが団結したサイトのクラスター（クラスター）を観察できます。
たとえば、検索にhabrahabr.ruを入力すると、dirty.ruとleprosorium.ruが同じ「星座」にあり、livejournal.ruが遠くにあることがわかります。 これは、このテキストを読んでいる人もこれらのサイトにアクセスする可能性が高いことを示唆しています（もちろん、平均的なRunetユーザーに関して）。
紫色の日本と黄色がかったブラジルの間にあるクラスターのさらに興味深い例は、マップの下部に見ることができます。ユーロネット全体に匹敵するサイズのポルノの国全体があります。 興味深いことに、検討中の問題について十分な能力を備えているため、小さなポルノサブクラスターは大きなポルノクラスター内で区別できます。
簡単な技術的な説明に興味がある人-カットへようこそ
エンジニアリング部
プロジェクト全体はC＃で記述されており、3つの部分で構成されています：クラスタリングプログラム、タイル生成プログラム、およびWebサイト。 各部分を個別に検討する必要があり、興味がある場合は、それらについて詳しく説明します。
初期データはAlexaから取得されたもので、出席の記録、ユーザーの上流と下流の遷移（上流-移動元、下流-移動先）です。 正規化後、350万の頂点と200万を超えるエッジを持つ重み付き無向グラフが得られます。
このようなグラフの計算は難しい計算タスクであるため、GPU用の特別なモジュールが作成されましたが、幸いなことにそれは必要ありませんでした。 トリッキーな最適化の後、計算全体に強力であるが依然として家庭用鉄の連続操作に数週間かかりました。
簡単に言うと、アルゴリズムは、サイトに作用する力に応じて、マップ上のサイトの段階的な動きで機能しました。 多くのユーザーの移行-強い力がサイトを近づけようとします。 サイトが近すぎる場合、反発力が働き始めます。 詳細については、この作業をご覧くださいreports-archive.adm.cs.cmu.edu/anon/1998/CMU-CS-98-189.pdf
主な問題は、このようなアルゴリズムの巨大な計算の複雑さでした。 実際、問題を「正面から」解決する場合、各ステップで各サイトの力の重ね合わせを計算する必要があります。 サイトの各ペアの強度を計算すると、そのようなペアは約1,220億あります（1ステップで悪くないでしょう？）。 したがって、アルゴリズムの厳密な最適化と計算の完全な並列化が実行されました。 幸いなことに、.netプラットフォームはこの種の楽しみに驚くほど優れていました。
2番目の段階は、タイルの生成です。 タイルとは、Googleマップ、yandex、その他のサービスでマップ画像を構成する256x256ピクセルの小さな画像です。 一般的に、複雑なことは何もありません-私は大きな画像を生成し、ビジネス、適切なサイズの正方形に切り取りました。 しかし、そのような写真は約3000万個あり、タイルがウィンドウにあるディレクトリをコピーまたは削除するだけでも2日かかります。 そして、それらをホスティングにアップロードすることは別の問題です。
3番目の段階は、Googleマップエンジンを固定し、すべてをまとめて地図を表示することです。 ここでは、一般に、地図の投影と位置決めには多少の困難がありましたが、複雑なことはありません。
最後の段階は、ホスティングとリリースの選択です。 ここも冒険なしではありませんでした。 今ではすべてがAmazonクラウドで回転しており、想像していたよりもはるかにシンプルで安価であることがわかりました。
一般的に、私はいくつかの経験を積んでおり、尊敬されるコミュニティと喜んで共有します。 もちろん、一般的には、特別なことは何もありません。Habréには本当に興味深いプロジェクトや重要なソリューションがありますが、それでも多くの人が興味を持っていると思います。
また、私はどんなアイデア、フィードバック、批判にも満足します-フィードバック！
優しい言葉をありがとうございました！ 私は、結果を見るだけでなく、それを達成するためにどれだけの作業が行われたかを理解している人々から、専門家コミュニティから支援を受けることが非常に重要でした。 また、HaNetのおかげで、RuNetには私たち全員を統合するプラットフォームがあります！
続き： Web Architecture Internet Maps