Хто ВКонтакте найголовніший?

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



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

Відразу застереження — нічого конкретного ми не маємо на увазі і не робимо жодних висновків, ми просто любимо математику і просто користуємося відкритими даними

Багато хто з Вас пам'ятають, що не так давно ми відкривали один з відкритих проектів, в якому під керівництвом досвідчених людей учасники могли вирішувати реальні завдання аналізу даних і набиратися досвіду. Тепер прийшов час розповісти про результати і показати, куди ми рухаємося далі. Для початку нагадаємо задачу, яку ми вирішували.

Введення
Не секрет, що останнім часом соціальні мережі стають одним з найбільш ефективних інструментів поширення інформації. Не так давно громадськість бачила приклади, коли ці інструменти використовуються не за призначенням — начебто сидиш собі — нічого не робиш, як раптом у друзі додається невідомий аккаунт і мимоволі починаєш отримувати нові незрозумілі записи в стрічці 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, добродійко набрала більше передплатників, ніж багато російські зірки. Приємного перегляду!=)

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.