Лувенский алгоритм

Лувенский алгоритм поиска сообществ в графе разработан группой авторов из лувенского католического университета (г. Лувен, Бельгия) в 2008 году.

В начале алгоритма каждая вершина образует отдельное сообщество. Шаг алгоритма состоит из двух фаз. На первой фазе для каждой вершины происходит попытка найти сообщество, перемещение в которое даст максимальное общее положительное изменение модулярности Q. Переместить вершину можно только по смежным ребрам, то есть только в те сообщества, которым принадлежат вершины, смежные с данной. Просмотр всех вершин продолжается до тех пор, пока происходит хотя бы одно перемещение вершины.

На второй фазе происходит сжатие графа: вершины, входящие в одно сообщество образуют новую супервершину с соответствующим преобразованием ребер. Алгоритм останавливается, когда граф перестает изменяться.

На рисунке изображена схема работы лувенского алгоритма. Ниже приведен псевдокод алгоритма, соответствующий примеру реализации.

Louvein algorithm
Рис. Схема работы лувенского алгоритма.

Псевдокод лувенского алгоритма поиска сообществ в графе

Input: граф G(V, E)
Output: массив сообществ component_id
Begin
component_id[v]=v, \forall v \in V // изначально каждая вершина графа образует отдельную компоненту
calculate_sigma // вычисление стартовых сумм
while (true) {
new_component_id[v]=v, \forall v \in V // каждая вершина графа образует отдельную компоненту нового графа
more = changed = false
// Фаза 1
do {
more = false
for \forall u \in V {
// получение номера компоненты, перемещение в которую вершины u максимизирует posdelta -
// положительное изменение модулярности Q
best_component = argmax_{\forall c, e(u,v) \in E, v \in c}(posdelta)
if component_id[u] \ne best_component {
update // модификация хранимых сумм
new_component_id[u] = best_component // перемещение вершины в другую компоненту
more = true
}
}
changed = changed | more
} while (more)
// Фаза 2
if changed == false {
return // выход из алгоритма
}
G(V, E) = compress(G) // сжатие графа
component_id = new_component_id // присваивание новых компонент, процедура translate
}
End