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

Днями вдалося провернути цікаву штуку. Для всіх груп Вконтакте з числом передплатників від 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 рядків і розрахунок виглядав так: виписуємо групи і користувачів, які в них складаються у дві колонки:
user group
3953835 10
2065169 100001643
2112714 100001643
...

Виходить файл ~9Гб, сортуємо його юниксовым сортом по другій колонці, дивимося, де складається Павло Дуров:
user group
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 хвилин.

Подібний підхід теоритечески можна використовувати в будь-задачі, де є дві пов'язані сутності: сайти і користувачі, запит і результати видачі, наприклад.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.