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

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

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

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

            Есть даже его интервью, ссылку могу чуть позже скинуть
        • 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 вообще порой бывают странности.
                                      Но в целом, к этому методу у меня нареканий не было. По крайней мере, количество пабликов, на которые подписан человек, он выдавал точно. А именно они меня и интересовали.

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

                        Самое читаемое