Вычисление betweenness centrality - История изменений

ASA в 11:43, 29 июля 2015

2015-07-29T11:43:14Z

← Предыдущая версия		Версия от 11:43, 29 июля 2015
Строка 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 />

			[[Категория:Начатые статьи]]

Daryin: /* Последовательная сложность алгоритма */

2015-06-23T13:15:55Z

Последовательная сложность алгоритма

← Предыдущая версия		Версия от 13:15, 23 июня 2015
Строка 39:		Строка 39:
	=== Описание схемы реализации последовательного алгоритма ===		=== Описание схемы реализации последовательного алгоритма ===
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===
			Вычислительная сложность алгоритма Брандеса <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> и значение центральности, а для каждого ребра – отметку, лежит ли оно на кратчайшем пути.

	=== Информационный граф ===		=== Информационный граф ===
	=== Описание ресурса параллелизма алгоритма ===		=== Описание ресурса параллелизма алгоритма ===

Daryin: /* Вычислительное ядро алгоритма */

2015-06-23T13:03:54Z

Вычислительное ядро алгоритма

← Предыдущая версия		Версия от 13:03, 23 июня 2015
Строка 34:		Строка 34:

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===
			Основной объём вычислений в алгоритме Брандеса приходится на решение задачи [[Поиск кратчайшего пути от одной вершины (SSSP)\|поиска кратчайших путей одной вершины]] (для взвешенного графа) или на [[Поиск в ширину (BFS)\|поиск в ширину]] (для невзвешенного).

	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	=== Описание схемы реализации последовательного алгоритма ===		=== Описание схемы реализации последовательного алгоритма ===

Daryin: /* Математическое описание */

2015-06-23T13:01:55Z

Математическое описание

@@ Строка 12: / Строка 12: @@
 === Математическое описание ===
 === Вычислительное ядро алгоритма ===
 === Макроструктура алгоритма ===

Daryin: /* Общее описание алгоритма */

2015-06-23T12:50:12Z

Общее описание алгоритма

← Предыдущая версия		Версия от 12:50, 23 июня 2015
Строка 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> для взвешенного.

	=== Математическое описание ===		=== Математическое описание ===

Daryin: /* Общее описание алгоритма */

2015-06-23T12:31:55Z

Общее описание алгоритма

← Предыдущая версия		Версия от 12:31, 23 июня 2015
Строка 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>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> для взвешенного.

	=== Математическое описание ===		=== Математическое описание ===

Daryin: /* Существующие реализации алгоритма */

2015-06-18T19:39:42Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 19:39, 18 июня 2015
Строка 38:		Строка 38:
	* Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/BetweennessCentrality.html BetweennessCentrality]</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: [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 ~~NetworkKit~~] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/centrality.html#networkit.centrality.Betweenness networkit.centrality.Betweenness]</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 />

Daryin: /* Существующие реализации алгоритма */

2015-06-18T19:35:14Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 19:35, 18 июня 2015
Строка 38:		Строка 38:
	* Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/BetweennessCentrality.html BetweennessCentrality]</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: [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 NetworkKit] (~~модуль~~ <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/centrality.html centrality]</code>).		* Python/C++: [https://networkit.iti.kit.edu NetworkKit] (класс <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/centrality.html#networkit.centrality.Betweenness networkit.centrality.Betweenness]</code>).

	== Литература ==		== Литература ==

	<references />		<references />

Daryin: /* Существующие реализации алгоритма */

2015-06-18T19:33:21Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 19:33, 18 июня 2015
Строка 38:		Строка 38:
	* Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/BetweennessCentrality.html BetweennessCentrality]</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: [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 NetworkKit] (модуль <code>[https://networkit.iti.kit.edu/data/uploads/docs/NetworKit-Doc/python/html/centrality.html centrality]</code>).

	== Литература ==		== Литература ==

	<references />		<references />

Daryin: /* Существующие реализации алгоритма */

2015-06-11T18:13:37Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 18:13, 11 июня 2015
Строка 37:		Строка 37:
	** функция <code>[http://www.boost.org/libs/graph_parallel/doc/html/non_distributed_betweenness_centrality.html non_distributed_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>), многопоточная реализация.		* 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>).

	== Литература ==		== Литература ==

	<references />		<references />