Определение диаметра графа
Свойства и структура алгоритма
Общее описание алгоритма
Диаметром неориентированного графа называется максимальная длина кратчайшего пути между двумя вершинами. Классический способ определения диаметра – выполнить поиск в ширину от всех вершин, тогда диаметр равен максимальному из найденных расстояний. Сложность такого подхода составляет [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]. - Python/C++: NetworKit (класс
networkit.properties.Diameter).
Литература
- ↑ 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.