Хабрахабр

Обнаружение пересекающихся сообществ в Instagram для определения интересов пользователей

Сколько может рассказать о человеке профиль в соцсети? Фотографии, посты, комментарии, подписки – непаханное поле для анализа. Сегодня поговорим о том, как мы определяем интересы пользователей на основе их подписок в сети Instagram.

image

Источник
Очевидный подход – разложить подписки человека по категориям. Допустим, среди подписок пользователя Ивана мы обнаружили двух автоблогеров и три аккаунта со смешными картинками, остальные профили не тематические (будем считать, что это друзья, родственники, коллеги и т. д.). Отсюда делаем вывод: Иван веселый человек, увлекается автомобилями. Профит. Все, что нам нужно – это соответствие “блогер + тематика контента”, но здесь не все так просто.

Блогер в Instagram ничем не отличается от обычного аккаунта (и вообще, это что-то вроде состояния души). Кто такой блогер? В идеале нас интересуют тематические аккаунты с большой долей живой аудитории, при этом не хотелось бы просто отсекать по числу подписчиков, можем что-то упустить.

Если придумывать категории самостоятельно, то обязательно что-нибудь интересное затеряется в “разном”, а когда все будет готово, окажется, что категории слишком широкие. Где взять хорошую таксономию? Мы же хотим получить естественное разбиение, а поэтому будем блогеров кластеризовать.

Еще как! Может ли один блогер относиться к нескольким категориям? Очень часто он одновременно и швец, и жнец, и на дуде игрец (а еще тревел, лайфстайл, жена и мама).
Итак, нам нужен датасет с очень большим числом блогеров и алгоритм кластеризации с пересекающимися кластерами на выходе.

С чего все началось

К нам обращаются клиенты, которые хотят разместить свою рекламу у лидеров мнений в Instagram наиболее эффективно. Иногда есть список блогеров, и тогда мы решаем задачу оптимизации – охватить больше людей за меньшие деньги, а иногда списка нет и релевантных блогеров надо найти. На этот раз искали профили врачей-офтальмологов.

Мы использовали подход, похожий на рекомендательную систему:

  1. Выбираем 3-7 подходящих профилей руками (“ядро сообщества”)

    image

  2. С помощью пересечения подписчиков определяем людей, которые интересуются темой (“увлеченные”)

    image

  3. Ищем в подписках “увлеченных” людей новых врачей

    image

  4. В случае необходимости повторяем шаги 1-3 (добавляя новых врачей к “ядру” или меняя его)

Теперь подробнее на примере.

С помощью поиска в Instagram отобрали 6 аккаунтов врачей-офтальмологов из разных регионов России: Шаг 1.

image

Список довольно случайный, но нам было достаточно того, что блог действительно соответствует тематике и подписчиков не меньше, чем 1000 человек.

После пересечения всех подписчиков смотрим на распределение.
Шаг 2.

Ура! Пересечения есть.

Итак, теперь нужно определить, кого считаем “увлеченными” офтальмологией. Более того, есть два человека, которые подписаны на все шесть профилей! Как говорится, 1 раз — случайность, 2 раза — совпадение, 3 — уже закономерность. Мы решили, что берем всех, начиная с трех подписок. Таким образом, нашли 131 (2+3+24+102) “увлеченного” пользователя.

Загружаем подписки “увлеченных” людей и опять всячески агрегируем. Шаг 3.

image

Получили внушительный список аккаунтов, из которых теперь будем отбирать новых офтальмологов. Правый столбец показывает, сколько из 131 человека, которые отобраны на втором шаге, подписаны на профиль. В топе оказались профили из нашей изначальной шестерки, что неудивительно. Если мы сейчас подберем порог и скажем: “Все профили со значением count больше десяти – новые врачи”, то мы рискуем отнести популярные аккаунты вроде Ольги Бузовой к врачам-офтальмологам и в то же время потерять меленькие, но релевантные профили, поэтому добавим еще одним столбцом количество подписчиков и рассчитаем долю увлеченных пользователей среди подписчиков.

image

Для удобства доля умножена на 100 (так что share – это по факту процент). В итоге с условием count >= 6 и share >= 0.05 получили 166 новых врачей-офтальмологов. Класс!

172 аккаунта стали новым “ядром” сообщества, это помогло найти ещё примерно 500 новых офтальмологов, но результат уже смещался в зарубежные аккаунты. Шаг 4.

Похожие аккаунты в рекомендациях Instagram

Это все, конечно, интересно, и теперь мы умеем неплохо находить похожие друг на друга аккаунты, но мы все еще мечтаем получить разбивку всех инстаблогеров по категориям. И тут в голову пришла идея посмотреть на готовые рекомендации инстаграма.

image alt

