Longest shortest path, Java, WebGraph
Основные авторы описания: И.В.Афанасьев
Ссылки
WebGraph (класс FourSweepIterativeFringeDiameter), многопоточная реализация. Алгоритм был использован для вычисления диаметра подграфа социальной сети Facebook (149 миллионов вершин, 16 миллиардов рёбер), время работы составило 20 минут[1].
Локальность данных и вычислений
Локальность реализации алгоритма
Структура обращений в память и качественная оценка локальности
Количественная оценка локальности
Масштабируемость алгоритма и его реализации
Масштабируемость алгоритма
Масштабируемость реализации алгоритма
Динамические характеристики и эффективность реализации алгоритма
Результаты прогонов
Литература =
- ↑ 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.