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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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