Математика Кто ВКонтакте самый главный?

Тема в разделе "Мир вокруг нас", создана пользователем лис.хвост, 2 сен 2015.

  1. лис.хвост
    Оффлайн

    лис.хвост VIP Разработчик

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

    Введение

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

    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) письмо с темой «Лидеры мнения ВКонтакте»

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

    Источник: Кто ВКонтакте самый главный?
     
    Последнее редактирование: 2 сен 2015
    orderman, Phoenix, Kиpилл и 3 другим нравится это.
  2. Kиpилл
    Оффлайн

    Kиpилл Команда форума Администратор

    Лучший автор месяца

    Сообщения:
    12.220
    Симпатии:
    4.978
    Я всегда не любил всякие контактники))
    Оказывается шибко умные они еще.
     

Поделиться этой страницей