Метод Лувена

Часть серии статей о
Сетевая наука
Теория
График Сложная сеть Заражение Маленький мир Без чешуи Структура сообщества Перколяция Эволюция Управляемость Графическое изображение Социальный капитал Анализ ссылок Оптимизация Взаимность Закрытие Гомофилия Транзитивность Преимущественное присоединение Теория равновесия Сетевой эффект Социальное влияние
Типы сетей
Информационный (вычислительный) Телекоммуникации Транспорт Социальный Научное сотрудничество Биологический Искусственная нейронная сеть Взаимозависимый Семантический Пространственный Зависимость Поток на чипе
Графики
Функции Клика Компонент Резать Цикл Структура данных Край Петля Район Путь Вершина Список смежности  / матрица Список  / матрица заболеваемости Типы Двудольный Полный Направленный Гипер Помечено Мульти Случайный Взвешенный
Метрики Алгоритмы
Центральность Степень Мотив Кластеризация Распределение степеней Ассортативность Расстояние Модульность Эффективность
Модели
Топология Случайный график Эрдёш–Реньи Барабаши–Альберт Бьянкони–Барабаши Фитнес-модель Уоттс-Строгац Экспоненциальный случайный (ERGM) Случайный геометрический (RGG) Гиперболический (HGN) Иерархический Стохастический блок Блочное моделирование Максимальная энтропия Мягкая конфигурация LFR-бенчмарк Динамика Булева сеть на основе агента Эпидемия / SIR
Списки Категории
Темы Программное обеспечение Network scientists Category:Network theory Category:Graph theory
v t e

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

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

В методе обнаружения сообществ Лувена сначала находятся небольшие сообщества путем оптимизации модульности локально на всех узлах, затем каждое небольшое сообщество группируется в один узел, и первый шаг повторяется. Метод похож на более ранний метод Клаузета, Ньюмена и Мура ^[2] , который соединяет сообщества, объединение которых дает наибольшее увеличение модульности. Было показано, что алгоритм Лувена правильно определяет структуру сообщества, когда она существует, в частности, в стохастической блочной модели. ^[3]

Значение, которое необходимо оптимизировать, — это модульность , определяемая как значение в диапазоне , который измеряет плотность связей внутри сообществ по сравнению со связями между сообществами. ^[1] Для взвешенного графа модульность определяется как:${\displaystyle [-1,1]}$

$${\displaystyle Q={\frac {1}{2m}}\sum _{i=1}^{N}\sum _{j=1}^{N}{\bigg [}A_{ij}-{\frac {k_{i}k_{j}}{2m}}{\bigg ]}\delta (c_{i},c_{j}),}$$

где:

• ${\displaystyle A_{ij}}$представляет собой вес ребра между узлами i и j ; см. Матрица смежности ;
• ⁠ ⁠${\displaystyle k_{i}}$ и ⁠ ⁠${\displaystyle k_{j}}$ — сумма весов ребер, прикрепленных к узлам i и j соответственно;
• m — сумма весов всех ребер в графе;
• N — общее количество узлов в графе;
• ⁠ ⁠${\displaystyle c_{i}}$ и ⁠ ⁠${\displaystyle c_{j}}$ — сообщества, к которым принадлежат узлы i и j ; и
• ${\displaystyle \delta }$— это дельта-функция Кронекера :

$${\displaystyle {\begin{aligned}\delta (c_{i},c_{j})&={\begin{cases}1&{\text{if }}c_{i}{\text{ and }}c_{j}{\text{ are the same cluster}}\\0&{\text{otherwise}}\end{cases}}\end{aligned}}}$$

На основе приведенного выше уравнения модульность сообщества c можно рассчитать следующим образом: ^[4]

$${\displaystyle {\begin{aligned}Q_{c}&={\dfrac {1}{2m}}\sum _{i}\sum _{j}A_{ij}\mathbf {1} \left\{c_{i}=c_{j}=c\right\}-\left(\sum _{i}{\dfrac {k_{i}}{2m}}\mathbf {1} \left\{c_{i}=c\right\}\right)^{2}\\&={\frac {\Sigma _{in}}{2m}}-\left({\frac {\Sigma _{tot}}{2m}}\right)^{2}\end{aligned}}}$$

где

• ${\displaystyle \Sigma _{in}}$— сумма весов ребер между узлами внутри сообщества c (каждое ребро рассматривается дважды); и
• ${\displaystyle \Sigma _{tot}}$представляет собой сумму всех весов ребер для узлов внутри сообщества (включая ребра, которые связаны с другими сообществами).

Поскольку узлы в разных сообществах не вносят вклад в модульность Q , ее можно записать как:

$${\displaystyle Q=\sum _{c}Q_{c}}$$

Метод Лувена работает путем повторения двух фаз. ^[1] На первой фазе узлы сортируются в сообщества на основе того, как изменяется модульность графа, когда узел перемещает сообщества. На второй фазе граф переосмысливается таким образом, что сообщества рассматриваются как отдельные узлы. Подробное объяснение приведено ниже.

Метод Лувена начинается с рассмотрения каждого узла v в графе как его собственного сообщества. Это можно увидеть на рисунке 1, где каждая точка (представляющая узлы) имеет уникальный цвет (представляющий, к какому сообществу принадлежит узел).

Для каждого узла v мы рассматриваем, как перемещение v из его текущего сообщества C в соседнее сообщество C' повлияет на модульность разбиения графа. В псевдокоде ниже это происходит в цикле for. Мы выбираем сообщество C' с наибольшим изменением модульности, и если изменение положительное, мы перемещаем v в C' ; в противном случае мы оставляем его там, где он есть. Это продолжается до тех пор, пока модульность не перестанет улучшаться.

функция moveNodes(граф G, раздел P): делать  старая_модульность <- текущая_модульность_раздела для v в V(G), сделать # найти сообщество, которое вызывает наибольшее увеличение модульности при перемещении в него v C' <- argmax(delta_Q) # delta_Q — это изменение модульности если delta_Q > 0, то переместить v в C' конец, если  конец для обновить текущую_модульность_раздела пока текущая_модульность_раздела > старая_модульность возврат P конечная функция

^[5]

Этот процесс применяется многократно и последовательно ко всем узлам до тех пор, пока не может произойти никакого увеличения модульности. Как только достигается этот локальный максимум модульности, первая фаза заканчивается. На рисунке 2 показано, как может выглядеть график на рисунке 1 после одной итерации фазы 1.

Для каждого сообщества в разделе нашего графа отдельные узлы, составляющие это сообщество, объединяются, и само сообщество становится узлом. Ребра, соединяющие отдельные сообщества, используются для взвешивания новых ребер, соединяющих наши агрегированные узлы.

Этот процесс моделируется в псевдокоде, где функцияgregateGraph возвращает новый граф, вершины которого являются разбиением старого графа, а ребра вычисляются с использованием старого графа. Эта функция не показывает, что ребра взвешиваются, но простая модификация позволит отслеживать эту информацию.

функция агрегатГраф(Граф G, Раздел P): В <- П  E <- [(A,B) | (x,y) находится в E(G), x находится в A и A находится в P, y находится в B и B находится в P] возвратить График(V,E)конечная функция

^[5]

Рисунок 3 показывает, как будет выглядеть график из рисунка 2 после агрегации. Этот график аналогичен графику на рисунке 1 в том смысле, что каждый узел назначен одному сообществу. Отсюда процесс можно повторять, чтобы больше узлов перемещалось в существующие сообщества, пока не будет достигнут оптимальный уровень модульности.

Приведенный ниже псевдокод показывает, как предыдущие две функции работают вместе, завершая процесс.

функция louvain(график G, раздел P): делать P <- moveNodes(G, P) done <- length(P) == length(V(G)) # каждое сообщество — это один узел, несмотря на запущенный moveNodes если этого не сделано, то: G <- агрегатГрафик(G, P) P <- singletonPartition(G) конец, если пока не сделаноконечная функцияфункция singletonPartition(Graph G): return [{v} | v находится в V(G)] # каждый узел помещается в свое собственное сообществоконечная функция

^[5]

В общем случае предполагается, что метод Лувена имеет временную сложность . Ричард Блондель, соавтор статьи, в которой изначально был опубликован метод Лувена, похоже, поддерживает эту идею ^[6], но другие источники утверждают, что временная сложность «по существу линейна по числу связей в графе», ^[7] что означает, что временная сложность вместо этого будет , где m — число ребер в графе. К сожалению, ни один источник не опубликовал анализ временной сложности метода Лувена, поэтому здесь мы попытаемся сделать это.${\displaystyle O(n\log {}n)}$${\displaystyle O(m)}$

В псевдокоде выше функция louvain управляет выполнением алгоритма. Ясно видно, что внутри louvain moveNodes будет повторяться до тех пор, пока не станет возможным объединять узлы в сообщества. Это зависит от двух факторов: насколько может улучшиться модульность графа и, в худшем случае, если модульность может улучшиться с каждой итерацией louvain , это зависит от того , насколько быстроgregateGraph сократит граф до одного узла.

Если в каждой итерации louvain , moveNodes может переместить только один узел в сообщество, тоgregateGraph сможет уменьшить размер графа только на один. Это приведет к тому, что louvain повторится v раз. Поскольку moveNodes проходит по всем узлам в графе, это приведет к временной сложности , где n — количество узлов.${\displaystyle {\mathcal {O}}(n^{2})}$

