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

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

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

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

Обычно задачу 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:

• На Кэгле — IJCNN Social Network Challenge
• На АлгоМосту  — Развитие динамического графа социальной сети

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

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

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

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