Алгоритм Лувена для обнаружения сообществ (Louvain Method)

Материал из MachineLearning.

(Различия между версиями)

Перейти к: навигация, поиск

Текущая версия

Статья написана с использованием LLM Qwen3.7-Plus и проверена участником Mariia Shubina 10:22, 19 июля 2026 (MSD)

Содержание

1 Введение
2 Постановка задачи и математические основы
3 Фазы алгоритма Лувена
- 3.1 Фаза 1: Локальная оптимизация
- 3.2 Фаза 2: Агрегация графа
4 Псевдокод и вычислительная сложность
- 4.1 Псевдокод
- 4.2 Анализ вычислительной сложности
5 Проблема предела разрешения
- 5.1 Параметр разрешения
6 Сравнение с другими методами
7 Ограничения метода
8 Варианты и расширения
9 Литература

Введение

Алгоритм Лувена (англ. Louvain method) — это эвристический метод для обнаружения сообществ в больших сетях, основанный на жадной оптимизации модулярности. Впервые предложенный в 2008 году Венсаном Блонделем и его коллегами, алгоритм получил широкое распространение благодаря своей вычислительной эффективности и способности выявлять иерархическую структуру в графах, содержащих миллионы вершин и рёбер^[1].

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

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

Формальная постановка задачи

Пусть дан неориентированный взвешенный граф $G = (V, E)$ , где $V$ — множество вершин ( $|V| = N$ ), а $E$ — множество рёбер ( $|E| = M$ ). Граф описывается матрицей смежности $A$ , где элемент $A_{ij}$ представляет собой вес ребра между вершинами $i$ и $j$ (для невзвешенных графов $A_{ij} \in \{0, 1\}$ ). Степень вершины $i$ обозначается как $k_i = \sum_j A_{ij}$ , а общий вес всех рёбер в графе равен $2m = \sum_{i,j} A_{ij}$ .

Задача обнаружения сообществ заключается в разбиении множества вершин $V$ на непересекающиеся подмножества (сообщества) $C = \{c_1, c_2, \dots, c_k\}$ таким образом, чтобы связи внутри сообществ были значительно плотнее, чем связи между различными сообществами.

Модулярность Ньюмана-Гирвана

Ключевой метрикой качества разбиения в алгоритме Лувена является модулярность $Q$ , предложенная Ньюманом и Гирваном. Модулярность измеряет разность между долей рёбер внутри сообществ и математическим ожиданием этой доли в нулевой модели (модели конфигураций), которая сохраняет распределение степеней вершин, но соединяет их случайным образом.

Формула модулярности имеет вид:

$Q = \frac{1}{2m} \sum_{i,j} \left[ A_{ij} - \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)$

где $\delta(c_i, c_j) = 1$ , если вершины $i$ и $j$ принадлежат одному сообществу, и $0$ в противном случае. Слагаемое $\frac{k_i k_j}{2m}$ представляет собой вероятность наличия ребра между $i$ и $j$ в модели конфигураций. Максимально возможное значение $Q$ близко к 1, хотя на практике для реальных сетей значения выше 0.3–0.7 уже свидетельствуют о выраженной модульной структуре.

Приращение модулярности при перемещении узла

Основная вычислительная идея алгоритма заключается в эффективном расчёте изменения модулярности $\Delta Q$ при перемещении вершины $i$ из её текущего сообщества в соседнее сообщество $C$ .

Пусть $\Sigma_{in}$ — сумма весов рёбер внутри сообщества $C$ , а $\Sigma_{tot}$ — сумма весов всех рёбер, инцидентных вершинам сообщества $C$ . Обозначим через $k_{i,in}$ сумму весов рёбер между вершиной $i$ и вершинами сообщества $C$ .

Приращение модулярности при добавлении вершины $i$ в сообщество $C$ вычисляется как разность модулярности после и до перемещения:

$\Delta Q = \left[ \frac{\Sigma_{in} + 2k_{i,in}}{2m} - \left( \frac{\Sigma_{tot} + k_i}{2m} \right)^2 \right] - \left[ \frac{\Sigma_{in}}{2m} - \left( \frac{\Sigma_{tot}}{2m} \right)^2 - \left( \frac{k_i}{2m} \right)^2 \right]$

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

$\Delta Q = \frac{k_{i,in}}{m} - \frac{\Sigma_{tot} k_i}{2m^2}$