Дело в том, что у тематических аккаунтов есть рекомендации, а у обычных людей – нет. Вот и ответ на вопрос, кого считать блогерами и минус одна головная боль. Ура!

У нас был список из 1000 российских блогов, начали с него. В рекомендациях у одного блогера до 80 похожих профилей. Взяли похожих, потом похожих похожих, потом … ну вы поняли:)

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

Теперь у нас есть граф с 3 428 453 вершинами (блогеры) и 96 967 974 ребрами (похожесть двух блогеров между собой).

image

Так выглядит наш граф на очень маленьком сэмпле

Кстати, оказалось, мы не первые решили использовать такой подход.

Это похоже на наш поиск офтальмологов, но теперь мы можем учитывать все сообщества, к которым одновременно принадлежит блогер. Судя по всему, рекомендации в Instagram формируются, исходя из того, на кого еще подписаны подписчики этого профиля, поэтому у врача из Брянска в рекомендациях будут популярные брянские аккаунты и другие врачи. Плюс, скорость обработки увеличивается в разы, потому что нет необходимости анализировать всех подписчиков блогера, достаточно взять всего 80 рекомендованных аккаунтов.

Выбор и описание алгоритма

Отлично! Данные подготовили, теперь надо выбрать инструмент и алгоритм, который справится с таким большим графом, желательно за адекватное время. Напомню, что на выходе мы хотим получить набор сообществ, где один блогер может принадлежать нескольким из них.

Мы остановили свой выбор на библиотеке Stanford Network Analysis Platform (SNAP)

It is written in C++ and easily scales to massive networks with hundreds of millions of nodes, and billions of edges. Stanford Network Analysis Platform (SNAP) is a general purpose network analysis and graph mining library. It efficiently manipulates large graphs, calculates structural properties, generates regular and random graphs, and supports attributes on nodes and edges.

Наше внимание привлек алгоритм AGMfit (AGM – Affilated Graph Model), а использовали в итоге BIGCLAM (Cluster Affiliation Model for Big Networks). Отличаются они лишь тем, что в первом случае задача оптимизации решается комбинаторно, что делает его менее масштабируемым, а второй как раз позволяет подавать на вход графы вроде нашего.

В основе обоих алгоритмов лежит Affilated Graph Model, так что остановимся на ней подробнее: Основная и довольно интуитивная мысль: чем больше у двух узлов общих сообществ, тем больше вероятность связи между этими двумя узлами.

Чем больше вес, тем больше вероятность того, что участник связан (знаком) с другими членами сообщества. Предположим, у нас есть двудольный граф, в котором круглые вершины – это сообщества ($A$ и $B$), а квадратные – пользователи соцсети, и каждый человек ($u$) относится к разным сообществам с определенными весами ($F_$ и $F_{uB}$).

image

Пример: коллеги, которые учились в одном университете подписаны друг на друга в Instagram. Оба они являются выпускниками одного ВУЗа (сообщество 1) и работают в одной компании (сообщество 2), мы не знаем, что послужило причиной “дружбы” в сети и когда они познакомились. Пусть один только что окончил универ и устроился на работу, а второй выпустился пять лет назад и все это время работает в компании, тогда вес принадлежности первого к сообществу 1 будет больше, а к сообществу 2 – меньше и наоборот.

Для каждого общего сообщества пары человек мы получаем независимый шанс быть знакомыми:

$1 - exp(-F_{uc}\cdot F_{vc})$

Таким образом, чем больше общих сообществ, тем больше шансов знать друг друга:

$1 - exp(-\sum_c F_{uc}\cdot F_{vc})$

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

Таким образом, от представления слева мы перешли к картинке справа.

image

Теперь поймем, как эта модель используется в обнаружении сообществ.

Делается это с помощью максимизации функции правдоподобия У нас есть граф похожих друг на друга блогеров и наша цель обнаружить $K$ сообществ с помощью модели описанной выше, путем подбора наиболее подходящей матрицы весов $F$ (ее размерность $N$ узлов на $K$ сообществ) так, чтобы полученный на выходе граф был похож на наш исходный.

$l(F) = log P(G|F)$

А еще все это дело можно представить в виде неотрицательного матричного разложения, что как раз дает плюс в масштабируемости алгоритма BIGCLAM по сравнению с AGMfit.

Подробнее можно почитать здесь и здесь.

Подбор числа сообществ и запуск

В BIGCLAM можно задать как точное число сообществ, так и интервал. Алгоритм выбирает 20% пар узлов на тест, а на 80% происходит подгонка модели с разным числом сообществ.

Сформировали входной файлик со списком ребер и запускаем:

image

./bigclam -o:bloggers -i:query_graph_all.edgelist -c:-1 -nc:20 -mc:50000 -xc:200000 -nt:10

