Алгоритм Лувена для обнаружения сообществ (Louvain Method)
Материал из MachineLearning.
| Статья написана с использованием LLM Qwen3.7-Plus и проверена участником Mariia Shubina 10:52, 19 июля 2026 (MSD) |
|
Введение
Алгоритм Лувена (англ. Louvain Method) — это быстрый эвристический метод для обнаружения сообществ в больших сетях, основанный на жадной оптимизации модулярности графа. Метод был предложен в 2008 году исследователями из Католического университета Лувена (Бельгия) и стал одним из наиболее широко применяемых подходов в анализе графов благодаря своей высокой вычислительной эффективности и способности выявлять иерархическую структуру сообществ. Алгоритм не требует априорного знания числа сообществ и масштабируется на графы с миллионами вершин и рёбер, что делает его стандартом де-факто для задач кластеризации сетей в социальных науках, биоинформатике и рекомендательных системах.
Формальная постановка задачи и интуиция
Задача обнаружения сообществ заключается в разбиении множества вершин графа V V на непересекающиеся подмножества (сообщества) C 1 , C 2 , … , C k C 1
,C
2
,…,C
k
таким образом, чтобы связи внутри сообществ были значительно плотнее, чем связи между различными сообществами.
В основе алгоритма Лувена лежит понятие модулярности Q Q, введённое Ньюманом и Гирваном. Модулярность измеряет разницу между долей рёбер внутри сообществ в реальной сети и ожидаемой долей таких рёбер в эталонной случайной сети (модель конфигураций) с тем же распределением степеней вершин. Для взвешенного графа с матрицей весов w i j w ij
модулярность определяется как:
где: m = 1 2 ∑ i , j w i j m= 2 1
∑
i,j
w
ij
— суммарный вес всех рёбер в графе;
k i = ∑ j w i j k i
=∑
j
w
ij
— взвешенная степень вершины
i i; c i c i
— индекс сообщества, к которому принадлежит вершина
i i; δ ( c i , c j ) δ(c i
,c
j
) — символ Кронекера, равный 1, если
c i = c j c i
=c
j
, и 0 в противном случае.
Интуиция метода заключается в итеративном локальном улучшении разбиения: алгоритм перемещает вершины между сообществами, если это увеличивает общую модулярность, а затем агрегирует найденные сообщества в супервершины, повторяя процесс на более высоком уровне абстракции.
Математическое обоснование и алгоритм
Алгоритм состоит из двух чередующихся фаз, которые повторяются до тех пор, пока модулярность не перестанет расти.
Фаза 1: Локальное перемещение вершин
Изначально каждая вершина графа рассматривается как отдельное сообщество. Алгоритм последовательно перебирает все вершины i i. Для каждой вершины i i оценивается изменение модулярности Δ Q ΔQ, которое произойдёт при удалении i i из её текущего сообщества и добавлении её в сообщество одной из её соседних вершин. При перемещении вершины i i в сообщество C C изменение модулярности вычисляется по формуле:
где: Σ i n Σ in
— сумма весов рёбер внутри сообщества
C C; Σ t o t Σ tot
— сумма весов всех рёбер, инцидентных вершинам сообщества
C C; k i , i n k i,in
— сумма весов рёбер между вершиной
i i и вершинами сообщества C C; k i k i
— степень вершины
i i. Вершина i i перемещается в то сообщество соседа, которое обеспечивает максимальное положительное значение Δ Q ΔQ. Если все возможные перемещения приводят к Δ Q ≤ 0 ΔQ≤0, вершина остаётся в своём текущем сообществе. Процесс повторяется обходом всех вершин до тех пор, пока не будет достигнуто состояние локального оптимума (ни одно перемещение не увеличивает Q Q).
Фаза 2: Агрегация графа
После достижения локального оптимума строится новый укрупнённый граф: Каждое сообщество, найденное на Фазе 1, становится новой супервершиной. Вес ребра между двумя супервершинами равен сумме весов всех рёбер между вершинами соответствующих сообществ в исходном графе. Вес петли (self-loop) супервершины равен сумме весов всех рёбер, соединяющих вершины внутри данного сообщества. Полученный граф передаётся на вход Фазы 1. Две фазы повторяются итеративно, формируя иерархию сообществ, до тех пор, пока модулярность не перестанет увеличиваться или граф не схлопнется в одну вершину.
Вычислительная сложность
Время: В худшем случае сложность составляет O ( N log N ) O(NlogN) для разреженных графов, где N N — число вершин. На практике алгоритм работает почти за линейное время O ( N + M ) O(N+M), где M M — число рёбер, благодаря тому, что на каждом последующем уровне агрегации размер графа экспоненциально уменьшается, а пересчёт Δ Q ΔQ выполняется только для локальных окрестностей. Память: Требуется O ( N + M ) O(N+M) для хранения структуры графа и текущих назначений сообществ. Матрица смежности в явном виде не строится, используются списки смежности.
Проблема предела разрешения
Одним из фундаментальных ограничений оптимизации модулярности является проблема предела разрешения (Resolution Limit), впервые описанная Фортунато и Бартелеми. Модулярность содержит глобальный масштабный параметр (общее число рёбер 2 m 2m), из-за чего в больших сетях метод систематически объединяет небольшие, но структурно чётко выраженные сообщества в более крупные кластеры. Математически два сообщества могут быть несправедливо объединены, если суммарное число рёбер между ними превышает ожидаемое число рёбер в случайном графе, даже если внутренняя связность этих сообществ высока. Это делает классический алгоритм Лувена менее пригодным для обнаружения мелких сообществ в гигантских сетях без дополнительной модификации (например, введения параметра разрешения γ γ).
Сравнение с другими методами
Спектральная кластеризация: Обеспечивает строгие теоретические гарантии и хорошо работает на графах среднего размера, но требует вычисления собственных векторов матрицы Лапласа, что имеет сложность O ( N 3 ) O(N 3
) и неприменимо для больших сетей.
Алгоритм Гирвана-Ньюмана: Иерархический дивизивный метод, удаляющий рёбра с наибольшей промежуточностью (betweenness). Точен, но имеет сложность O ( N 3 ) O(N 3
), что делает его крайне медленным.
Распространение меток (Label Propagation): Работает за O ( M ) O(M) и крайне быстр, но часто сходится к тривиальным решениям (одно гигантское сообщество) и обладает высокой стохастичностью. Алгоритм Лейден: Прямой преемник алгоритма Лувена. Исправляет главный структурный недостаток Лувена — возможность формирования несвязных (disconnected) сообществ на этапе агрегации, гарантируя, что все найденные сообщества являются слабо связными.
Ограничения метода
Несвязные сообщества: Из-за жадного характера Фазы 1 и агрегации Фазы 2, алгоритм может сформировать сообщество, внутренние вершины которого не имеют путей друг к другу (разрывные сообщества). Недетерминированность: Результат зависит от порядка обхода вершин на Фазе 1. Разные запуски на одном и том же графе могут давать слегка различающиеся разбиения с близкими значениями модулярности. Локальные оптимумы: Жадная эвристика не гарантирует нахождение глобального максимума модулярности. Предел разрешения: Невозможность выявить мелкие сообщества в крупных графах без модификации функции оптимизации.
Варианты и расширения
Модифицированная модулярность: Введение параметра разрешения γ γ в формулу модулярности ( Q γ = 1 2 m ∑ i , j [ w i j − γ k i k j 2 m ] δ ( c i , c j ) Q γ
=
2m 1
∑
i,j
[w
ij
−γ
2m k i
k
j
]δ(c
i
,c
j
)) позволяет контролировать масштаб обнаруживаемых сообществ.
Динамический (инкрементальный) Лувен: Методы, позволяющие обновлять разбиение графа при добавлении или удалении рёбер без полного перезапуска алгоритма, что критично для анализа временных сетей. Алгоритм Лейден: Современный стандарт, заменяющий Лувен в большинстве библиотек. Добавляет фазу "рафинирования" (refinement) между перемещением и агрегацией, что устраняет проблему несвязных сообществ и часто приводит к более высокому значению модулярности.
Литература
Ошибка цитирования Входные данные недействительны, так как не предполагаются
