Поиск похожих групп и пабликов Вконтакте

На днях удалось провернуть интересную штуку. Для всех групп Вконтакте с числом подписчиков от 5000 до 10 000 (~100 000 групп) был построен полный граф, в котором веса рёбер равнялись пересечению аудиторий групп.

Во-первых, такой граф красиво выглядит:


Во-вторых, с его помощью можно быстро подбирать группы заданой тематики. Например, нужно найти группы про вязание. По ключевому слову «вязание» находим, одну подходящую группу, Knitting -Вязание online-, например. Выводим группы, с которыми она связана:

Knitting -Вязание online-:
6.04% Корпорация «ПРЯЖА»
5.90% Мамочкин канал — для творческих мам (КРЮЧКОМ!)
3.40% Вязание. В этом мире всё связано...))
3.01% ПРЯЖА ДЁШЕВО.ФЛИС.РЕЗИНКИ ДЛЯ ПЛЕТЕНИЯ БРАСЛЕТОВ
2.35% Пряжа Spagetti Спагетти
1.87% Магазинчик пряжи Eesti l?ng (Kauni, Кауни)
1.73% *Искусство вязания крючком*
1.70% Пряжа Кауни (Kauni) — легенда Эстонии. Вязание.
1.66% «Кружевные мотивы» — вязание и рукоделие
1.54% Пряжа турецкая в наличии и на заказ(Украина)

И повторяем пока не надоест или пока не перестанут появляться новые названия.

Вязание. В этом мире всё связано...:
8.88% Корпорация «ПРЯЖА»
3.06% Мамочкин канал — для творческих мам (КРЮЧКОМ!)
2.58% ПРЯЖА ДЁШЕВО.ФЛИС.РЕЗИНКИ ДЛЯ ПЛЕТЕНИЯ БРАСЛЕТОВ
2.30% Knitting -Вязание online-
2.14% Интернет-Магазин Пряжи «АЖУР»
1.94% Пряжа Кауни (Kauni) — легенда Эстонии. Вязание.
1.85% Магазин пряжи — ? ВАША ПРЯЖА ?
1.76% Пряжа
1.72% Ажурный мир: связано с любовью!
1.55% Магазинчик пряжи Eesti l?ng (Kauni, Кауни)

Корпорация «ПРЯЖА»:
7.54% Вязание. В этом мире всё связано...))
4.01% Мамочкин канал — для творческих мам (КРЮЧКОМ!)
3.47% Knitting -Вязание online-
3.20% ПРЯЖА ДЁШЕВО.ФЛИС.РЕЗИНКИ ДЛЯ ПЛЕТЕНИЯ БРАСЛЕТОВ
2.72% Интернет-Магазин Пряжи «АЖУР»
2.67% Пряжа
2.11% «Мадам Вязалкина» Пряжа (товары для рукоделия)
2.00% Пряжа Кауни (Kauni) — легенда Эстонии. Вязание.
1.85% Магазинчик пряжи Eesti l?ng (Kauni, Кауни)
1.82% Пряжа Spagetti Спагетти

«Мадам Вязалкина» Пряжа (товары для рукоделия):
2.49% Пряжа
2.37% Корпорация «ПРЯЖА»
1.42% Магазинчик пряжи Eesti l?ng (Kauni, Кауни)
1.39% Пряжа Кауни (Kauni) — легенда Эстонии. Вязание.
1.32% ПРЯЖА ДЁШЕВО.ФЛИС.РЕЗИНКИ ДЛЯ ПЛЕТЕНИЯ БРАСЛЕТОВ
1.26% Магазин пряжи и товаров для рукоделия КУДЕЛЬ
1.24% Вязаные головные уборы и не только.
1.21% HOBBY & HOME | РУКОДЕЛИЕ
1.18% Интернет-Магазин Пряжи «АЖУР»
1.15% Пряжа Spagetti Спагетти

Аналогичного результата можно добиться грамотно подобрав ключевые слова для поиска: «вязание», «пряжа», «рукоделие», «крючком». Но их не всегда просто придумать.

Чтобы построить такой граф было использовано несколько неочевидных технических решений, о которых я хотел бы рассказать.

Чтобы получить полный список групп заданного размера, был прокачан прекрасный сайт allsocial.ru. Интересно как они собирают эти данные? Просто идут по всем индексам: vk.com/club1, vk.com/club2, ...? Брались только средние группы с числом подписчиков от 5000 до 10 000 человек по двум причинам: огромные паблики типа МДК чёкнешься прокачивать, но, что важнее, членство в них не несёт особенного сигнала, такие группы связаны со всем на свете.

Чтобы получить список подписчиков групп в АПИ Вконтакта, есть специальный метод. Но он позволяет получать по 1000 пользователей за раз и только 3 раза за секунду. А прокачать надо было порядка 1 000 000 000 пользователей, что дофига. Получается, что надо будет ждать 3-4 суток, если ВК будет отвечать на каждый запрос мгновенно. Это, в целом, терпимо, но смущало следующее замечание в документации:

Помимо ограничений на частоту обращений, существуют и количественные ограничения на вызов однотипных методов. По понятным причинам, мы не предоставляем информацию о точных лимитах.

В нашем случае, это замечание напрягает, потому что нужно будет сделать 1 000 000 запросов. На помощь здесь приходит крутейший метод execute. Большой респект за него ребятам из ВК. Интересно у кого-нибудь ещё есть такая штука? Суть в том, что через execute можно посылать в Контакт программы на специальном языке VKScript, запихивать туда несколько запросов к АПИ и, возможно, какую-то логику. В моём случае программа выглядела примерно так:

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 обращений к АПИ. То есть число запросов сокращается до 40 000, теоретически бан может миновать. Каждый такой запрос выполнялся уже совсем не мгновенно, а примерно 5-6 секунд, поэтому подождать всё равно пришлось. Да, можно было бы запустить скачивание в несколько потоков, но чёт было стрёмно. Через два с половиной дня всё докачалось и заняло примерно 10Гб у меня на диске.

Теперь встаёт вопрос как запихнуть эти 10Гб в оперативную память и как посчитать попарное пересечение аудиторий для 100 000 групп. Спасает тот факт, что каждый пользователь состоит обычно в небольшом количестве групп (99% пользователей состоят менее чем в 15 группах). Можно выписать какие вклады вносит в пересечения каждый пользователь и потом эти вклады сложить. Пускай, например, есть два пользователя: А и Б, и три группы 1, 2 и 3. А состоит во всех трёх, Б — только в 1 и 3. А вносит вклады в три пересечения: (1, 2), (1, 3) и (2, 3), Б — в одно: (1, 3). Складываем, получаем, что 1 и 3 пересекаются по двум пользователя, остальные группы по одному. Если технично проигнорировать пользователей, которые состоят в 15 группах и больше, то придётся выписать примерно 500 000 000 пересечений, что гораздо лучше, чем при решении в лоб, где нужно будет посчитать 100 000 * 100 000 пересений.

Прекрасно, осталась только проблема с оперативной памятью. К счастью, описанный алгоритм хорошо ложится на парадигму мап-редьюс, поэтому был запилен нано-хадуп на 50 строчек и расчёт выглядел так: выписываем группы и пользователей, которые в них состоят в две колонки:

group	user 3953835	10 2065169	100001643 2112714	100001643 ... 

Получается файл на ~9Гб, сортируем его юниксовым сортом по второй колонке, смотрим, где состоит Павел Дуров:

group	user 2226515	1 37110020	1 38354466	1 43453499	1 60140141	1 60615047	1 64980878	1 1019652	10 ... 

Читаем файл, группируем поток по второй колонке, в памяти держим только список групп пользователя, если групп меньше 15, выписываем все паросочетания в ещё один файл:

source	target 10000	10027193 9980615	9997141 9974	9976553 ... 

Так как порог подобран грамотно, файл получается не слишком большой — ~9Гб. Сортируем его по двум колонкам:

source	target 10000	100000 10000	100000 10000	10009982 10000	100100 10000	100100 10000	10019194 10000	10019194 10000	1002 10000	1002 10000	1002 ... 

Дальше файл читается, группируется по двум колонкам и сразу считается пересечение. Для групп 10000 и 100000, например, перечение 2 пользователя. Это можно сказать сразу, ничего хранить в памяти не надо.

Дальше рёбра фильтруются по какому-нибудь разумному порогу, чтобы их осталось не очень много. Результат можно посмотреть в Гефи. Есть два секрета: чтобы все работало не мучительно долго нужно отключить рисование рёбер, для укладки нужно скачать OpenOrd, он уложил мой граф на ~100 000 вершин за ~5 минут.

Подобный подход теоретически можно использовать в любой задаче, где есть две связанные сущности: сайты и пользователи, запрос и результаты выдачи, например.