Параметры позволяют задавать количество попыток, минимальное и максимальное число сообществ (или точное, если необходимо), количество тредов для параллелизации и префикс выходных файлов. В нашем случае мы задали интервал от 50 до 200 тысяч сообществ с 20 попытками на 10 тредах. Все это великолепие считалось пять дней на 2 Intel® Xeon® Gold 6150 CPU @ 2.70GHz. На выходе получили два файла один для Gephi, второй текстовый, в котором каждая строка – это сообщество.

В этот раз мы опять попали в максимальное значение в 200 тысяч сообществ, но они были гораздо более качественные, на этом и остановились. На самом деле, мы запускали алгоритм дважды и первый раз уперлись в верхнюю границу в 50 тысяч сообществ, результат был неплохой, но часто попадались смешанные сообщества. Вероятно, можно было получить результат еще лучше, но двести тысяч сообществ без названий и так пугали наше воображение.

image

Красивая картинка

Что же теперь со всем этим делать?

Если есть парочка блогеров для примера, то берем все сообщества, в которые они входят, отбрасываем ненужные и все. С одной стороны, полученные сообщества помогают нам быстро искать узкие группы блогеров (как тогда с офтальмологами). Можно использовать поиск по названиям, вот, например, одно из сообществ про декор и дизайн интерьера:

image

С другой стороны, для определения интересов пользователей все эти сообщества надо как-то осмысленно назвать. А может быть, все и не нужно.

CRank

К сожалению, не все полученные сообщества одинаково хороши, и для обнаружения наиболее интересных решили попробовать использовать метод приоритезации CRank из той же библиотеки SNAP. Он призван автоматически на основе структуры графа сопоставить каждому сообществу ранг: чем больше значение, тем лучше сообщество.

На вход программе подаем найденные ранее сообщества, для каждого из них вычисляются метрики приоритизации (4 штуки), затем эти метрики агрегируются, и мы получаем оценку.

image

Подробнее можно почитать тут.

Запуск

./crank -i:bloggers_cmtyvv.txt -c:query_graph_all.edgelist -o:bloggers_prioritization.txt

Во время запуска столкнулись с проблемой совместимости с Ubuntu 18.04, здесь предлагают решение.

Так как наш файл с полученными сообществами bloggers_cmtyvv.txt и список ребер query_graph_all.edgelist изначально содержали никнеймы (типа string), пришлось их захэшировать, чтобы было int, иначе crank ругается.

Посмотрим, как это работает на примере:

Красным цветом обозначены участники сообщества, под каждой картинкой соответствующий score. Выберем несколько сообществ, где встречаются профили, содержащие в названии строку “lokomotiv”, по задумке это должны быть сообщества футбольных болельщиков клуба “Локомотив”, посмотрим, что же на самом деле.

image

Сообщество 1, score 0.4

image

Сообщество 2, score 0.41

image

Сообщество 3, score 0.34

image

Сообщество 4, score 0.13

Затем, просмотрев все профили из этого подграфа, выделяем тех, кто действительно относится к искомому сообществу, получилось вот так:

image

Получается, что первые два сообщества на самом деле содержат то, что нам нужно, практически без ошибок (за исключением профиля сборной РФ по футболу teamrussia), третье сообщество хорошее, но покрывает меньше аккаунтов, чем первые два, поэтому и score поменьше, а четвертое сообщество хоть и состоит из аккаунтов на околофутбольную тему (здесь и футболисты других клубов, и их жены, и менеджеры), но мимо, нам не подходит.
Можно сделать вывод, что CRank работает весьма неплохо.

Ручная разметка для раскраски и результаты

Для решения задачи раскраски пользователей по интересам, мы также анализируем тексты постов и нам хотелось посмотреть, где лучше/интереснее результат (в текстах или в подписках) и вообще есть ли совпадения. Для небольшой выборки людей пришлось самостоятельно разметить около 800 сообществ. Результатом мы остались более чем довольны и решили, что этот подход стоит развивать. Метод обнаружения сообществ позволяет находить очень узкие и необычные категории интересов, например, подписка на профили крыс (в смысле маленьких сереньких грызунов) и прочие удивительные вещи, можно узнать, каким именно видом спорта предположительно увлекается человек, а не запихивать всё в категорию “экстрим” и т д

Такие дела 🙂 Размечать все 200 тысяч сообществ мы, вероятно, не будем, но, может быть, поиграемся с результатами CRank и оставим только сообщества с высоким скором, а может, будем размечать по мере необходимости.

Спасибо!

Статья написана совместно с моим руководителем Артёмом Королёвым (korolevart) R&D Dentsu Aegis Network Russia

image

Источник

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»