Определение диаметра графа: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Daryin (обсуждение | вклад) Общее описание алгоритма |
Daryin (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
* Java: [http://webgraph.di.unimi.it WebGraph] (класс <code>[http://webgraph.di.unimi.it/docs/it/unimi/dsi/webgraph/algo/FourSweepIterativeFringeDiameter.html FourSweepIterativeFringeDiameter]</code>), многопоточная реализация. Алгоритм был использован для вычисления диаметра подграфа социальной сети Facebook (149 миллионов вершин, 16 миллиардов рёбер), время работы составило 20 минут<ref>Backstrom, Lars, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. “Four Degrees of Separation,” WebSci'12, 33–42, New York, New York, USA: ACM Press, 2012. doi:10.1145/2380718.2380723.</ref>. | |||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Версия от 15:42, 11 июня 2015
Свойства и структура алгоритмов
Общее описание алгоритма
Диаметром неориентированного графа называется максимальная длина кратчайшего пути между двумя вершинами. Классический способ определения диаметра – выполнить поиск в ширину от всех вершин, тогда диаметр равен максимальному из найденных расстояний. Сложность такого подхода составляет [math]\displaystyle{ O(mn) }[/math], и в худшем случае (например, когда граф является циклом) эту оценку, по-видимому, улучшить нельзя.
Алгоритм iFUB[1] (англ. iterative Fringe Upper Bound) позволяет уменьшить количество вызовов алгоритма поиска в ширину. Для многих реальных графов будет достаточно всего нескольких вызовов и общая сложность будет близка к линейной [math]\displaystyle{ O(m) }[/math].
Математическое описание
Вычислительное ядро алгоритма
Макроструктура алгоритма
Описание схемы реализации последовательного алгоритма
Последовательная сложность алгоритма
Последовательная сложность алгоритма iFUB равна [math]\displaystyle{ O(Bm) }[/math], где [math]\displaystyle{ B }[/math] – число вызовов алгоритма поиска в ширину, сложность каждого вызова [math]\displaystyle{ O(m) }[/math]. В худшем случае (граф является циклом) [math]\displaystyle{ B = n }[/math] и общая сложность равна [math]\displaystyle{ O(mn) }[/math], однако для многих реальных графов [math]\displaystyle{ B = O(1) }[/math] и общая сложность составляет [math]\displaystyle{ O(m) }[/math].
Информационный граф
Описание ресурса параллелизма алгоритма
Описание входных и выходных данных
Входные данные: неориентированный граф [math]\displaystyle{ (V, E) }[/math] ([math]\displaystyle{ n }[/math] вершин [math]\displaystyle{ v_i }[/math] и [math]\displaystyle{ m }[/math] рёбер).
Объём входных данных: [math]\displaystyle{ O(m + n) }[/math].
Выходные данные: диаметр графа [math]\displaystyle{ (V, E) }[/math].
Объём выходных данных: [math]\displaystyle{ O(1) }[/math].
Свойства алгоритма
Программная реализация алгоритмов
Особенности реализации последовательного алгоритма
Описание локальности данных и вычислений
Возможные способы и особенности реализации параллельного алгоритма
Масштабируемость алгоритма и его реализации
Динамические характеристики и эффективность реализации алгоритма
Выводы для классов архитектур
Существующие реализации алгоритма
- Java: WebGraph (класс
FourSweepIterativeFringeDiameter), многопоточная реализация. Алгоритм был использован для вычисления диаметра подграфа социальной сети Facebook (149 миллионов вершин, 16 миллиардов рёбер), время работы составило 20 минут[2].
Литература
- ↑ Crescenzi, Pilu, Roberto Grossi, Michel Habib, Leonardo Lanzi, and Andrea Marino. “On Computing the Diameter of Real-World Undirected Graphs.” Theoretical Computer Science 514 (November 2013): 84–95. doi:10.1016/j.tcs.2012.09.018.
- ↑ Backstrom, Lars, Paolo Boldi, Marco Rosa, Johan Ugander, and Sebastiano Vigna. “Four Degrees of Separation,” WebSci'12, 33–42, New York, New York, USA: ACM Press, 2012. doi:10.1145/2380718.2380723.