Вычисление 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.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).