Аналогичная формула применяется для расчёта выигрыша при удалении вершины из сообщества (с заменой $k_{i,in}$ на сумму весов рёбер к сообществу без учёта самой вершины, а $\Sigma_{tot}$ на сумму без учёта степени вершины).

Фазы алгоритма Лувена

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

Фаза 1: Локальная оптимизация

На начальном этапе каждая вершина графа выделяется в собственное уникальное сообщество. Далее алгоритм выполняет следующие действия для каждой вершины $i$ :

Рассматриваются все соседние сообщества вершины $i$ .
Для каждого соседнего сообщества вычисляется $\Delta Q$ , которое получилось бы при перемещении $i$ в это сообщество.
Вершина $i$ перемещается в то сообщество, которое обеспечивает максимальный положительный прирост $\Delta Q > 0$ . Если ни одно перемещение не даёт положительного прироста, вершина остаётся в своём текущем сообществе.
Процесс повторяется для всех вершин графа в определённом порядке до тех пор, пока за полный проход не будет сделано ни одного перемещения (достигнут локальный максимум модулярности).

Фаза 2: Агрегация графа

После завершения первой фазы строится новый, агрегированный граф:

Каждое найденное сообщество становится новой супервершиной.
Вес ребра между двумя супервершинами равен сумме весов всех рёбер между вершинами соответствующих сообществ в исходном графе.
Ребра, соединяющие вершины внутри одного сообщества, превращаются в петли (self-loops) супервершины, вес которых равен сумме внутренних рёбер сообщества.

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

Псевдокод и вычислительная сложность

Псевдокод

Вход: Граф G = (V, E) с весами рёбер A_ij
Выход: Разбиение вершин на сообщества

1. Инициализация: присвоить каждой вершине i уникальное сообщество c_i = i
2. Повторять:
3.    изменения = ложь
4.    Для каждой вершины i в V (в случайном или фиксированном порядке):
5.        удалить i из текущего сообщества
6.        найти сообщество C, максимизирующее \Delta Q при добавлении i в C
7.        если максимальное \Delta Q > 0:
8.            переместить i в C
9.            изменения = истина
10.   если не изменения: прервать цикл (Фаза 1 завершена)
11. Построить агрегированный граф G' из найденных сообществ
12. Если G' идентичен графу предыдущей итерации:
13.    завершить алгоритм
14. Иначе:
15.    G = G'
16.    перейти к шагу 2 (начать новую итерацию для агрегированного графа)

Анализ вычислительной сложности

Время: Вычисление $\Delta Q$ для одной вершины требует знания только степеней и сумм весов рёбер соседних сообществ, что при правильной поддержке структур данных (например, хеш-таблиц для $\Sigma_{tot}$ и $k_{i,in}$ ) выполняется за время, пропорциональное степени вершины $O(k_i)$ . Полный проход по всем вершинам занимает время $O(M)$ . На практике алгоритм сходится за небольшое число проходов (обычно 2–5), а количество уровней иерархической агрегации логарифмически мало. Таким образом, общая временная сложность оценивается как $O(M \log N)$ или даже $O(N + M)$ для разреженных графов, что делает метод одним из самых быстрых.
Память: Требуется хранение исходного графа, структур для отслеживания сообществ и агрегированных графов на каждом уровне. Пространственная сложность составляет $O(N + M)$ , что позволяет обрабатывать графы с десятками миллионов рёбер на стандартном оборудовании.

Проблема предела разрешения

Одним из фундаментальных ограничений оптимизации модулярности является так называемый предел разрешения (resolution limit), впервые описанный Фортунато и Бартелеми в 2007 году^[1].

Модулярность сравнивает фактическое число рёбер с математическим ожиданием в модели конфигураций. В очень больших сетях ( $m$ велико) ожидаемое число рёбер между двумя небольшими, но внутренне плотными сообществами может быть меньше 1. В результате объединение этих двух сообществ в одно формально увеличивает значение $Q$ , даже если они структурно обособлены. Алгоритм Лувена, максимизируя $Q$ , неизбежно сольёт такие мелкие сообщества, не позволяя обнаружить мелкомасштабную структуру.

Параметр разрешения $\gamma$

Для решения этой проблемы вводится параметр разрешения $\gamma$ , модифицирующий формулу модулярности:

$Q_\gamma = \frac{1}{2m} \sum_{i,j} \left[ A_{ij} - \gamma \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)$

