Метод Лувена

Метод Лувена для обнаружения сообществ — это метод извлечения непересекающихся сообществ из больших сетей, созданный Блонделем и др . из Лувенского университета (источник названия этого метода). Этот метод представляет собой жадный метод оптимизации, который работает во времени. $O(n\cdot \log n)$ где $n$ — количество узлов в сети.

Оптимизация модульности

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

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

Алгоритм

Оптимизируемое значение — это модульность , определяемая как значение в диапазоне $[-1/2,1]$ который измеряет плотность связей внутри сообществ по сравнению со связями между сообществами. Для взвешенного графа модульность определяется как:

$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}),$

где:

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

${\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$ можно рассчитать как:

${\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}}$

где

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

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

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

Чтобы максимально эффективно максимизировать модульность, метод Лувена состоит из двух этапов, которые повторяются итеративно.

Этап 1:

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

2. Далее для каждого узла $i$, изменение модульности рассчитывается для удаления $i$ из своего сообщества и перемещения его в сообщество каждого соседа $j$ из $i$. Это значение вычисляется в два этапа:

(a) Вычислите изменение модульности $\Delta Q$ для удаления узла $i$ от своего первоначального сообщества.

(б) Вычислить изменение модульности $\Delta Q$ для вставки изолированного узла $i$ (т.е. узел $i$ не имеет связей и находится в сообществе только самого себя) в сообщество соседнего узла, обозначаемого $c_{j}$.

Далее мы покажем вывод для (b). Уравнения для (а) аналогичны и могут быть вычислены аналогичными методами.

Сначала мы вычисляем модульность изолированного кластера узлов $i$, который мы назовем $c_{i}$. Здесь мы предполагаем, что петель нет, и поэтому $A_{\mu \mu }=0$ для всех значений $\mu$:

${\begin{aligned}Q_{i}^{\text{prev}}&={\dfrac {1}{2m}}\sum _{\mu =1}^{N_{i}=1}\sum _{\nu =1}^{N_{i}=1}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{i}=1}{\dfrac {k_{\mu }}{2m}}\right)^{2}\\&=-\left({\dfrac {k_{i}}{2m}}\right)^{2}\end{aligned}}$

Далее мы вычисляем модульность кластера $c_{j}$ прежде чем мы добавили новый узел $i$. Мы уже вычислили это уравнение:

${\begin{aligned}Q_{j}^{\text{prev}}&={\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{j}}{\dfrac {k_{\mu }}{2m}}\right)^{2}\end{aligned}}$

Наконец, мы вычисляем модульность кластера $c_{j}$ после того, как мы добавили новый узел $i$:

${\begin{aligned}Q_{j}^{\text{updated}}&={\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}+1}\sum _{\nu =1}^{N_{j}+1}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{j}+1}{\dfrac {k_{\mu }}{2m}}\right)^{2}\end{aligned}}$

Мы можем переписать первый член следующим образом:

${\begin{aligned}{\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}+1}\sum _{\nu =1}^{N_{j}+1}A_{\mu \nu }&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2\sum _{\mu =1}^{N_{j}+1}A_{\mu ,N_{j}+1}\right]\\&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2k_{i}^{(j)}\right]\end{aligned}}$

где $k_{i}^{(j)}$ представляет собой сумму весов всех ребер, которые проходят между узлами $i$ и узлы в сообществе $c_{j}$. Другими словами, $k_{i}^{(j)}$ это степень узла $i$ внутри сообщества $c_{j}$.

Мы можем переписать второе слагаемое так:

${\begin{aligned}\left(\sum _{\mu =1}^{N_{j}+1}{\dfrac {k_{\mu }}{2m}}\right)^{2}&=\sum _{\mu =1}^{N_{j}+1}\sum _{\nu =1}^{N_{j}+1}{\dfrac {k_{\mu }k_{\nu }}{(2m)^{2}}}\\&=\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}{\dfrac {k_{\mu }k_{\nu }}{(2m)^{2}}}+2k_{N_{j}+1}\sum _{\mu =1}^{N_{j}+1}{\dfrac {k_{\mu }}{(2m)^{2}}}+{\dfrac {(k_{N_{j}+1})^{2}}{(2m)^{2}}}\\&={\dfrac {1}{(2m)^{2}}}\left[\left(\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}\right)\left(\sum _{\nu =1}^{N_{j}}k_{\nu }+k_{N_{j}+1}\right)\right]\\&=\left({\dfrac {\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}}{2m}}\right)^{2}\end{aligned}}$

