Label Propagation Algorithm¶

Label Propagation Algorithm (LPA) — это полуконтролируемый или неконтролируемый алгоритм машинного обучения, используемый для обнаружения сообществ (кластеризации) в графах, а также для классификации узлов на основе распространения меток. Алгоритм основан на принципе, что узлы в графе, имеющие схожие связи, с высокой вероятностью принадлежат к одной группе (сообществу), и метка группы может распространяться от узла к соседним узлам.

¶История

Алгоритм распространения меток (Label Propagation) был впервые предложен в 2002 году исследователями Чжу Сяоцзинем и Зубином Гафраманом для полуконтролируемого обучения. В 2007 году У. Н. Рагхаван, Р. Альберт и С. Кумара ввели модификацию алгоритма для неконтролируемого обнаружения сообществ в графах, известную как «алгоритм распространения меток для сообществ» (Community Label Propagation Algorithm). С тех пор LPA стал популярным методом в анализе социальных сетей, биоинформатике и рекомендательных системах благодаря своей простоте и масштабируемости.

¶Основные принципы

¶Полуконтролируемый LPA

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

¶Неконтролируемый LPA (для сообществ)

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

¶Алгоритм

¶Пошаговое описание (неконтролируемый вариант)

Инициализация: Каждому узлу $v$ присваивается уникальная метка $l_v$, например, $l_v = v$.
Итерация: Для каждого узла $v$ (в случайном порядке) обновляется его метка:

$l_v = \text{argmax}_{l} \sum_{u \in N(v)} \delta(l_u, l)$,

где $N(v)$ — множество соседей узла $v$, $\delta$ — функция Кронекера (равна 1, если метки совпадают, и 0 в противном случае). Если несколько меток имеют одинаковую максимальную частоту, выбирается одна из них случайным образом.

Проверка сходимости: Если метки всех узлов не изменились за текущую итерацию, алгоритм останавливается. В противном случае повторяется шаг 2.

¶Особенности

Случайность: Порядок обработки узлов и разрешение конфликтов при равных частотах меток вносят случайность, поэтому результат может варьироваться между запусками.
Скорость: Алгоритм имеет линейную сложность $O(m)$ по числу ребер $m$ на одну итерацию, что делает его пригодным для больших графов.
Сходимость: Алгоритм гарантированно сходится, но может зацикливаться в некоторых случаях (например, в двудольных графах). Для предотвращения зацикливания часто вводят ограничение на максимальное число итераций или используют модификации, такие как асинхронное обновление.

¶Применение

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

¶Классификация узлов в графах

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

¶Биоинформатика

В анализе биологических сетей (например, белок-белковых взаимодействий) LPA используется для выявления функциональных модулей или групп генов, связанных с определенными заболеваниями.

¶Обработка текстов

LPA может применяться для кластеризации документов или терминов на основе их совместной встречаемости в текстах, что полезно для построения тематических моделей.

¶Преимущества и недостатки

¶Преимущества

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

¶Недостатки

Нестабильность: Результат может сильно варьироваться из-за случайности выбора меток при конфликтах.
Склонность к образованию одного большого сообщества: Алгоритм может объединять все узлы в одно сообщество, если граф плотный.
Зацикливание: В некоторых структурах графа (например, двудольных) алгоритм может не сходиться.
Нет гарантии оптимальности: Результат не обязательно является оптимальным с точки зрения качества сообществ.

¶Модификации

¶Асинхронный LPA (ALPA)

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

¶LPA с весами

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

¶LPA с ограничениями

Для предотвращения образования одного большого сообщества вводятся ограничения, например, на размер сообщества или на количество итераций.

¶LPA с полуконтролем

В полуконтролируемом варианте метки части узлов фиксируются и не изменяются в процессе алгоритма.

¶Пример

Рассмотрим простой граф с 5 узлами: A — B — C — D — E (линейная цепочка). Инициализация: метки A, B, C, D, E. Первая итерация (порядок: A, B, C, D, E):

A: соседи — B. Метка B. Новая метка A = B.
B: соседи — A (метка B) и C (метка C). Частота: B=1, C=1. Выбираем случайно, например, B. Новая метка B = B.
C: соседи — B (метка B) и D (метка D). Частота: B=1, D=1. Выбираем случайно, например, B. Новая метка C = B.
D: соседи — C (метка B) и E (метка E). Частота: B=1, E=1. Выбираем случайно, например, B. Новая метка D = B.
E: соседи — D (метка B). Новая метка E = B.

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

¶Интересные факты

Алгоритм распространения меток вдохновлен процессами распространения информации в социальных сетях, где люди перенимают мнения или поведение от своих знакомых.
LPA является одним из немногих алгоритмов обнаружения сообществ, который не требует предварительного задания числа сообществ.
В 2015 году была предложена модификация LPA, называемая «Speaker-listener Label Propagation Algorithm» (SLPA), которая позволяет обнаруживать перекрывающиеся сообщества (узлы могут принадлежать нескольким сообществам).

¶Источники

Zhu, X., & Ghahramani, Z. (2002). Learning from labeled and unlabeled data with label propagation. Technical Report CMU-CALD-02-107, Carnegie Mellon University.
Raghavan, U. N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3), 036106.
Xie, J., Szymanski, B. K., & Liu, X. (2011). SLPA: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. IEEE 11th International Conference on Data Mining Workshops.

Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru