Вычисление betweenness centrality: различия между версиями

[непроверенная версия]

Версия 16:01, 23 июня 2015

Содержание

1 Свойства и структура алгоритмов
2 Программная реализация алгоритмов
3 Литература

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

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

Центральностью (англ. betweenness centrality^[1]) вершины [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].

Алгоритм Брандеса^[2] вычисляет центральность всех вершин графа за время [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]

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

[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.4 Макроструктура алгоритма

1.5 Описание схемы реализации последовательного алгоритма

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

1.7 Информационный граф

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

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

1.9 Описание входных и выходных данных

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Описание локальности данных и вычислений

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

3 Литература

↑ Freeman, Linton C. “A Set of Measures of Centrality Based on Betweenness.” Sociometry 40, no. 1 (March 1977): 35. doi:10.2307/3033543.
↑ ^2,0 ^2,1 Brandes, Ulrik. “A Faster Algorithm for Betweenness Centrality.” The Journal of Mathematical Sociology 25, no. 2 (June 2001): 163–77. doi:10.1080/0022250X.2001.9990249.
↑ McLaughlin, Adam, and David A Bader. “Scalable and High Performance Betweenness Centrality on the GPU,” SC'14, 572–83, IEEE Press, 2014. doi:10.1109/SC.2014.52.

[1] Freeman, Linton C. “A Set of Measures of Centrality Based on Betweenness.” Sociometry 40, no. 1 (March 1977): 35. doi:10.2307/3033543.

[Brandes-2] 2,0 ^2,1 Brandes, Ulrik. “A Faster Algorithm for Betweenness Centrality.” The Journal of Mathematical Sociology 25, no. 2 (June 2001): 163–77. doi:10.1080/0022250X.2001.9990249.

[3] McLaughlin, Adam, and David A Bader. “Scalable and High Performance Betweenness Centrality on the GPU,” SC'14, 572–83, IEEE Press, 2014. doi:10.1109/SC.2014.52.

[1]

[2]

[3]

@@ Строка 12: / Строка 12: @@
 === Математическое описание ===
+Пусть на графе <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>
+Брандес доказал<ref name=Brandes />, что зависимость вершин удовлетворяет рекурсивному соотношению
+:<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> после [[Поиск кратчайшего пути от одной вершины (SSSP)|нахождения кратчайших путей от вершины]] <math>s</math>.
 === Вычислительное ядро алгоритма ===
 === Макроструктура алгоритма ===