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

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

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

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

[math] C_B(v) = \sum_{s \ne t \ne v \in V} \frac{\sigma_{st}(v)}{\sigma_{st}}, [/math]

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

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

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

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

[math] P_s(v) = \{ w \in V \mid d(s, v) = d(s, w) + f(w, v) \} [/math]

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

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

[math] \delta_s(v) = \sum_{t \in V} \frac{\sigma_{st}(v)}{\sigma_{st}}. [/math]

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

[math] C_B(v) = \sum_{s \ne v} \delta_s(v). [/math]

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

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

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

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

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

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

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

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

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

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

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).