Алгоритм распространения констант для задачи поиска сообществ в социальном графе

1 Постановка задачи

Рисунок 1. Пример разбиения на сообщества

Рассматривается задача поиска сообществ в неориенетированном графе с весами, значение которых являются действительными неотрицательными числами.

Дан граф [math] G = (V, E)[/math], где [math] V [/math] — множество вершин, [math] E [/math] — множество ребер, [math] w (u, v) [/math] — вес каждого ребра [math] e(u, v) \in E, u, v \in V[/math].

Цель задачи — найти такое разбиение графа [math]G[/math] на множество [math]C[/math] непересекающихся сообществ вершин [math]c_i \subseteq V[/math]: [math] \cup c_i = V, \forall c_i \in C [/math] [math] c_i \cap c_j = \varnothing, \forall c_i, c_j \in C, i \neq j, [/math] чтобы максимизировать функционал модулярности [math]Q[/math]:

[math] Q = \sum_{c \in C} \left(\frac{\sum_{in}^{c}}{m} - \left[\frac{\sum{out}^{c}}{m} \right]^2\right)[/math],

где [math] \sum_{in}^{c} = \sum_{u, v \in c, e(u, v) \in E} w(u, v), [/math]

[math] \sum_{out}^{c} = \sum_{in}^{c} + \sum_{u \in c, v \notin c, e(u, v) \in E} w(u, v)[/math],

[math] m = \sum_{e(u, v) \in E} w(u, v).[/math]

[math]\sum_{in}^{c} [/math] — сумма весов всех внутренних рёбер сообщества.

[math]\sum_{out}^{c} [/math] — сумма весов всех рёбер, исходящих из вершин сообщества.

[math]m[/math] — нормализующий коэффициент, сумма весов рёбер графа. Вершины одного сообщества должны быть сильно связаны, а вершины из разных сообществ должны быть слабо связаны.

2 Алгоритм решения

В качестве подхода к решению будем рассматривать алгоритм Label Propagation. К достоинствам данного алгоритма можно отнести следующие его аспекты:

• время работы
• количество итераций слабо зависит от размера графа
• прост в понимании

Недостатками алгоритма являются:

• недетерминированность, то есть на одном и том же наборе входных данных при новом запуске результат может получиться отличным от предыдущего
• при некоторых входных данных может давать плохие решения

В начальный момент времени каждой вершине приписана уникальная метка сообщества. Обновление меток вершин осуществляется по следующему принципу: у каждой вершины есть определенное число смежных вершин, которым приписаны метки каких-то сообществ, также у ребер между вершинами определены свои веса. На очередном шаге определим метку вершины [math]current[/math]. У соседей этой вершины метки сообществ, к которым они принадлежат, могут быть различными. Рассмотрим каждый тип меток. Для вершин [math]i[/math]-го типа считаем сумму весов ребер, которые соединяют эти вершины с изучаемой вершиной [math]current[/math]. Приписываем нашей вершине ту метку, для которой эта сумма оказалась максимальной. Итерации происходят до тех пор, пока меняются метки вершин. В стандартном алгоритме принято рассматривать вершины в случайном порядке, это позволяет улучшить метрику. Можно отказаться от переупорядочивания вершин для увеличения быстродействия вычислений. Также в параллельной версии программы потоки в рамках одного узла могут конкурировать, производить вычисления неравномерно, засчёт чего достигается эффект случайности в обработке вершин.

Граф хранится как разреженная матрица смежности в формате CSR.

Разбиваем множество вершин на заданное число узлов. Каждый узел пересчитывает метки для своего набора вершин. Массивы меток для всех вершин синхронизируются с помощью операции MPI_Allgather.