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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
 
(не показано 5 промежуточных версий 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>.
+
'''Алгоритм Брандеса'''<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 />
 +
 +
[[Категория:Начатые статьи]]

Текущая версия на 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.