Вычисление betweenness centrality: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
Daryin (обсуждение | вклад) |
||
| Строка 39: | Строка 39: | ||
=== Описание схемы реализации последовательного алгоритма === | === Описание схемы реализации последовательного алгоритма === | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Вычислительная сложность алгоритма Брандеса <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> (для алгоритма [[Поиск в ширину (BFS)|поиска в ширину]]) и общая сложность составляет <math>O(mn)</math>. | |||
Для взвешенного графа <math>S(n, n) = O(m + n \ln n)</math> (для [[Алгоритм Дейкстры|алгоритма Дейкстры]]<ref>Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.</ref> с использованием фибоначчиевой кучи<ref name=FibHeap>Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1987): 596–615. doi:10.1145/28869.28874.</ref>) и общая сложность составляет <math>O(mn + n^2 \ln n)</math>. | |||
Используемый объём памяти в обоих случаях составляет <math>O(m + n)</math>: для каждой вершины необходимо хранить зависимость текущей вершины <math>s</math> и значение центральности, а для каждого ребра – отметку, лежит ли оно на кратчайшем пути. | |||
=== Информационный граф === | === Информационный граф === | ||
=== Описание ресурса параллелизма алгоритма === | === Описание ресурса параллелизма алгоритма === | ||
Версия от 13:15, 23 июня 2015
Свойства и структура алгоритмов
Общее описание алгоритма
Центральностью (англ. betweenness centrality[1]) вершины [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].
Алгоритм Брандеса[2] вычисляет центральность всех вершин графа за время [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]
Брандес доказал[2], что зависимость вершин удовлетворяет рекурсивному соотношению
- [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] (для алгоритма Дейкстры[3] с использованием фибоначчиевой кучи[4]) и общая сложность составляет [math]\displaystyle{ O(mn + n^2 \ln n) }[/math].
Используемый объём памяти в обоих случаях составляет [math]\displaystyle{ O(m + n) }[/math]: для каждой вершины необходимо хранить зависимость текущей вершины [math]\displaystyle{ s }[/math] и значение центральности, а для каждого ребра – отметку, лежит ли оно на кратчайшем пути.
Информационный граф
Описание ресурса параллелизма алгоритма
Алгоритм обладает высоким потенциалом параллелизма, как при вычислении кратчайших путей, так и при вычислении зависимостей вершин. Существуют эффективные реализации для GPU.[5]
Описание входных и выходных данных
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- 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).
Литература
- ↑ 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.
- ↑ Dijkstra, E W. “A Note on Two Problems in Connexion with Graphs.” Numerische Mathematik 1, no. 1 (December 1959): 269–71. doi:10.1007/BF01386390.
- ↑ Fredman, Michael L, and Robert Endre Tarjan. “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.” Journal of the ACM 34, no. 3 (July 1987): 596–615. doi:10.1145/28869.28874.
- ↑ 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.