Прогноз появления рёбер

Есть такая задача — Link Prediction Problem, на русский язык нет однозначного перевода, но что-то типа «прогнозирование появления/исчезновения рёбер». В статическом варианте проблемы — дан граф (как правило, социальной сети), необходимо предсказать, какие рёбра в нём появятся в ближайшее время (и/или какие удалятся). В динамическом может быть дано несколько графов (в разные моменты времени) и прогноз может потребоваться на разные моменты времени. В варианте с фиксированным тестом — задано множество пар вершин, для которого нужно дать прогноз (например, какие из этих пар станут рёбрами). Из-за того, что чаще рассматривают графы соцсетей, возникает интересная терминология, например, смежные вершины называются друзьями, вершина, смежная с двумя другими вершинами, — их общим другом и т.д.

graph

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

Методы решения

Обычно задачу LPP сводят к стандартной задаче признаковой классификации/регрессии (в зависимости от того, нужен ли вам чёткий прогноз или вероятности появления рёбер). Признаки строятся для пар потенциальных вершин. Это простые признаки (степень вершины, коэффициент кластеризации и т.п.) или специальные:

  1. Длина кратчайшего пути между вершинами (ясно, что чем он меньше, тем скорее они соединятся ребром).
  2. Число общих друзей (= число путей длины 2 между вершинами, также ясно, что чем он больше, тем скорее вершины соединятся).
  3. Коэффициент Жаккара (отношение числа общих друзей двух вершин к числу всех друзей двух вершин — нормированный вариант предыдущего признака).
  4. Коэффициент Адамик/Адара — весовая сумма общих друзей, каждый общий друг берётся с весом «1/log(число его друзей)», т.е. дружба с теми, кто дружит не со всеми подряд, более ценная.
  5. Аналогично и число путей между вершинами можно вычислять по весовой схеме. Наиболее популярная — Katz.
  6. Признаки, основанные на случайных блужданиях. Устраивают случайные блуждания из одной вершины, вычисляют различные характеристики, связанные с попаданием во вторую (например, среднее число попаданий, при ограниченном времени блуждания).
  7. Рекурсивные признаки. Вершины близки (а все признаки здесь так или иначе формализуют понятие «близость») тогда и только тогда, когда близки их друзья. Поэтому можно пересчитывать близость вершин, основываясь на близости соседних.

Это классика, есть масса других подходов, например, основанных на матричной факторизации (матрицы смежности графа или её подматриц).

Статьи

Классическая работа с описанием этих признаков:

Liben-Nowell, D. and Kleinberg, J. The link-prediction problem for
social networks // Journal of the American Society for Information
Science and Technology, 58(7) 1019–1031 (2007).

Можно посмотреть мою небольшую работу про решение конкретной задачи LPP:

Дьяконов А.Г. Прогнозирование связности графа // Математические методы распознавания образов: 15-я Всероссийская конференция, г.Петрозаводск, 11–17 сентября 2011 г.: Сборник докладов. – М.: МАКС Пресс, 2011. С. 254-257.

Соревнования

Проводилось несколько соревнований по LPP:

Я сейчас сделал новое для своих магистров и ПЗАДовцев:

Если кто-то хочет попрактиковаться — приглашаю поучаствовать — данные очень простые, а в форуме уже есть код и отчёты моих магистров, так что начинаете не с нуля. Кстати, некоторые нужные функции для решения LPP есть в библиотечке NetworkX, но мне она очень не понравилась. Проще написать функции самому, поскольку в уже реализованных есть всякие ограничения (граф должен быть неориентирован, не иметь петель и т.п.)  Соревнование я подержу открытым до конца января.

П.С. У меня есть и слайды с картинками и формулами по теме — но я их пока не буду выкладывать в общий доступ.

Реклама

3 thoughts on “Прогноз появления рёбер

  1. Здравствуйте, Александр Геннадьевич!

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

    Заранее спасибо!

    • Вот именно с весами не скажу. А так, зависит от того, что Вы хотите в таком обзоре. Классика — это обзор Фортунато http://leonidzhukov.net/hse/2015/socialnetworks/papers/fortunato_review.pdf
      Там вроде есть и какие-то эксперименты, но статья больше «энциклопедичная».

      А так, чтобы взяли разные методы и погоняли на одинаковых задачах… вот выпускная работа моего студента http://www.machinelearning.ru/wiki/images/6/60/2015_417_SlavnovKA.pdf (см. с. 23) у него все методы из igraph взяты.

      Алгоритмы кластеризации, в принципе, редко сравнивают:)

      • Большое спасибо! Будем коллективом изучать статьи 🙂

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

        Пишу это на случай, если Вам известны ещё какие-нибудь полезные исследования.

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

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

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s