При $\gamma = 1$ мы получаем классическую модулярность.
При $\gamma > 1$ штраф за объединение сообществ увеличивается, что способствует обнаружению меньших и более плотных сообществ.
При $\gamma < 1$ алгоритм склонен формировать более крупные, укрупнённые сообщества.

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

Сравнение с другими методами

Спектральная кластеризация: основана на поиске собственных векторов матрицы Лапласа графа. Обладает строгими теоретическими гарантиями, но имеет временную сложность $O(N^3)$ , что делает её неприменимой для больших сетей без использования аппроксимаций (например, метода Нистрома).
Алгоритм Гирвана-Ньюмана: иерархический метод, удаляющий рёбра с наибольшей промежуточностью (betweenness centrality). Имеет сложность $O(N M^2)$ или $O(N^3)$ для разреженных графов, что также ограничивает его применение малыми сетями, несмотря на высокую интерпретируемость.
Распространение меток (Label Propagation): работает за время $O(N + M)$ , передавая метки соседям. Чрезвычайно быстр, но сильно недетерминирован и склонен к формированию одного гигантского сообщества (так называемого "monster community"), поглощающего большую часть графа.
Алгоритм Лейден (Leiden algorithm): прямой современный преемник алгоритма Лувена, предложенный Траагом и др. в 2019 году^[1]. Он добавляет фазу рафинирования (refinement) между локальной оптимизацией и агрегацией, что гарантирует связность всех выделяемых сообществ и часто приводит к более высоким значениям модулярности при сопоставимой вычислительной стоимости.

Ограничения метода

Несмотря на популярность, классический алгоритм Лувена имеет ряд существенных ограничений:

Недетерминированность: Результат зависит от порядка обхода вершин на Фазе 1. Разные порядки могут приводить к различным локальным оптимумам модулярности.
Риск застревания в локальных оптимумах: Жадный характер перемещения вершин не гарантирует нахождения глобального максимума $Q$ . Сообщества, однажды объединённые на ранних этапах агрегации, не могут быть разделены на последующих уровнях (проблема "необратимости агрегации").
Несвязные сообщества: Из-за механизма агрегации супервершина на верхнем уровне может соответствовать набору вершин в исходном графе, которые не имеют путей связи друг с другом внутри этого сообщества. Это топологический артефакт, который нарушает интуитивное определение сообщества как связного подграфа.

Варианты и расширения

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

Динамический (инкрементальный) Лувен: адаптирован для временных графов. Вместо полного перезапуска алгоритма при добавлении или удалении рёбер пересчитываются только значения $\Delta Q$ для затронутых вершин и их соседей, что обеспечивает почти постоянное время обновления.
Многоуровневое рафинирование: техники, при которых после завершения агрегации алгоритм "спускается" обратно к исходному графу, используя найденное разбиение как начальное приближение для повторной локальной оптимизации, что помогает выйти из локальных оптимумов.
Глубокие методы кластеризации графов (GNN): современные подходы, такие как Graph Autoencoders или методы на основе контрастивного обучения, не максимизируют модулярность напрямую, а обучают векторные представления вершин, сохраняя топологию. Они принципиально отличаются от Лувена, так как являются параметрическими и требуют обучения, но часто превосходят эвристические методы в задачах с богатыми признаками вершин.

Литература

Blondel V. D., Guillaume J. L., Lambiotte R., Lefebvre E. Fast unfolding of communities in large networks // Journal of Statistical Mechanics: Theory and Experiment: Журнал. — 2008. — Т. 2008. — № 10. — С. P10008.
Traag V. A., Waltman L., van Eck N. J. From Louvain to Leiden: guaranteeing well-connected communities // Scientific Reports: Журнал. — 2019. — Т. 9. — № 1. — С. 5233.
Fortunato S., Barthelemy M. Resolution limit in community detection // Proceedings of the National Academy of Sciences: Журнал. — 2007. — Т. 104. — № 1. — С. 36-41.
Newman M. E. J. Networks: An Introduction. — Oxford University Press, 2010. — 754 с.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9B%D1%83%D0%B2%D0%B5%D0%BD%D0%B0_%D0%B4%D0%BB%D1%8F_%D0%BE%D0%B1%D0%BD%D0%B0%D1%80%D1%83%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D1%81%D0%BE%D0%BE%D0%B1%D1%89%D0%B5%D1%81%D1%82%D0%B2_%28Louvain_Method%29»

Категории: Анализ графов | Обнаружение сообществ | Машинное обучение | Энциклопедия анализа данных | Кластеризация