Мы уже знакомы по предыдущим статьям на тему анализа данных. Теперь настало время рассказать об одной очень практической задаче, которую мы научились решать. А именно — мы узнаем, кто же на самом деле управляет нашим мнением в социальной сети ВКонтакте. Код катом много необычных результатов и интересной математики.
Сразу оговорка — ничего конкретного мы не имеем ввиду и не делаем никаких выводов, мы просто любим математику и просто пользуемся открытыми данными
Многие из Вас помнят, что не так давно мы открывали один из открытых проектов, в котором под руководством опытных людей участники могли решать реальные задачи анализа данных и набираться опыта. Теперь пришло время рассказать о результатах и показать, куда мы двигаемся дальше. Для начала напомним задачу, которую мы решали.
Введение
Не секрет, что в последнее время социальные сети становятся одним из самых эффективных инструментов распространения информации. Не так давно общественность видела примеры, когда эти инструменты используются не по назначению — вроде бы сидишь себе — ничего не делаешь, как вдруг в друзья добавляется неизвестный аккаунт и невольно начинаешь получать новые непонятные записи в ленте Facebook. На сегодняшний день существует множество методов по раскрутке групп и страниц в социальных сетях для генерирования трафика и последствующего извлечения из этого выгоды. Также далеко не секрет, что интернет-компании активно борются с данного рода деятельностью и сотрудничают с соответствующими ведомствами, т.к. зачастую деятельность «лидеров мнений» несет угрозу в том числе и национальной безопасности стран.
Знаете ли Вы, как можно управлять мнением в социальных сетях? На самом деле, не так то это и сложно — важно знать, через какие каналы распространять информацию. И тут, как всегда, не обойтись без математики, в особенности — теории графов.
Именно поэтому мы решили запустить серию задач, в которой покажем, как, используя достаточно ограниченный API социальных сетей, научиться находить лидеров мнений, измерять качество рекламных кампаний и следить за распространением информации в социальных сетях на примере ВКонтакте.
Первой, и самой простой задачей, приближающей нас к вычислению лидеров мнений является задача выявления пользователей с максимальным количеством подписчиков в рамках ограниченного API. Особенностью здесь является то, что весь граф социальной сети практически нереально просмотреть. Учитывая, что ежемесячная аудитория ВКонтакте насчитывает более 300 млн. пользователей, а запросов к API разрешается делать не более 3х в секунду, легко сообразить, что понадобился около 3х лет, чтобы вычислить кол-ва подписчиков всех людей. Мы покажем, как вычислить ТОП100 людей с максимальным кол-вом подписчиков за несколько минут. Но сперва немного погрузимся в формальные определения. Ведь без хорошей математики тут не обойтись.
Социальная сеть с точки зрения математики можно представить ориентированным графом, вершины которого — пользователи, а ребра, их соединяющие обозначают факт дружбы/фолловерства/подписки. При этом, наш граф ориентированный — ребра имеют направление (в зависимости от того, кто кого «фолловит»). Для неориентированного графа определено понятие степени (кол-ва друзей вершины). Для ориентированного — входящей степени (кол-во «фолловеров») и исходящей степени (кол-во людей, на которых челоек «подписан»).
В целом, ничего особенного, если бы многие графы, которые встречаются в жизни не были бы устроены определенным образом. Для этого даже есть целая наука, которая занимается исследованием так называемых веб-графов. Все началось с того, что в 1999 году вышла в свет статья А.-Л. Барабаши и Р.Альберт, в которой авторы экспериментально исследовали свойства Интернета и предложили идею его формирования, которая впоследствии была формализована многими авторами и очень активно используется на практике. Итак, начнем с тех самых особенностей социальных сетей.
Свойства реальных сетей
Сразу скажем, что когда мы говорим о веб-графе, под вершинами мы подразумеваем определенные единицы в Интернете, для определенности будем считать сайты (можно, например, рассматривать и хосты). Ребрами будем соединять те вершины, между которыми имеются ссылки. Понятно, что граф ориентированный и допускаются кратные ребра. Допускаются даже петли (ребра из вершины в себя) и даже кратные петли.
1. Диаметр веб-графа мал
Это одно из самых известных свойств графов типа веб, которое многие знают как «теория шести рукопожатий», которое означает, что любые 2 человека на Земле знакомы через 6 рукопожатий друг с другом. На языке теории графов это свойство означает, что у графа малый диаметр. Это наводит на мысли, что граф должен быть достаточно плотным, однако, это не так.
2. Разреженность
Веб-граф — это довольно разреженный граф. Более формально — на n вершинах всего около const*n ребер. Казалось бы, что большой граф малого диаметра должен быть очень плотным, т.е. иметь порядка n^2 ребер, однако, факт остается фактом. Следующее свойство для человека, не знакомого с математикой звучит не так информативно, но именно оно в будущем подскажет, как должен формироваться сам граф, чтобы удовлетворять всем свойствам реального веба.
3. Степенной закон распределения степеней вершин
Оказывается, что доля вершин степени d в веб-графе оценивается как const/d^a, где 2 < a < 3 (на момент исследования значение a было около 2.1).
Именно такими свойствами обладает Интернет. Теперь, если мы будем знать, как устроен процесс такого графа, мы сможем делать многие вещи, начиная от того, что искать спам-структуры (многие из которых представляют совбо плотные двудольные подграфы), заканчивая тем, чтобы эффективно искать вершины максимальной степени (об этом мы и расскажем ниже).
Идея предпочтительного присоединения
На сегодняшний день одной из самых распространненых идей, лежащих в основе построения веб-графа является идея предпочтительного присоединения, логика которой заключается в следующем. Давайте считать, что как только появляется новый сайт, он скорее предпочтет состаться на тех, кто уже популярен на тот момент. Более формально — вероятность, с которой новый сайт поставит ссылку на уже существующий пропорциональна числу уже имевшихся на тот сайт ссылок.
Понятно, что описанная выше идея плохо формализована и уточняя многие детали можно получить множество моделей веб-графов. Так появились модели Боллобаша — Риордана, Бакли — Остгуса, модель копирования и многие другие. Не так давно в Яндексе был даже рассмотрен целый класс моделей, для которого было доказано множество интересных результатов.
Надеюсь, у читателя сложилось понимание того, как устроен Интернет с точки зрения теории графов. Оказывается, что множество других реальных сетей, в том числе и соц. сети устроены похожим образом. Именно это и поможет нам в нашей задаче.
Эвристический алгоритм определения вершин максимальной степени
Теперь вернемся к нашей задаче. Как можно использовать свойства реальных сетей, описанные выше для того, чтобы найти вершины максимальной степени с достаточно большой точностью? Давайте возьмем некоторое количество произвольных вершин нашего графа (например, из равномерного распределения). Обозначим это множество вершин за A. Примерно понятно, что с достаточно большой вероятностью многие из них сошлются на одну из каких-то популярных вершин. Давайте тогда выпустим из этих вершин ребра (посмотрим, на кого эти вершины подписались) — обозначим множество этих вершин за B. Понятно, что какие-то вершины из A ссылаются на одну и ту же вершину из B. Для каждой вершины V из множества B подсчитаем кол-во вершин из A, которые попали в вершину V. Тем самым, мы получим оценку снизу на входящую степень (кол-во подписчиков) каждой вершины из множества B. Назовем это «оценкой входящей степени» вершины V.
А теперь главный момент, который очень сложно объяснить читателю без серьезной математической подготовки более подробно, чем в этой статье: за счет того, что социальный граф обладает свойствами, описанными выше получается так, что в множество B попадут именно вершины максимальной степени в исходном графе. Таким образом, остается отсортировать вершины из множества B по «оценке входящей степени» и уточнить для каждой из этих вершин реальное значение подписчиков в ней. Более подробно с алгоритмом и его обоснованием можно познакомиться тут.
Как видно, алгоритм довольно простой и не требовательный к вычислительным ресурсам. Именно это и предполагалось реализовать участникам нашего исследования для российской социальной сети ВКонтакте.
Небольшой оффтоп
Как мы уже говорили ранее, в том числе на прошедших конференциях, при обучении людей мы стараемся объяснять сложные вещи простым языком и давать максимально практические навыки. Чтобы у человека сформировался некоторый образ и понимание, достаточные для практического применения навыков анализа данных. Именно поэтому, мы берем людей из разных предметных областей, и, обмениваясь опытом друг с другом, прививаем недостающие навыки участникам и себе.
Одним из участников исследования являлся Глеб Морозов, который более 6ти лет решал аналитические задачи в крупных федеральных ритейловых сетях, среди которых, например, ЗАО «Тандер» (Магнит) или ТД «Мегаполис». После большого кол-ва совместно решенных задач, о которых он еще расскажет чуть позже, Глеб научился применять машинное обучение в ритейле, а команда MLClass получила опыт предметной области. О самих задачах Глеб расскажет чуть позже самостоятельно, а пока я приведу его код, который он использовал для решения вышеописанной задачи.
Реализация алгоритма на языке R
Ниже приведена довольно простая и хорошо откомментированная реализация данного алгоритма на языке R. Любой читатель сможет легко вопроизвести результат.
library("RCurl") # Библиотека для генерации запросов к API
library("jsonlite") # Библиотека для обработки JSON
library("stringr") # Библиотека для работы с текстом
# Шаблон запроса подписок аккаунта
url <- "https://api.vk.com/method/users.getSubscriptions?user_id="
# Шаблон запроса подписчиков аккаунта
url2 <- "https://api.vk.com/method/users.getFollowers?user_id="
# Генерируем id аккаунта с replace (выбираем из 2.8 млн. id 700 аккаунтов с повторениями)
id_num <- sample.int(280000000, size = 300, replace = T)
# Функция для получения id подписок для сгенерированных аккаунтов
get_id_account <- function(id) {
url_get <- str_c(url, id) # Составляем запрос к API
resp <- getURL(url_get) # Запрашиваем и получаем ответ
Sys.sleep(0.5) # Задержка для обхода ограничения на кол-во запросов в сек
# Обрабатываем ответ и получаем id подписок
fromJSON(resp)$response$users$items
}
# Функция для получения кол-ва подписчиков аккаунта
get_count <- function(id) {
url_get <- str_c(url2, id)
resp <- getURL(url_get)
Sys.sleep(0.5)
fromJSON(resp)$response$count
}
# Получаем, при помощи функции get_id_account, id подписок для аккаунтов в виде list
account_id <- sapply(id_num, get_id_account)
# Преобразовываем list в data.frame
account_id <- unlist(account_id)
# Подсчитываем кол-во попаданий для каждого id полученных аккаунтов
account_id <- table(account_id)
# Преобразовываем в data.frame
account_id <- as.data.frame(account_id)
# Сортируем в убывающем порядке
account_id <- account_id[order(-account_id$Freq),]
# Получаем, при помощи функции get_count, кол-во подписчиков
result <- sapply(as.numeric(as.character(account_id$account_id[1:300])), get_count)
# Объединяем полученные данные о кол-ве подписчиков с id аккаунтов
result <- cbind(as.numeric(as.character(account_id$account_id[1:300])), result)
# Сортируем в убывающем порядке
result <- result[order(-result[,2]),]
result <- data.frame(id = result[,1], count_of_followers = result[, 2])
write.csv(result, "result_subscribers.csv")
Как видно, что алгоритм, что его реализация — очень простые. Теперь давайте немного посмотрим на результаты.
Результаты
Буквально за несколько минут мы получим следующие результаты (ТОП20 вершин максимальной степени, более полный список — см. тут).
| Человек | Кол-во подписчиков |
| Павел Дуров | 6192543 |
| Дмитрий Медведев | 2058871 |
| Катя Клеп | 1397818 |
| Иван Рудской | 1308458 |
| Нюша Шурочкина | 916338 |
| Мария Кожевникова | 908909 |
| Саша Спилберг | 837179 |
| Михаил Задорнов | 736109 |
| Максим Голополосов | 734602 |
| Виктория Боня | 733385 |
| Кристина Добродушная | 607419 |
| Мария Вэй | 598583 |
| Тина Канделаки | 541142 |
| Катя Самбука | 538611 |
| Софья Темникова | 530157 |
| Алексей Долматов | 518934 |
| Михаил Галустян | 515012 |
| Мариана Рожкова | 508894 |
| Вася Вакуленко | 445594 |
| Владимир Жириновский | 442578 |
В общем то, когда мы увидели данный список (а потом просмотрели его дальше) сделали 2 вывода:
- Алгоритм работает
- Результаты немного поражают. Особенно нам понравился школьник Иван Рудской, который уделал многих звезд Российской эстрады
Мы начали было сомневаться в том, насколько корректно работает алгоритм, но т.к. в открытых источниках людей с максимальным кол-вом подписчиков мы не нашли, решили протестировать алгоритм на группах (искать группы с максимальным числом подписчиков), благо для них есть списки, вроде этого. И, действительно, получив вот такие результаты, и поняв, что ВКонтакте — это вовсе не мир скандально известного MDK, были удовлетворены.
ИТОГО
Теперь, после того, как мы получили такие результаты, мы будем двигаться дальше, а именно, используя все тот же API пытаться строить граф «репостов» со страниц этих людей, дабы оценить человека не только по кол-ву подписчиков, но и по-тому, насколько данный человек способен рапространять мнение, используя свое влияние в сети. Есть идеи, как тут грамотно применить PageRank.
Если Вы желаете подключиться к данному исследованию и получить очень крутой опыт — присоединяйтесь к нашему Data Science сообществу и пишите мне на почту (al.krot.kav@gmail.com) письмо с темой «Лидеры мнения ВКонтакте»
Ну а мы тем временем продолжим исследования и будем радовать Вас новыми статьями из мира анализа данных и хорошей математики!
UPD
Да, кстати, нашли много красивых девушек таким образом
Вот, например, vk.com/id109507300, сударыня набрала подписчиков больше, чем многие российские звезды. Приятного просмотра!
Комментарии (45)
Dreamastiy
02.09.2015 14:21+1# Генерируем id аккаунта с replace (выбираем из 2.8 млн. id 700 аккаунтов с повторениями) id_num <- sample.int(280000000, size = 300, replace = T)
Все думал, как собрать список Id VK.
Ваше решение порадовало.
А почему выборка с повторениями?
EngineerSpock
02.09.2015 14:33+16Кто все эти люди из топа? (ну, кроме Дурова, Медведева и Жирика)
Посмотрел на топ и возникло ощущение, что я вообще не участвую в жизни страны :)
redmanmale
02.09.2015 17:18+1А вы вспомните:
распределение по возрасту
numberfive
02.09.2015 18:27там уже выше писали, что смотря на эти результаты люди испытывают чувство стыда за других.
akrot
02.09.2015 18:44У меня было также=) особенно порадовало, что некто Катя Самбука, например, обгоняет многих звезд, типа Тины Канделаки=)
questor
02.09.2015 14:45+1Можно ли как-то вычислять ботов во вконтакте? Вот, надысь был скандал с Ashley Madison — у них оказывается полно было ботов-женщин. Факт, что любую группу вк можно прокачать собачками абсолютно никого не удивляет. А какие есть методики их, ботов, надёжного выявления без участия человека?
akrot
02.09.2015 18:45Ботов найти довольно легко, ровно как и выявить, что пользователь нагнал своих подписчиков
Как минимум по тому, что у них срок жизни маленький
Jeditobe
02.09.2015 16:16+2Посмотрел я кто такая Маша Вей, посмотрел ее ютуб канал, и мне захотелось все это развидеть и не знать, кто у нас лидер мнений и чем интересуются пользователи.
AllexIn
02.09.2015 16:25+7Ну весь канал я не шерстил, но конкретно видео по ссылке вроде вполне нормальное с ЦА в виде школьниц.
Вот EeOneGuy я совершенно не понимаю ни цели существования, ни ЦА.Jeditobe
02.09.2015 19:34+1Советую все-же весь канал пролистать.
А вообще, мне есть много чего про эту чушь сказать, но не буду, а то вдруг и на Хабре ее ЦА сидит.
Mozart
02.09.2015 21:04+2Монтаж сразу видно хороший. Да и кол-во просмотров, лайков отличное. Нашла свою аудиторию отлично. )
wiygn
02.09.2015 23:40+3Все правильно, для Хабра нужен code-beauty blog с рефакторингом в стиле «теперь я беру синтаксический анализатор и круговыми движениями провожу им по коду».
Вместо «моя комната» будет «мой репозиторий».
А вместо «косметика, которой я пользуюсь» всякие новые модненькие библиотеки.
akrot
02.09.2015 18:46+2А тем временем, все эти люди из ТОПа неплохо монетизируют свои страницы, надо сказать)
rushter
02.09.2015 23:38Скорей всего многие из них ещё со старых времён подписчиков и ботов себе нагнали, когда вк не так жёстко их банил.
Ведь чем больше подписчиков, тем выше страничка. Мне попадалась расценки на ботов и на сколько я помню за несколько тысяч рублей можно было получить 50 тыс. ботов. Ну а дальше уже живые люди будут подписывать из-за особенностей ранжирования у вк.
Так что многие «звёзды» которых за пределами вк никто не знает скорей всего так и поступали, ну или просто скрипты использовали, которые всем заявки шлют в друзья, а потом в подписчики кидают.rushter
02.09.2015 23:50+1О, кстати, вспомнилось. Я на основе тематических групп вк (например про маркетинг) находил влиятельных людей в выбранной сфере.
Там тоже очень большое поле для работы есть, если построить граф связанности друзей, то открывается интересная картина.
Можно увидеть определённые кластеры, которые представляют из себя работников одних компаний.
Т.е. чисто теоретически с помощью соц. сетей в любой нише можно найти лидирующие компании и их работников не используя linkedin :).
wiygn
02.09.2015 23:51В статье 6 из 20 людей — видеоблоггеры (ну это те, о ком я слышал вообще) и там аудитория, насколько я знаю, изначально приходила с youtube. Некоторые вообще забавно «переливают» свою аудиторию, например женщина упомянутого в статье Рудского, стала популярной после упоминаний и появлений в его роликах. Та же Мария Вэй светилась у Клеп. Спилберг просто беззастенчиво накручивала аудиторию и просмотры на youtube (как сейчас у нее с этим не знаю).
Другое дело, что можно накручивать подписки уже на youtube.akrot
03.09.2015 14:47Видеоблогеры — тема отдельная, есть определенные механики, позволяющие видео накручивать
У Рудского, например, есть даже ценник, кажется, для этого
ValdikSS
27.09.2015 16:41Когда я крутил VNC-рулетку, я находил довольно много машин-ботов, которые заскриптованно открывали страницы браузеров, как правило, youtube-видео, просматривали его и кликали на лайки всякие.
Dreamastiy
02.09.2015 22:37+5Попробовал исполнить приведенный код, получил
следующие результатыТОП-20
(красивая табличка почему-то не форматируется,
цифра — количество подписчиков,
в коде заменил https на http, иначе не работало):
Павел Дуров 6186800
Катя Клэп 1406028
Михаил Задорнов 735902
Виктория Боня 733776
Кристина Добродушная 609152
Maria Way 602324
Юлия Пушман 433243
Макс Корж 417176
Ира Ира 240699
Дарья http://vkontakte.ru/club5896878 Пынзарь (Черных) 215022
Анна Хилькевич 208150
Miron Oxxxymiron Федоров 207155
Дмитрий Данилов 178425
Саша [Феникс] Межаков 133934
Назарій Куля 112318
Анастасия MarMeladka Мачихина 102562
Денис Гущин 101302
Ирина Воронцова 98883
Гузалька Хуббиева 98122
Сергей dreik Колесник 97648
questor
03.09.2015 00:55У меня до пятой строчки совпадает с приведённым в статье, а потом пошли разночтения.
"",«id»,«count_of_followers»
«1»,1,6186619
«2»,53083705,2063781
«3»,5592362,1406207
«4»,53636214,1329797
«5»,2677959,734812
«6»,16971887,609240
«7»,49794138,519518
«8»,2128351,445980
«9»,322022,323733
«10»,13082236,307983
akrot
03.09.2015 14:46+1Посмотрите ссылку на статью — там написано про то, как именно подбирать значение более подробно. Если кратко — посмотирте на график, который там есть — сразу на вскидку будет понятно, как оптимальное значение подобрать
Michael134096
03.09.2015 13:18Автор, вы поссчитали людей, у которых больше всего подписчиков. А каков будет список людей, у которых больше всего друзей?
А в Фейсбуке и других социальных сетях кто имеет больше всего подписчиков и друзей?
Встречается ли кто-то и тут и там?questor
03.09.2015 13:40+1Во вконтакте есть лимит на число друзей — 10 тысяч. И в него упрётся слишком большое число людей. Вон, у Дурова 6 миллионов подписчиков, а у Медведева — «всего лишь» два миллиона. И вы хотите считать «каких-то» десятитысячников.
Цифра в 10 тысяч и без того завышена. Это ж если не спать, ни есть, ни работать — на одного друга за год по минуте общения выйдет. Что за друзья такие? Эти отношения явно не дружбой называть надо.
akrot
03.09.2015 14:44+1Все верно написано ниже — друзей смотреть нет смысла — там потолок
ФБ не смотрели еще. Смотрели твиттер (у него, кстати, еще жестче ограничения API), но там ничего интересноно
deNULL
03.09.2015 19:38+3Учитывая, что ежемесячная аудитория ВКонтакте насчитывает более 300 млн. пользователей, а запросов к API разрешается делать не более 3х в секунду, легко сообразить, что понадобился около 3х лет, чтобы вычислить кол-ва подписчиков всех людей.
В рамках ВКонтакте API есть один интересный метод execute, который может пригодиться всем желающим ускорить/оптимизировать запросы к социальной сети.
С помощью него в один http-запрос (чаще всего) удается уместить до 25 обращений к методам API — то повысить фактическую частоту обращений с 3 запросов в секунду до (в идеальном случае) 75. Правда, с некоторыми «тяжелыми» методами такое не очень прокатывает, так как сервера ВК физически могут быть не способны успеть обработать столько запросов. Конкретные лимиты нужно выяснять опытным путем (а лучше всего делать умный группировщик запросов, который при возникновении ошибок будет способен разбить большой пакет запросов на несколько более мелких пакетов).
Тем не менее, наверняка многим этот подход окажется полезен.
rhamdeew
04.09.2015 02:26Можно еще в инстаграм пошариться и вывести топ российских звезд. Правда у них довольно жесткие ограничения на запросы к API (не более 5 тысяч за час и отдача максимум 33 фотографий за раз).
Из интереса сделал простой вариант с топом по своему небольшому городу. Самое интересное что аккаунты накручиваемые ботами очень сильно палятся. У них в день может быть по 600-900 подписок и примерно столько же отписок. Механизм используется примерно тот же что и в ВК — бот сперва подписывается на вас, а когда вы подписываетесь в ответ через некоторые время он отписывается. В итоге пользователи так и смотрят потом фотографии с «навязанного» им аккаунта.
kfedorenko
08.09.2015 15:59+2Ваши результаты в крайне неудобном виде представлены. Добавьте, пожалуйста, названия групп к id группы.
WaveCut
Топ удивляет…
AllexIn
Что конкретно вас удивило?
WaveCut
Удивило количество низкосортных «влоггеров» и школьников. Тот момент, когда стыдно за других людей. За миллионы других людей.
AllexIn
А кто там должен быть-то?
Простой вопрос: на кого подписаны Вы в контакте?
Наверняка ни на кого, или на пару специфичных людей, которые не постят массовую информацию, а постят специфичные вещи интересные вам и еще паре человек.
Ну никогда теория струн не будет популярнее шуток про секс.
Потому что теорией струн интересуется два с половиной человека из тысячи, а сексом — вся тысяча.
Jeditobe
Маша Вей — это уже тушите свет.
vlreshet
Я не знаю кто минуснул ваш коммент, но была бы карма — люто заплюсовал бы. Такая жесть и в топе.
alexpp
Кто это такая вообще?
akrot
Да не, топ как раз по идее не сильно должен удивлять, учитывая, что основная аудитория ВК — это как раз школьники. А вот дальше там есть интересные моменты. Например, одна из Питерских девушек, которая довольно высоко в ТОПе вообще не гуглится. Тем не менее набирает лайки и подписчиков очень круто за счет обнаженки=) за что, кстати, судя по постам на ее страница, ее не раз уже банили=)
questor
Насколько будут отличаться результаты для нишевых сообществ? Пример: по теме «игра мафия» во вконтакте есть 2000 сообществ, в тех, где указан город Москва состоит порядка 160 тысяч уникальных учёток, из них 40 тысяч — из Москвы, много в Киеве и т.п. (ручаюсь за порядок цифр, точные давно не смотрел) Ежедневно есть некоторый прирост этого всего графа. Насколько закономерности «общероссийские» будут нивелироваться закономерностями тематики сообществ?
fido_max
Видимо, что Владимир Владимирович не пользуется VK
akrot
Страница В.В., кстати, там есть довольно высоко. Но она не подтвержденная, у него там около 200 тыс подписчиков