Просмотр кода страницы Вычисление betweenness centrality

== Свойства и структура алгоритмов ==
=== Общее описание алгоритма ===

'''Центральностью''' (англ. betweenness centrality<ref>Freeman, Linton C. “A Set of Measures of Centrality Based on Betweenness.” Sociometry 40, no. 1 (March 1977): 35. doi:10.2307/3033543.</ref>) вершины <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>.

'''Алгоритм Брандеса'''<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>.
         
=== Математическое описание ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Описание схемы реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Описание ресурса параллелизма алгоритма ===

Алгоритм обладает высоким потенциалом параллелизма, как при вычислении кратчайших путей, так и при вычислении зависимостей вершин. Существуют эффективные реализации для 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>

=== Описание входных и выходных данных ===
=== Свойства алгоритма===
== Программная реализация алгоритмов ==
=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===
== Литература ==

<references />