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

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

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


Содержание

Введение

Алгоритм Лувена (англ. 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:

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

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

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

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

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

Литература


Источник — «http://www.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»