Вычисление betweenness centrality: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) (Общее описание алгоритма) |
ASA (обсуждение | вклад) |
||
| (не показано 13 промежуточных версий 1 участника) | |||
| Строка 1: | Строка 1: | ||
| − | == Свойства и структура | + | == Свойства и структура алгоритма == |
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| Строка 9: | Строка 9: | ||
где <math>\sigma_{st}</math> – число различных кратчайших путей в графе <math>G</math> от вершины <math>s</math> к вершине <math>t</math>, а <math>\sigma_{st}(v)</math> – число таких путей, проходящих через вершину <math>v</math>. | где <math>\sigma_{st}</math> – число различных кратчайших путей в графе <math>G</math> от вершины <math>s</math> к вершине <math>t</math>, а <math>\sigma_{st}(v)</math> – число таких путей, проходящих через вершину <math>v</math>. | ||
| − | '''Алгоритм Брандеса'''<ref>Brandes, Ulrik. “A Faster Algorithm for Betweenness Centrality | + | '''Алгоритм Брандеса'''<ref name=Brandes>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.</ref> вычисляет центральность всех вершин графа за время <math>O(mn)</math> невзвешенного графа и <math>O(mn + n^2 \ln n)</math> для взвешенного. |
| − | + | ||
| − | === Математическое описание === | + | === Математическое описание алгоритма === |
| + | Пусть на графе <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>. | ||
| + | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| + | Основной объём вычислений в алгоритме Брандеса приходится на решение задачи [[Поиск кратчайшего пути от одной вершины (SSSP)|поиска кратчайших путей одной вершины]] (для взвешенного графа) или на [[Поиск в ширину (BFS)|поиск в ширину]] (для невзвешенного). | ||
| + | |||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| − | === | + | === Схема реализации последовательного алгоритма === |
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| + | Вычислительная сложность алгоритма Брандеса <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> и значение центральности, а для каждого ребра – отметку, лежит ли оно на кратчайшем пути. | ||
| + | |||
=== Информационный граф === | === Информационный граф === | ||
| − | === | + | === Ресурс параллелизма алгоритма === |
Алгоритм обладает высоким потенциалом параллелизма, как при вычислении кратчайших путей, так и при вычислении зависимостей вершин. Существуют эффективные реализации для GPU.<ref>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.</ref> | Алгоритм обладает высоким потенциалом параллелизма, как при вычислении кратчайших путей, так и при вычислении зависимостей вершин. Существуют эффективные реализации для GPU.<ref>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.</ref> | ||
| − | === | + | === Входные и выходные данные алгоритма === |
| − | === Свойства алгоритма=== | + | === Свойства алгоритма === |
| − | == Программная реализация | + | |
| + | == Программная реализация алгоритма == | ||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
| − | === | + | === Локальность данных и вычислений === |
| − | === Возможные способы и особенности реализации | + | ==== Локальность реализации алгоритма ==== |
| + | ===== Структура обращений в память и качественная оценка локальности ===== | ||
| + | ===== Количественная оценка локальности ===== | ||
| + | === Возможные способы и особенности параллельной реализации алгоритма === | ||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
| + | ==== Масштабируемость алгоритма ==== | ||
| + | ==== Масштабируемость реализации алгоритма ==== | ||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
| + | |||
| + | * C++: [http://www.boost.org/libs/graph/doc/ Boost Graph Library] (функция <code>[http://www.boost.org/libs/graph/doc/betweenness_centrality.html betweenness_centrality]</code>). | ||
| + | * C++, MPI: [http://www.boost.org/libs/graph_parallel/doc/html/index.html Parallel Boost Graph Library] | ||
| + | ** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/betweenness_centrality.html brandes_betweenness_centrality]</code> вычисляет центральность вершин распределённого графа; | ||
| + | ** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/non_distributed_betweenness_centrality.html non_distributed_brandes_betweenness_centrality]</code> вычисляет центральность вершин графа, помещающегося в память одного узла, распределяя между узлами работу по поиску кратчайших расстояний. | ||
| + | * Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/BetweennessCentrality.html BetweennessCentrality]</code>), многопоточная реализация. | ||
| + | * Python: [https://networkx.github.io NetworkX] (функция <code>[http://networkx.github.io/documentation/networkx-1.9.1/reference/generated/networkx.algorithms.centrality.betweenness_centrality.html#networkx.algorithms.centrality.betweenness_centrality betweenness_centrality]</code>). | ||
| + | * Python/C++: [https://networkit.iti.kit.edu NetworKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/centrality.html#networkit.centrality.Betweenness networkit.centrality.Betweenness]</code>). | ||
| + | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
| + | |||
| + | [[Категория:Начатые статьи]] | ||
Текущая версия на 14:43, 29 июля 2015
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Локальность данных и вычислений
- 2.3 Возможные способы и особенности параллельной реализации алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 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 Последовательная сложность алгоритма
Вычислительная сложность алгоритма Брандеса [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] (для алгоритма Дейкстры[3] с использованием фибоначчиевой кучи[4]) и общая сложность составляет [math]O(mn + n^2 \ln n)[/math].
Используемый объём памяти в обоих случаях составляет [math]O(m + n)[/math]: для каждой вершины необходимо хранить зависимость текущей вершины [math]s[/math] и значение центральности, а для каждого ребра – отметку, лежит ли оно на кратчайшем пути.
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Алгоритм обладает высоким потенциалом параллелизма, как при вычислении кратчайших путей, так и при вычислении зависимостей вершин. Существуют эффективные реализации для GPU.[5]
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.2.1 Локальность реализации алгоритма
2.2.1.1 Структура обращений в память и качественная оценка локальности
2.2.1.2 Количественная оценка локальности
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Масштабируемость алгоритма
2.4.2 Масштабируемость реализации алгоритма
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.
- ↑ 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.
