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

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

    image
    Источник

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

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

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

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

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

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

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

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

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

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

      image

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

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

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

    image

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

    Шаг 2. После пересечения всех подписчиков смотрим на распределение.
    Number of mutual followings Number of accounts
    6 2
    5 3
    4 24
    3 102
    2 693
    1 30025

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

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

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

    image

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

    image

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

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

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

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

    image alt

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

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

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

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

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

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

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

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

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

    Мы остановили свой выбор на библиотеке Stanford Network Analysis Platform (SNAP)
    Stanford Network Analysis Platform (SNAP) is a general purpose network analysis and graph mining library. It is written in C++ and easily scales to massive networks with hundreds of millions of nodes, and billions of edges. 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_{uA}$ и $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, второй текстовый, в котором каждая строка – это сообщество.

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

    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 ругается.

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

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

    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
    Источник
    Dentsu Aegis Network
    78,86
    Компания
    Поделиться публикацией

    Комментарии 10

      0
      Серьезный подход) А подскажите, пожалуйсте, каким образом вы спарсили похожие аккаунты такой масштабной аудитории в инсте?
        0
        Поставщиков и механик, которые позволяют получать такие данные, достаточно много. Если хочется писать все с нуля самому, то можно использовать стандартный aiohttp на python. Все остальное легко гуглится:)
        0
        Статья отличная.
        Меня интересует технический вопрос. Как происходит процесс граббинга данных? Блокировок IP от Instagram нет? Как обходите?
          0
          Спасибо!
          В этой статье хотелось поделиться тем, как мы работаем с данными и анализируем их, а вот про сбор ответить ничего, к сожалению, не могу, вне моей компетенции. Благо людей, которые парсят вокруг достаточно
          0
          На этой неделе, вроде как уже, должны закрыть информацию о подписках пользователей в инсте
            0
            Нет, там речь о другом, закроют/закрыли вкладку Following, где раньше отображалась инфа о том, кто из твоих друзей что лайкнул или на кого подписался. А подписки в шапке профиля пока в целости и сохранности:)
            0

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

              +1
              Нет, такого решения нам, к сожалению, не встречалось. Почти уверена, что такой открытой базы просто не существует.
              Да, на счет мощностей вы правы, но по сути все зависит от задач, а метод AGMfit можно использовать и на маленьком графе
              0
              Статья очень крутая! Не совсем понятны несколько моментов на 3 шаге, когда пытаемся получить новую выборку офтальмологов:
              1. Каким способом, например для dr.nikiforova, из 53 count мы получили 7 count увлеченных?
              2. Почему count увлеченных именно >= 6 и share именно >= 0.05 выделяет офтальмологов от Ольги Бузовой?
              Благодарю за ответ!
                +1
                Спасибо!
                У dr.nikiforova count 53 это и есть число увлеченных подписчиков у этого аккаунта, оно не менялось (на втором скриншоте его нет)
                Вообще этими двумя картинками хотелось показать следующее: когда увлеченных много (топ списка) — это почти 100% офтальмологи, а вот когда поменьше (например, 7), то уже надо брать не всех, а смотреть на долю share. Если внимательно посмотреть на второй скриншот, то можно заметить, что там врачи (причем не все офтальмологи, есть и другие специальности) и селебы (Шнуров, Галкин и т д) и вот чтобы лишних не взять, мы ставим ограничение на share >= 0.05
                2. Почему именно эти значения: воспользовались методом пристального взгляда:)

                Для разных сообществ будут разные пороги и это зависит много от чего, из-за этого автоматизация немного усложняется. Опять же пример: для российских аккаунтов офтальмологов 25 тыс подписчиков — потолок, а если мы хотим выделить сообщество мамочек, то там и миллионники встречаются, поэтому пороги сильно зависят от задачи, от части поэтому мы перешли к другому подходу:)

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое