Во-первых, такой граф красиво выглядит:
Во-вторых, с его помощью можно быстро подбирать группы заданой тематики. Например, нужно найти группы про вязание. По ключевому слову «вязание» находим, одну подходящую группу, Knitting -Вязание online-, например. Выводим группы, с которыми она связана:
Knitting -Вязание online-:
6.04% Корпорация «ПРЯЖА»
5.90% Мамочкин канал — для творческих мам (КРЮЧКОМ!)
3.40% Вязание. В этом мире всё связано...))
3.01% ПРЯЖА ДЁШЕВО.ФЛИС.РЕЗИНКИ ДЛЯ ПЛЕТЕНИЯ БРАСЛЕТОВ
2.35% Пряжа Spagetti Спагетти
1.87% Магазинчик пряжи Eesti long (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 long (Kauni, Кауни)
Корпорация «ПРЯЖА»:
7.54% Вязание. В этом мире всё связано...))
4.01% Мамочкин канал — для творческих мам (КРЮЧКОМ!)
3.47% Knitting -Вязание online-
3.20% ПРЯЖА ДЁШЕВО.ФЛИС.РЕЗИНКИ ДЛЯ ПЛЕТЕНИЯ БРАСЛЕТОВ
2.72% Интернет-Магазин Пряжи «АЖУР»
2.67% Пряжа
2.11% «Мадам Вязалкина» Пряжа (товары для рукоделия)
2.00% Пряжа Кауни (Kauni) — легенда Эстонии. Вязание.
1.85% Магазинчик пряжи Eesti long (Kauni, Кауни)
1.82% Пряжа Spagetti Спагетти
«Мадам Вязалкина» Пряжа (товары для рукоделия):
2.49% Пряжа
2.37% Корпорация «ПРЯЖА»
1.42% Магазинчик пряжи Eesti long (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)
alexkuku
03.08.2015 01:29+1На чем вы это делаете, какие технологии используете?
Пишу код на питоне.
Давно хочу разобраться с доступом к контакту как крупнейшей русскоязычной социальной сети. Обзорная/вводная статья (а лучше серия статей «по шагам») была бы очень кстати.
Неужели их не существует? Мне, честно говоря, обзорные и вводные тексты не очень интересно писать. У ВК прекрасная документация.
Можно ли например провернуть такую штуку: взять список пользователей и список групп, пройтись по ним и найти все комментарии и все лайки пользователя с конкретным ID. Скорость пофиг, все в личных целях.
Да, думаю, можно.
shadowjack
03.08.2015 06:20+4А что за зелёная хорда такая?
efremovaleksey
03.08.2015 10:06Присоединюсь к вопросу.
А еще слева, параллельно зелёной идёт еле-заметная синяя.
alexkuku
03.08.2015 11:31Не знаю, какой-то артефакт укладки. Укладка — полуслучайный процесс. Сейчас уложил ещё раз, эта хорда пропала.
Psychopompe
03.08.2015 22:19Вообще говоря, такого быть не должно. А можно несколько таких укладок привести для сравнения?
alexkuku
04.08.2015 11:02Если обоснуете почему, займусь. Можете скачать граф (ссылка ниже) и поукладывать
Xao
03.08.2015 10:33Выложите архивчик с пользователями / группами? vk.execute конечно, хорош, но ждать два дня как-то… А поиграться хочется)
Совсем уж наглая просьба- И картинку графа в оооочень большом разрешении.
alexkuku
03.08.2015 11:55yadi.sk/d/1FMLAtShiEg5L — в таблице две колонки: номер группы и номер пользователя. Рассматривались группы с числом пользователей от 5000 до 10000 человек. Данные недельной давности.
yadi.sk/d/Yv3cCMkBiEgDS — граф, который можно открыть в Гефи и смотреть в любом разрешении.
Alexeyslav
03.08.2015 10:35Примерно так будет выглядеть граф взаимосвязей внеземных колоний через миллион лет.
Apatic
03.08.2015 10:40Спасибо за статью. Бигдата и соцсети — это всегда интересно.
Но у меня небольшие сомнения вызвал тот факт, что 99% пользователей состоит в 15 групп и менее. Я тут проводил одно исследование, правда, только по пользователям из Белоруссии (не думаю, что для России и других стран картина принципиально иная), так вот по моим данным распределение будет такое:
alexkuku
03.08.2015 11:05Наверное, это потому что в тексте идёт речь о выборке групп размером от 5000 до 10000 человек. Грубо говоря, если добавить в выборку МДК, все сразу станут состоять в 16 группах.
Apatic
03.08.2015 11:32Если честно, не вижу причин, почему так должно происходить. Распределение должно быть примерно одинаковое, что для подписчиков крупных групп, что для маленьких.
alexkuku
03.08.2015 11:41Возьмём выборку из трёх групп Киномания, МДК и Чёткие приколы. Сколько пользователей будут состоять во всех трёх из них? Много. Теперь возьмём выборку из Любители стрижки каре!, НЕФТЯНИКИ, Любопышка- мамы и папы Ярославля. Сколько будут состоять в этих трёх? Мало. Вот такая идея
Apatic
03.08.2015 12:06Это понятно. Но уменьшение размера выборки не должно (по идее) приводить к такому изменению распределения признака.
Либо тут какая-то очень занятная взаимосвязь. Те, кто состоит в крупных группах, как правило подписаны на большое количество пабликов/групп. Те, кто состоит в небольших группах, состоят в небольшом количестве пабликов/групп.alexkuku
03.08.2015 12:18Уменьшение выборки не должно к этому приводить, если выборка равномерная. У меня неравномерная, у меня только группы среднего размера
Anvol
03.08.2015 11:51на мой взгляд, надо строить нормальное распределение (Гаусса) и смотреть. Круговая диаграмма с делением больше/меньше одной величины — это деление, а не распределение.
Apatic
03.08.2015 12:04Распределение по каким величинам? Почему Гаусса, мы же не знаем, нормальное оно или нет.
Да, это деление, но тем не менее, оно даже близко не соответствует тому делению, что указано в статье. 35 к 65, это все же слишком далеко от 1 к 99.
alexkuku
03.08.2015 12:21На группах от 5000 до 10000 распределение такое
Apatic
03.08.2015 12:44Стоп. А как вы считали показатель «количество групп пользователя»?
alexkuku
03.08.2015 12:50А какие есть варианты? Берём пользователя, смотрим в каких группах из выборки он состоит
Apatic
03.08.2015 12:55Ага, теперь я понял, почему у нас так различаются данные:)
Я то брал пользователя из выборки и получал количество подписок, в которых он состоит с помощью users.getSubscriptions
Тогда вы, конечно, правы. Ничего странного в таком распределении нет. Извиняюсь, что сразу не додумался о разнице в подходах.
mechkladenets
05.08.2015 11:19Ваш способ сбора групп, а потом проверки на вхождение в нее юзера должен быть лучше, чем users.getSubscriptions — я замечал, что он выдает не все группы, в которые юзер входит, почему не знаю.
Apatic
06.08.2015 13:46У VK Api вообще порой бывают странности.
Но в целом, к этому методу у меня нареканий не было. По крайней мере, количество пабликов, на которые подписан человек, он выдавал точно. А именно они меня и интересовали.
NeoCode
На чем вы это делаете, какие технологии используете? Давно хочу разобраться с доступом к контакту как крупнейшей русскоязычной социальной сети. Обзорная/вводная статья (а лучше серия статей «по шагам») была бы очень кстати.
Можно ли например провернуть такую штуку: взять список пользователей и список групп, пройтись по ним и найти все комментарии и все лайки пользователя с конкретным ID. Скорость пофиг, все в личных целях.
AgentSmith
конечно можно
Protos
Я проворачивал это: поиск фото пользователя в альбомах групп в которых он состоит и поиск фото в комментариях написанным им в группах. Однако у меня все медленно искалось (не использовал трюки с распараллеливанием) делалось. Может кто реализует.
ilnuribat
skotobaza.org
На дваче эту идею озвучивали, мой друг его реализовал (php + mySQL). Быстро набрав популярность сервер не выдержал и упал (19 тыс пользователей за ночь, всё логгировалось, железо было самое простое). Через некоторое время пришло письмо на его личную почту (которую он нигде не публиковал) с просьбой закрыть сайт от админов группы 40 кг (или от других групп, не помню детали), с угрозой «наши юристы сделают с Вами плохо». Сразу после этого он выложил исходный код на двач и бросил это дело.
Подхватили его друзья, быстро переписали на nodejs и запустили, я так полагаю, на зарубежных серверах.
В свое время их блокировали РосРеестр, но позже их открыли.
Есть даже его интервью, ссылку могу чуть позже скинуть
Psychopompe
Интересно было бы почитать.
ilnuribat
tjournal.ru/p/vk-photo-search
Автор сейчас в армии, поэтому долго с ним связывался
Apatic
Возьмите любой язык программирования и делайте на нем. Описание АПИ и доступа к нему есть в самом ВК и очень даже подробные.
Я выкладывал тут статью (теперь она на ММ), где к доступу к ВК использовал вообще 1С. Так что технологии не важны, был бы API:)
samodum
для таких вещей API не подходит, т.к. легко будет заблокировать все запросы
Apatic
А через что вы это предлагаете решать?
Насчет блокировки, автор статьи верно заметил про метод execute. Полностью не спасет, но значительно облегчит задачу — это точно.