Кто ВКонтакте самый главный?02.09.2015 13:49

Привет, хабр!

0f7c1213d47a4e14bb6356ac8a00121b.jpeg

Мы уже знакомы по предыдущим статьям на тему анализа данных. Теперь настало время рассказать об одной очень практической задаче, которую мы научились решать. А именно — мы узнаем, кто же на самом деле управляет нашим мнением в социальной сети ВКонтакте. Код катом много необычных результатов и интересной математики.
Сразу оговорка — ничего конкретного мы не имеем ввиду и не делаем никаких выводов, мы просто любим математику и просто пользуемся открытыми данными

Многие из Вас помнят, что не так давно мы открывали один из открытых проектов, в котором под руководством опытных людей участники могли решать реальные задачи анализа данных и набираться опыта. Теперь пришло время рассказать о результатах и показать, куда мы двигаемся дальше. Для начала напомним задачу, которую мы решали.

Введение


Не секрет, что в последнее время социальные сети становятся одним из самых эффективных инструментов распространения информации. Не так давно общественность видела примеры, когда эти инструменты используются не по назначению — вроде бы сидишь себе — ничего не делаешь, как вдруг в друзья добавляется неизвестный аккаунт и невольно начинаешь получать новые непонятные записи в ленте 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 вершин максимальной степени, более полный список — см. тут).
В общем то, когда мы увидели данный список (а потом просмотрели его дальше) сделали 2 вывода:

  • Алгоритм работает
  • Результаты немного поражают. Особенно нам понравился школьник Иван Рудской, который уделал многих звезд Российской эстрады


Мы начали было сомневаться в том, насколько корректно работает алгоритм, но т.к. в открытых источниках людей с максимальным кол-вом подписчиков мы не нашли, решили протестировать алгоритм на группах (искать группы с максимальным числом подписчиков), благо для них есть списки, вроде этого. И, действительно, получив вот такие результаты, и поняв, что ВКонтакте — это вовсе не мир скандально известного MDK, были удовлетворены.

ИТОГО


Теперь, после того, как мы получили такие результаты, мы будем двигаться дальше, а именно, используя все тот же API пытаться строить граф «репостов» со страниц этих людей, дабы оценить человека не только по кол-ву подписчиков, но и по-тому, насколько данный человек способен рапространять мнение, используя свое влияние в сети. Есть идеи, как тут грамотно применить PageRank.

Если Вы желаете подключиться к данному исследованию и получить очень крутой опыт — присоединяйтесь к нашему Data Science сообществу и пишите мне на почту (al.krot.kav@gmail.com) письмо с темой «Лидеры мнения ВКонтакте»

Ну, а мы тем временем продолжим исследования и будем радовать Вас новыми статьями из мира анализа данных и хорошей математики!=)

UPD
Да, кстати, нашли много красивых девушек таким образом
Вот, например, vk.com/id109507300. Приятного просмотра!=)

© Habrahabr.ru