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