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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
 
Строка 1: Строка 1:
−
== Свойства и структура алгоритмов ==
+
== Свойства и структура алгоритма ==
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
Строка 11: Строка 11:
 
'''Алгоритм Брандеса'''<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> для взвешенного.
 
'''Алгоритм Брандеса'''<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>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>
 
:<math>
Строка 37: Строка 37:
  
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
−
=== Описание схемы реализации последовательного алгоритма ===
+
=== Схема реализации последовательного алгоритма ===
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
 
Вычислительная сложность алгоритма Брандеса <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>O(n (S(n, m) + m))</math>, где <math>S(n, m)</math> – сложность поиска кратчайших путей от одной вершины. Такая оценка получается исходя из того, что для каждой из <math>n</math> вершин требуется найти кратчайшие пути (со сложностью <math>S(n, m)</math>) и затем вычислить зависимости и обновить центральность (со сложностью <math>O(m)</math>).  
Строка 48: Строка 48:
  
 
=== Информационный граф ===
 
=== Информационный граф ===
−
=== Описание ресурса параллелизма алгоритма ===
+
=== Ресурс параллелизма алгоритма ===
  
 
Алгоритм обладает высоким потенциалом параллелизма, как при вычислении кратчайших путей, так и при вычислении зависимостей вершин. Существуют эффективные реализации для 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>
  
−
=== Описание входных и выходных данных ===
+
=== Входные и выходные данные алгоритма ===
−
=== Свойства алгоритма===
+
=== Свойства алгоритма ===
−
== Программная реализация алгоритмов ==
+
 
 +
== Программная реализация алгоритма ==
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
−
=== Описание локальности данных и вычислений ===
+
=== Локальность данных и вычислений ===
−
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
==== Локальность реализации алгоритма ====
 +
===== Структура обращений в память и качественная оценка локальности =====
 +
===== Количественная оценка локальности =====
 +
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
=== Масштабируемость алгоритма и его реализации ===
 
=== Масштабируемость алгоритма и его реализации ===
 +
==== Масштабируемость алгоритма ====
 +
==== Масштабируемость реализации алгоритма ====
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
Строка 74: Строка 80:
  
 
<references />
 
<references />
 +
 +
[[Категория:Начатые статьи]]

Текущая версия на 14:43, 29 июля 2015

Содержание

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 Существующие реализации алгоритма

3 Литература

  1. ↑ Freeman, Linton C. “A Set of Measures of Centrality Based on Betweenness.” Sociometry 40, no. 1 (March 1977): 35. doi:10.2307/3033543.
  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. ↑ 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.
  4. ↑ 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.
  5. ↑ 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.
Источник — https://algowiki-project.org/w/ru/index.php?title=Вычисление_betweenness_centrality&oldid=2293