先日、私はなんとか面白いことを始めました。 サブスクライバー数が5,000〜10,000（〜100,000グループ）のすべてのVkontakteグループについて、エッジの重みがグループオーディエンスの交差に等しい完全なグラフが構築されました。
まず、このようなグラフは美しく見えます：
次に、その助けを借りて、特定のトピックのグループをすばやく選択できます。 たとえば、編み物に関するグループを見つける必要があります。 キーワード "knitting"により、たとえば
Knitting -Knitting online-という適切なグループが見つかります。 関連付けられているグループを表示します。
編み物-オンラインで編み物-：
6.04％
ヤーン株式会社5.90％
Mommy’s Channel-
クリエイティブな母親向け（HOOK！）3.40％
ニット。 この世界では、すべてが接続されています...））3.01％
糸安い、フリース、編みブレスレット用のゴム2.35％
糸スパゲッティスパゲッティ1.87％
糸屋Eestilõng（カウニ、カウニ）1.73％
*かぎ針編みのアート*1.70％
カウニ糸はエストニアの伝説です。 編み物。1.66％
「レースモチーフ」-編み物と裁縫1.54％
トルコ糸の在庫品および注文品（ウクライナ）そして、疲れるまで、または新しい名前が表示されなくなるまで繰り返します。
編み物。 この世界では、すべてが接続されています...：
8.88％
ヤーン株式会社
3.06％
Mommy’s Channel-クリエイティブなママ向け（HOOK！）2.58％
糸安い、フリース、編みブレスレット用ゴム2.30％
編み物-オンライン編み物-2.14％
糸オンラインストア「透かし彫り」1.94％
カウニ糸はエストニアの伝説です。 編み物。1.85％
糸ストア-ღあなたの糸ღ1.76％
糸1.72％
透かし彫りの世界：愛とつながる！1.55％
糸屋Eestilõng（カウニ、カウニ）ヤーン株式会社：
7.54％
ニット。 この世界では、すべてが接続されています...））4.01％
Mommy’s Channel-クリエイティブなママ向け（HOOK！）3.47％
編み物-オンライン編み物-3.20％
糸安い、フリース、編みブレスレット用ゴム2.72％
糸オンラインストア「透かし彫り」2.67％
糸2.11％
「マダム・ビャザルキナ」糸（裁縫用グッズ）2.00％
カウニ糸はエストニアの伝説です。 編み物。1.85％
糸屋Eestilõng（カウニ、カウニ）1.82％
糸スパゲッティスパゲッティ「Madame Vyazalkina」糸（裁縫用グッズ）：
2.49％
糸2.37％
ヤーン株式会社1.42％
糸屋Eestilõng（カウニ、カウニ）1.39％
カウニ糸はエストニアの伝説です。 編み物。1.32％
糸安い、フリース、編みブレスレット用のゴム1.26％
糸と裁縫店1.24％
ニット帽など。1.21％
ホビー＆ホーム| 針仕事1.18％
Yarn Online Store "Openwork"1.15％
糸スパゲッティスパゲッティ同様の結果は、検索用のキーワード「編み物」、「糸」、「針仕事」、「かぎ針編み」を正しく選択することで実現できます。 しかし、それらは常に簡単に思いつくとは限りません。
このようなグラフを作成するために、いくつかの非自明な技術的ソリューションが使用されました。
特定のサイズのグループの完全なリストを取得するために、素晴らしいサイト
allsocial.ruがアップロードされました 。 彼らはこのデータをどのように収集するのだろうか？ 彼らはすべてのインデックスを通過します：
vk.com/club1、vk.com/club2 、...？ 5,000人から10,000人の加入者数を持つ中規模グループのみが、2つの理由で引き受けられました：MDKのような大衆がポンプをかけようとしているが、さらに重要なことには、それらのメンバーシップは特別な信号を運ばず、そのようなグループは世界中のすべてに接続されています。
VKontakteのIPAでグループサブスクライバーのリストを取得する特別な方法があります。 ただし、一度に1000人のユーザーを1秒間に3回しか受信できません。 そして、約10億人のユーザー、つまりdofigaを利用する必要がありました。 VKが各リクエストに即座に応答する場合、3〜4日間待つ必要があることがわかります。 これは一般に許容範囲ですが、ドキュメント内の次のコメントを混同します。
呼び出しの頻度の制限に加えて、同じメソッドの呼び出しには定量的な制限があります。 明らかな理由により、正確な制限に関する情報は提供していません。
私たちの場合、1,000,000件のリクエストを行う必要があるため、この発言は迷惑です。 ここで最もクールな
executeメソッドが役立ちます。 VKから来た人たちに対する彼の尊敬の念。 他の誰かがそのようなものを持っていますか？ 要するに、executeを使用すると、特殊言語VKScriptのプログラムをContactに送信し、そこにいくつかのAPIリクエストを詰め込み、場合によっては何らかのロジックを詰め込めます。 私の場合、プログラムは次のようになりました。
return [ API.groups.getMembers(id=1, offset=0, count=1000), API.groups.getMembers(id=1, offset=1000, count=1000), API.groups.getMembers(id=1, offset=2000, count=1000), API.groups.getMembers(id=1, offset=3000, count=1000), API.groups.getMembers(id=1, offset=4000, count=1000), API.groups.getMembers(id=1, offset=5000, count=1000), ... ];
プログラム内では、25を超えるAPI呼び出しを行うことはできません。 つまり、リクエストの数は40,000に削減され、理論的には禁止は通過できます。 そのようなリクエストはすぐには実行されなくなりましたが、約5〜6秒でしたので、私はまだ待たなければなりませんでした。 はい、いくつかのストリームでダウンロードを開始することは可能ですが、それでも愚かでした。 2日半後、すべてがアップロードされ、ディスクに約10GBかかりました。
ここで、これらの10GBをRAMに詰め込む方法と、100,000グループのオーディエンスのペアワイズ交差を計算する方法の問題が発生します。 通常、各ユーザーが少数のグループで構成されているという事実が保存されます（ユーザーの99％は15未満のグループに属しています）。 各ユーザーが交差点で行った貢献を書き留めてから、これらの貢献を追加できます。 たとえば、AとB、および3つのグループ1、2と3の2人のユーザーがいるとします。Aは3つすべてで構成され、Bは1と3のみです。Aは3つの交差点に貢献します：（1、2）、（1 、3）および（2、3）、B-1つに：（1、3）。 さらに、1と3が2人のユーザーで交差し、残りのグループは1人ずつ交差することを取得します。 技術的に15グループ以上のユーザーを無視する場合、約500,000,000の交差点を書き出す必要があります。これは、額で解くよりもはるかに優れており、100,000 * 100,000の交差点を計算する必要があります。
すばらしい、RAMに問題があるだけでした。 幸いなことに、説明したアルゴリズムはマップリデューサーのパラダイムによく適合しているため、50行の
ナノフックが切断され、計算は次のようになりました。2つの列で構成されるグループとユーザーを記述します。
group user 3953835 10 2065169 100001643 2112714 100001643 ...
ファイルは約9GBであることがわかりました。2列目のUnixソートでソートしました。PavelDurovの位置を確認してください。
group user 2226515 1 37110020 1 38354466 1 43453499 1 60140141 1 60615047 1 64980878 1 1019652 10 ...
ファイルを読み取り、2番目の列でストリームをグループ化し、ユーザーグループのリストのみを保持するメモリに保存します。グループが15未満の場合は、一致するすべてを別のファイルに書き出します。
source target 10000 10027193 9980615 9997141 9974 9976553 ...
しきい値が正しく選択されているため、ファイルは大きすぎません-〜9GB。 2つの列に並べ替えます。
source target 10000 100000 10000 100000 10000 10009982 10000 100100 10000 100100 10000 10019194 10000 10019194 10000 1002 10000 1002 10000 1002 ...
次に、ファイルが読み取られ、2つの列にグループ化され、交差点がすぐに考慮されます。 たとえば、グループ10,000および100,000の場合、2人のユーザーをリストします。 これはすぐに言うことができ、何もメモリに保存する必要はありません。
さらに、いくつかの合理的なしきい値に従ってrib骨がフィルタリングされるため、それらの多くは残っていません。 結果はGefiで表示できます。 2つの秘密があります：すべてが痛みなく長く動作しないためには、エッジの描画をオフにする必要があります、スタイリングのためにOpenOrdをダウンロードする必要があります、彼は〜5分で〜100,000頂点に私のグラフを積み上げました。
理論的には、たとえばサイトとユーザー、クエリと発行結果という2つの関連エンティティがあるタスクで同様のアプローチを使用できます。