Вычисление betweenness centrality: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) |
ASA (обсуждение | вклад) Нет описания правки |
||
| (не показаны 4 промежуточные версии 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.” 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> для взвешенного. | '''Алгоритм Брандеса'''<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> | ||
=== | === Входные и выходные данные алгоритма === | ||
=== Свойства алгоритма=== | === Свойства алгоритма === | ||
== Программная реализация | |||
== Программная реализация алгоритма == | |||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
=== | === Локальность данных и вычислений === | ||
=== Возможные способы и особенности реализации | ==== Локальность реализации алгоритма ==== | ||
===== Структура обращений в память и качественная оценка локальности ===== | |||
===== Количественная оценка локальности ===== | |||
=== Возможные способы и особенности параллельной реализации алгоритма === | |||
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
==== Масштабируемость алгоритма ==== | |||
==== Масштабируемость реализации алгоритма ==== | |||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
| Строка 43: | Строка 80: | ||
<references /> | <references /> | ||
[[Категория:Начатые статьи]] | |||
Текущая версия от 11:43, 29 июля 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.