Объединив это, мы имеем:

${\begin{aligned}Q_{j}^{\text{updated}}&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2k_{i}^{(j)}\right]-\left({\dfrac {\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}}{2m}}\right)^{2}\end{aligned}}$

Сложив уравнения для $Q_{i}^{\text{prev}}$, $Q_{j}^{\text{prev}}$, и $Q_{j}^{\text{updated}}$, мы можем вычислить изменение модульности $\Delta Q$ для добавления изолированного узла $i$ в кластер $c_{j}$. Иногда это называют выигрышем :

$${\begin{aligned}\Delta Q&=Q_{j}^{\text{updated}}-Q_{j}^{\text{prev}}-Q_{i}^{\text{prev}}\\&={\dfrac {1}{2m}}\left[\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }+2k_{i}^{(j)}\right]-\left({\dfrac {\sum _{\mu =1}^{N_{j}}k_{\mu }+k_{N_{j}+1}}{2m}}\right)^{2}\\&-\left[{\dfrac {1}{2m}}\sum _{\mu =1}^{N_{j}}\sum _{\nu =1}^{N_{j}}A_{\mu \nu }-\left(\sum _{\mu =1}^{N_{j}}{\dfrac {k_{\mu }}{2m}}\right)^{2}-\left({\dfrac {k_{i}}{2m}}\right)^{2}\right]\end{aligned}}$$

3. После изменения модульности $\Delta Q$ было рассчитано для всех сообществ $\{c_{j}\}$ этот узел $i$ подключен к узлу $i$ помещен в сообщество, что привело к наибольшему увеличению модульности. Если увеличение невозможно, узел $i$ остается в своем первоначальном сообществе.

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

Этап 2:

Второй этап алгоритма включает в себя сокращение сообществ до одного узла и повторение шагов этапа 1:

1. Каждое сообщество $c_{j}$ сводится к одному узлу. Ребра, соединяющие узлы из $c_{j}$ другим сообществам и аналогичным образом сводится к одному взвешенному преимуществу.

2. После создания нового графа второй этап завершается, и первый этап можно повторно применить к новой сети.

Предыдущее использование

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

Недостатки

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

Сравнение с другими методами обнаружения непересекающихся сообществ

При сравнении методов оптимизации модульности важными показателями являются скорость и результирующее значение модульности. Чем выше скорость, тем лучше, поскольку это показывает, что метод более эффективен, чем другие, и желательно более высокое значение модульности, поскольку оно указывает на более четко определенные сообщества. Сравниваемыми методами являются алгоритм Клаузета, Ньюмана и Мура, Понс и Латапи, и Вакита и Цуруми.

Сравнение оптимизации модульности

	Каратэ	Арксив	Интернет	Веб-nd.edu	Телефон	Веб Великобритания-2005	Веб-веббаза 2001
Узлы/ссылки	34/77	9к/24к	70 тыс./351 тыс.	325 тыс./1М	2,6 М/6,3 М	39М/783М	118М/1Б
Клаузет, Ньюман и Мур	.38/0 с	0,772/3,6 с	.692/799 с	.927/5034с	-/-	-/-	-/-
Понс и Латапи	.42/0 с	0,757/3,3 с	.729/575с	.895/6666p	-/-	-/-	-/-
Вакита и Цуруми	.42/0 с	0,761/0,7 с	.667/62с	.898/248 с	.56/464 с	-/-	-/-
Лувенский метод	.42/0 с	.813/0p	0,781/1 с	.935/3с	.769/134с	.979/738 с	0,984/152 млн.

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

См. также

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

Ссылки

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