Неясно, возможна ли такая ситуация, поэтому приведенный выше результат следует считать слабой границей. Блондель и др. в своей оригинальной публикации заявляют, что большая часть времени выполнения тратится на ранние итерации алгоритма, поскольку «количество сообществ резко уменьшается уже после нескольких проходов». ^[1] Это можно понять, рассмотрев сценарий, в котором moveNodes может перемещать каждый узел так, чтобы каждое сообщество имело два узла. В этом случаеgregateGraph вернет граф в два раза меньше исходного. Если бы это продолжалось, то метод Лувена имел бы время выполнения , хотя неясно, будет ли это наихудшим случаем, лучшим случаем, средним случаем или ни одним из них. Кроме того, нет гарантии, что размер графа будет уменьшаться в том же размере с каждой итерацией, и поэтому ни одна функция логарифма не может идеально описать временную сложность.${\displaystyle n\log _{2}{n}}$

• Социальная сеть Twitter (2,4 миллиона узлов, 38 миллионов ссылок) Хосепа Пухоля, Виджая Эррамилли и Пабло Родригеса: ^[8] Авторы исследуют проблему разбиения онлайн-социальных сетей на разные машины.
• Сеть мобильной связи (4 миллиона узлов, 100 миллионов ссылок) Дерека Грина, Донала Дойла и Падрейга Каннингема: ^[9] Стратегии отслеживания сообществ для выявления динамических сообществ в различных динамических социальных сетях.
• Обнаружение видов в сетевой динамической модели. ^[10]

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

Худшим примером произвольно плохо связанного сообщества является внутренне разъединенное сообщество. Внутренне разъединенное сообщество возникает с помощью алгоритма Лувена, когда узел, который действовал как «мост» между двумя группами узлов в своем сообществе, перемещается в новое сообщество, оставляя старое разъединенным. Оставшиеся узлы в старом сообществе также могут быть перемещены, но если их связь с сообществом достаточно сильна, несмотря на удаление узла «мост», они вместо этого останутся на месте. Пример этого см. на изображении справа; обратите внимание, как удаление узла-моста, узла 0, привело к разделению красного сообщества на две непересекающиеся подгруппы. Хотя это наихудший сценарий, существуют и другие, более тонкие проблемы с алгоритмом Лувена, которые также могут привести к произвольно плохо связанным сообществам, например, формирование сообществ с использованием узлов, которые связаны только слабо.

Другая распространенная проблема с алгоритмом Лувена — это предел разрешения модульности , то есть несколько небольших сообществ, сгруппированных вместе в более крупное сообщество. Это приводит к тому, что более мелкие сообщества скрываются; в качестве примера см. визуальное изображение предела разрешения справа. Обратите внимание, как, когда зеленое сообщество поглощается синим сообществом для увеличения модульности графа, меньшая группа узлов, которую оно представляло, теряется. Больше нет способа отличить эти узлы от узлов, которые уже были в синем сообществе. И наоборот, узлы, которые уже были в синем сообществе, больше не кажутся отличными от тех, которые были в зеленом сообществе; другими словами, любое различие, которое изначально заставило их разместиться в отдельных сообществах, было скрыто.

И предел разрешения модульности, и проблема произвольно плохо связанного сообщества еще больше усугубляются с каждой итерацией алгоритма. В конечном счете, единственное, что гарантирует алгоритм Лувена, это то, что полученные сообщества не могут быть объединены далее; другими словами, они хорошо разделены. Чтобы избежать проблем, возникающих из произвольно плохо связанных сообществ и предела разрешения модульности, рекомендуется использовать вместо этого алгоритм Лейдена , поскольку его фаза уточнения и другие различные корректировки исправили эти проблемы. ^[5]

При сравнении методов оптимизации модульности двумя важными показателями являются скорость и результирующее значение модульности. Более высокая скорость лучше, поскольку она показывает, что метод эффективнее других, а более высокое значение модульности желательно, поскольку оно указывает на наличие лучше определенных сообществ. Сравниваемые методы: алгоритм Клаузета, Ньюмана и Мура ^[2] , Понса и Латапи ^{[11] и Вакиты и Цуруми [12]} .

-/- в таблице относится к методу, выполнение которого заняло более 24 часов. Эта таблица (из ^{[1] [14]} ) показывает, что метод Лувена превосходит многие аналогичные методы оптимизации модульности как в категориях модульности, так и времени.

• Алгоритм Лейдена
• Модульность (сети)
• Структура сообщества
• Сетевая наука
• Кластеризация методом k-средних

• «Метод Лувена для обнаружения сообществ в больших сетях» Венсан Блондель http://perso.uclouvain.be/vincent.blondel/research/louvain.html