Поиск связей в социальных сетях

    Привет, Хабр! В этом посте мы хотим поделиться нашим решением задачи по предсказанию скрытых связей в корпоративной социальной сети “Улей” компании Билайн. Эту задачу мы решали в рамках виртуального хакатона Microsoft. Надо сказать, что до этого хакатона у нашей команды уже был успешный опыт решения таких задач на хакатоне от Одноклассников и нам очень хотелось опробовать наши наработки на новых данных. В статье мы расскажем про основные подходы, которые применяются при решении подобных задач и поделимся деталями нашего решения.

    Постановка задачи и исходные данные


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

    В англоязычной литературе существует достаточно много публикаций по этой теме, а сама задача даже имеет специальную аббревиатуру PYMK (People You May Know).

    Компания Билайн в рамках виртуального хакатона от Microsoft предоставила граф корпоративной социальной сети «Улей». 5% ребер в графе была искусственно скрыта. Задача заключалась в поиске скрытых ребер исходного графа.



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

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

    Обучение и тест


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

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

    Каждая пара кандидатов описывается вектором признаков и бинарным ответом: “1” если ребро есть или “0” в случае отсутствия ребра. На полученном множестве {вектор признаков, ответ} обучается модель, предсказывающая вероятность наличия ребра для пары кандидатов.

    Т.к. граф в данной задаче ненаправленный, то вектор признаков не должен зависеть от перестановки кандидатов в паре. Это свойство позволяет при обучении учитывать пару кандидатов только один раз и сократить объем обучающей выборки вдвое.

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

    Для оценки качества и подбора параметров модели мы удалили из предоставленного графа 5% случайно выбранных ребер. Оставшийся граф использовали для поиска кандидатов, генерации признаков и обучения модели. Скрытые ребра использовали для подбора порога и финальной оценки качества.

    Ниже описаны основные подходы для генерации признаков в задаче PYMK.

    Счетчики


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

    Схожесть множеств и общие друзья


    Коэффициент Жаккарда — позволяет оценить сходство двух множеств. В качестве множеств могут быть как друзья, так, например, и сообщества кандидатов.


    Коэффициент Адамик/Адара — по сути это взвешенная сумма общих друзей двух кандидатов.

    Вес в этой сумме зависит от числа друзей общего друга. Чем меньше друзей у общего друга, тем больший вклад он дает в результирующую сумму. Кстати, именно эту идею мы активно использовали в своем решении.

    Латентные факторы


    Эти признаки получаются в результате матричных разложений. Причем, разложения можно применять как к матрице связей между пользователями, так и к матрицам сообщество — пользователь, или география — пользователь и им подобным. Полученные в результате разложения вектора с латентными признаками можно использовать для оценки похожести объектов друг на друга, например с помощью косинусной меры расстояния.

    Пожалуй самым распространенным алгоритмом матричного разложения является SVD. Также можно использовать популярный в рекомендательных системах алгоритм ALS и алгоритм поиска сообществ в графах BigCLAM.

    Признаки на графах


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

    Одним из популярных признаков является Hitting Time — среднее число шагов, необходимое для прохождения маршрута от одного кандидата к другому с учетом весов ребер. Путь прокладывается таким образом, что очередная вершина выбирается случайно с вероятностью, зависящей от значений атрибутов ребер, исходящих из текущего узла.

    Решение


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

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

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

    n — количество общих друзей;
    xi — количество друзей у общего друга;
    yi — сумма входящих и исходящих сообщений между кандидатами через их общего друга

    Во втором решении мы сгенерировали 32 признака и обучили на них модель лог. регрессии и random forest.

    Модели из первого и второго решения объединяли с помощью еще одной логистической регрессии.

    В таблице описаны основные признаки, которые использовались во втором решении.
    признак описание
    weighted_commom Аналог коэффициента Адамик/Адара, но вместо логарифма использовали корень третьей степени
    conductivity_common Взвешиваем общих друзей с учетом проводимости сообщений. Чем меньше соотношение исходящих и входящих сообщений/звонков/документов общего друга, тем выше его вес при суммировании
    flow_common Оцениваем проходимость сообщений/звонков/документов между кандидатами через общего друга. Чем выше проходимость, тем больше вес при суммировании
    friends_jaccard Коэффициент Жаккарда для друзей кандидатов
    friend_company Похожесть на основе доли друзей пользователя из компании кандидата
    company_jaccard Оцениваем дружественность компаний кандидатов с помощью коэффициента Жаккарда (равен единице, если кандидаты из одной компании)


    Ниже в таблице приведены оценки качества как отдельно, так и результирующих моделей
    Модель F1 Точность Полнота
    Эмпирическая формула 0.064 0.059 0.069
    Лог регрессия 0.060 0.057 0.065
    Random forest 0.065 0.070 0.062
    Лог регрессия + Random Forest 0.066 0.070 0.063
    Лог регрессия + Random Forest + Эмпирическая формула 0.067 0.063 0.071

    Подбор порога


    Итак, модель обучена. Следующий шаг — это подбор порога для оптимизации приемочной метрики.

    В данной задаче мы оптимизировали метрику F1.

    Эта метрика одинаково чувствительна как к точности, так и к полноте и представляет собой гармоническое среднее этих величин.

    Т.к. зависимость метрики F1 от порога является выпуклой функцией, то поиск максимума не составляет большого труда.

    В данной задаче для подбора оптимального значения порога мы воспользовались алгоритмом бинарного поиска.

    Технологии


    Исходный граф был задан в виде списка ребер с указанием идентификаторов пользователей и соответствующими атрибутами. Всего в обучающей выборке было представлено 5.5 миллионов связей. Исходные данные предоставлены в виде текстового файла формата csv и занимают на жестком диске 163Мб.

    В рамках хакатона нам были предоставлены ресурсы облачного сервиса Azure по программе Microsoft BizSpark, в котором мы создали виртуальную машину для наших расчетов. Цена сервера в час составляла $0.2 и не зависела от интенсивности расчетов. Выделенного организаторами бюджета оказалось достаточно для решения данной задачи.

    Алгоритм поиска общих друзей мы реализовали на Spark, результаты промежуточных вычислений кешировали на диск в формате parquet, что позволило заметно сократить время чтения даных. Время работы алгоритма поиска общих друзей на виртуальной машине составило 8 часов. Кандидаты со списком общих друзей в формате parquet занимают 2.1Гб.

    Алгоритм обучения и подбора параметров модели реализован на python с использованием пакета scikit-learn. Процессы генерации признаков, обучения модели и подбора порога на виртуальном сервере суммарно заняли примерно 3 часа.

    В заключении хочется поблагодарить Брагина Ивана за активное участие в решение задачи и креативность в выборе эмпирической формулы.
    • +13
    • 14,4k
    • 4
    Поделиться публикацией
    Комментарии 4
      +5
      И где ссылка на репозиторий с реализацией?
        0
        Мы не ставили цель сделать продакшен решение в рамках хакатона. Основной процесс заключался в написании прототипов для быстрой проверки гипотез. Из-за того что скрипты для прототипов нужно было писать быстро, их код далек от того чтобы называться читаемым. Поэтому выкладывать в общий доступ особого смысла нет.
        0
        это, кстати, одна из значительных ошибок… довольно таки часто друзья моих друзей совершенно не мои друзья.
        Это просто разные круги общения. И даже скажу больше: может быть и несколько друзей, у которых есть общие друзья, при этом не являющиеся моими друзьями. Примеры можно привести, но у каждого они могут быть и так.

        В этом смысле Гугловые круги более точны в понимании идеи. Друзья друзей не обязательно друзья ине. Они просто из другого круга и в мой не входят.
          0
          Вы совершенно правы, факт наличия общего друга не является достаточным для того чтобы кандидаты были друзьями.
          Общих друзей мы используем для того чтобы сузить круг поиска кандидатов.

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

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