3 августа 2015 в 00:11

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

На днях удалось провернуть интересную штуку. Для всех групп Вконтакте с числом подписчиков от 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 минут.

Подобный подход теоретически можно использовать в любой задаче, где есть две связанные сущности: сайты и пользователи, запрос и результаты выдачи, например.
Кукушкин Александр @alexkuku
карма
154,0
рейтинг –1,6
Лаборатория анализа данных Кукушкина Александра
Похожие публикации
Самое читаемое Разработка

Комментарии (34)

  • –3
    На чем вы это делаете, какие технологии используете? Давно хочу разобраться с доступом к контакту как крупнейшей русскоязычной социальной сети. Обзорная/вводная статья (а лучше серия статей «по шагам») была бы очень кстати.
    Можно ли например провернуть такую штуку: взять список пользователей и список групп, пройтись по ним и найти все комментарии и все лайки пользователя с конкретным ID. Скорость пофиг, все в личных целях.
    • 0
      конечно можно
    • 0
      Я проворачивал это: поиск фото пользователя в альбомах групп в которых он состоит и поиск фото в комментариях написанным им в группах. Однако у меня все медленно искалось (не использовал трюки с распараллеливанием) делалось. Может кто реализует.
      • 0
        skotobaza.org
        На дваче эту идею озвучивали, мой друг его реализовал (php + mySQL). Быстро набрав популярность сервер не выдержал и упал (19 тыс пользователей за ночь, всё логгировалось, железо было самое простое). Через некоторое время пришло письмо на его личную почту (которую он нигде не публиковал) с просьбой закрыть сайт от админов группы 40 кг (или от других групп, не помню детали), с угрозой «наши юристы сделают с Вами плохо». Сразу после этого он выложил исходный код на двач и бросил это дело.
        Подхватили его друзья, быстро переписали на nodejs и запустили, я так полагаю, на зарубежных серверах.
        В свое время их блокировали РосРеестр, но позже их открыли.

        Есть даже его интервью, ссылку могу чуть позже скинуть
        • 0
          Интересно было бы почитать.
    • 0
      Возьмите любой язык программирования и делайте на нем. Описание АПИ и доступа к нему есть в самом ВК и очень даже подробные.
      Я выкладывал тут статью (теперь она на ММ), где к доступу к ВК использовал вообще 1С. Так что технологии не важны, был бы API:)
      • 0
        для таких вещей API не подходит, т.к. легко будет заблокировать все запросы
        • 0
          А через что вы это предлагаете решать?

          Насчет блокировки, автор статьи верно заметил про метод execute. Полностью не спасет, но значительно облегчит задачу — это точно.
  • +1
    На чем вы это делаете, какие технологии используете?

    Пишу код на питоне.
    Давно хочу разобраться с доступом к контакту как крупнейшей русскоязычной социальной сети. Обзорная/вводная статья (а лучше серия статей «по шагам») была бы очень кстати.

    Неужели их не существует? Мне, честно говоря, обзорные и вводные тексты не очень интересно писать. У ВК прекрасная документация.
    Можно ли например провернуть такую штуку: взять список пользователей и список групп, пройтись по ним и найти все комментарии и все лайки пользователя с конкретным ID. Скорость пофиг, все в личных целях.

    Да, думаю, можно.
  • +4
    А что за зелёная хорда такая?
    • 0
      Присоединюсь к вопросу.
      А еще слева, параллельно зелёной идёт еле-заметная синяя.
    • 0
      Не знаю, какой-то артефакт укладки. Укладка — полуслучайный процесс. Сейчас уложил ещё раз, эта хорда пропала.
      • 0
        Вообще говоря, такого быть не должно. А можно несколько таких укладок привести для сравнения?
        • 0
          Если обоснуете почему, займусь. Можете скачать граф (ссылка ниже) и поукладывать
          • 0
            Есть мысль, что алгоритм укладки не очень хороший, вот и интересуюсь.
            • 0
              Не, алгоритм — космос
  • 0
    Выложите архивчик с пользователями / группами? vk.execute конечно, хорош, но ждать два дня как-то… А поиграться хочется)
    Совсем уж наглая просьба
    • И картинку графа в оооочень большом разрешении.
    • 0
      yadi.sk/d/1FMLAtShiEg5L — в таблице две колонки: номер группы и номер пользователя. Рассматривались группы с числом пользователей от 5000 до 10000 человек. Данные недельной давности.
      yadi.sk/d/Yv3cCMkBiEgDS — граф, который можно открыть в Гефи и смотреть в любом разрешении.
  • 0
    Примерно так будет выглядеть граф взаимосвязей внеземных колоний через миллион лет.
  • 0
    Спасибо за статью. Бигдата и соцсети — это всегда интересно.
    Но у меня небольшие сомнения вызвал тот факт, что 99% пользователей состоит в 15 групп и менее. Я тут проводил одно исследование, правда, только по пользователям из Белоруссии (не думаю, что для России и других стран картина принципиально иная), так вот по моим данным распределение будет такое:

    image
    • 0
      Наверное, это потому что в тексте идёт речь о выборке групп размером от 5000 до 10000 человек. Грубо говоря, если добавить в выборку МДК, все сразу станут состоять в 16 группах.
      • 0
        Если честно, не вижу причин, почему так должно происходить. Распределение должно быть примерно одинаковое, что для подписчиков крупных групп, что для маленьких.
        • 0
          Возьмём выборку из трёх групп Киномания, МДК и Чёткие приколы. Сколько пользователей будут состоять во всех трёх из них? Много. Теперь возьмём выборку из Любители стрижки каре!, НЕФТЯНИКИ, Любопышка- мамы и папы Ярославля. Сколько будут состоять в этих трёх? Мало. Вот такая идея
          • 0
            Это понятно. Но уменьшение размера выборки не должно (по идее) приводить к такому изменению распределения признака.

            Либо тут какая-то очень занятная взаимосвязь. Те, кто состоит в крупных группах, как правило подписаны на большое количество пабликов/групп. Те, кто состоит в небольших группах, состоят в небольшом количестве пабликов/групп.
            • 0
              Уменьшение выборки не должно к этому приводить, если выборка равномерная. У меня неравномерная, у меня только группы среднего размера
    • 0
      на мой взгляд, надо строить нормальное распределение (Гаусса) и смотреть. Круговая диаграмма с делением больше/меньше одной величины — это деление, а не распределение.
      • 0
        Распределение по каким величинам? Почему Гаусса, мы же не знаем, нормальное оно или нет.

        Да, это деление, но тем не менее, оно даже близко не соответствует тому делению, что указано в статье. 35 к 65, это все же слишком далеко от 1 к 99.

        • 0
          На группах от 5000 до 10000 распределение такое
          • 0
            Стоп. А как вы считали показатель «количество групп пользователя»?
            • 0
              А какие есть варианты? Берём пользователя, смотрим в каких группах из выборки он состоит
              • 0
                Ага, теперь я понял, почему у нас так различаются данные:)

                Я то брал пользователя из выборки и получал количество подписок, в которых он состоит с помощью users.getSubscriptions

                Тогда вы, конечно, правы. Ничего странного в таком распределении нет. Извиняюсь, что сразу не додумался о разнице в подходах.
              • 0
                Ваш способ сбора групп, а потом проверки на вхождение в нее юзера должен быть лучше, чем users.getSubscriptions — я замечал, что он выдает не все группы, в которые юзер входит, почему не знаю.
                • 0
                  У VK Api вообще порой бывают странности.
                  Но в целом, к этому методу у меня нареканий не было. По крайней мере, количество пабликов, на которые подписан человек, он выдавал точно. А именно они меня и интересовали.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.