Вычисление betweenness centrality

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Центральностью (англ. betweenness centrality) вершины $v$ графа $G = (V, E)$ называется величина

$C_B(v) = \sum_{s \ne t \ne v \in V} \frac{\sigma_{st}(v)}{\sigma_{st}},$

где $\sigma_{st}$ – число различных кратчайших путей в графе $G$ от вершины $s$ к вершине $t$, а $\sigma_{st}(v)$ – число таких путей, проходящих через вершину $v$.

Алгоритм Брандеса вычисляет центральность всех вершин графа за время $O(mn)$ невзвешенного графа и $O(mn + n^2 \ln n)$ для взвешенного.

1.2 Математическое описание алгоритма

Пусть на графе $G$ заданы положительные веса рёбер $f(e)$, $e \in E$. Если граф невзвешенный, то $f(e) \equiv 1$. Обозначим через $d(v, w)$ кратчайшее расстояние между вершинами $v$ и $w$. Множество

$P_s(v) = \{ w \in V \mid d(s, v) = d(s, w) + f(w, v) \}$

состоит из вершин $w$, предшествующих $v$ на кратчайших путях от $s$ к $v$.

Зависимостью вершины $s$ от вершины $v$ называется величина

$\delta_s(v) = \sum_{t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}}.$

По соглашению $\sigma_{ss} = 1$. Центральность тогда равна сумме зависимостей от всех вершин графа:

$C_B(v) = \sum_{s \ne v} \delta_s(v).$

Брандес доказал, что зависимость вершин удовлетворяет рекурсивному соотношению

$\delta_s(v) = \sum_{v \in P_s(w)} \frac{\sigma_{sv}}{\sigma_{sw}} \left( 1 + \delta_s(w) \right).$

Таким образом, зависимость $s$ от всех вершин может быть вычислена за время $O(m)$ после нахождения кратчайших путей от вершины $s$.

1.3 Вычислительное ядро алгоритма

Основной объём вычислений в алгоритме Брандеса приходится на решение задачи поиска кратчайших путей одной вершины (для взвешенного графа) или на поиск в ширину (для невзвешенного).

1.6 Последовательная сложность алгоритма

Вычислительная сложность алгоритма Брандеса $O(n (S(n, m) + m))$, где $S(n, m)$ – сложность поиска кратчайших путей от одной вершины. Такая оценка получается исходя из того, что для каждой из $n$ вершин требуется найти кратчайшие пути (со сложностью $S(n, m)$) и затем вычислить зависимости и обновить центральность (со сложностью $O(m)$).

Для невзвешенного графа $S(n, m) = O(m)$ (для алгоритма поиска в ширину) и общая сложность составляет $O(mn)$.

Для взвешенного графа $S(n, n) = O(m + n \ln n)$ (для алгоритма Дейкстры с использованием фибоначчиевой кучи) и общая сложность составляет $O(mn + n^2 \ln n)$.

Используемый объём памяти в обоих случаях составляет $O(m + n)$: для каждой вершины необходимо хранить зависимость текущей вершины $s$ и значение центральности, а для каждого ребра – отметку, лежит ли оно на кратчайшем пути.

1.8 Ресурс параллелизма алгоритма

Алгоритм обладает высоким потенциалом параллелизма, как при вычислении кратчайших путей, так и при вычислении зависимостей вершин. Существуют эффективные реализации для GPU.

2 Программная реализация алгоритма

2.7 Существующие реализации алгоритма

• C++: Boost Graph Library (функция betweenness_centrality).
• C++, MPI: Parallel Boost Graph Library
  • функция brandes_betweenness_centrality вычисляет центральность вершин распределённого графа;
  • функция non_distributed_brandes_betweenness_centrality вычисляет центральность вершин графа, помещающегося в память одного узла, распределяя между узлами работу по поиску кратчайших расстояний.
• Java: WebGraph (класс BetweennessCentrality), многопоточная реализация.
• Python: NetworkX (функция betweenness_centrality).
• Python/C++: NetworKit (класс networkit.centrality.Betweenness).