Longest shortest path, Java, WebGraph: различия между версиями
Перейти к навигации
Перейти к поиску
[досмотренная версия] | [досмотренная версия] |
ASA (обсуждение | вклад) (Новая страница: «{{level-i}} Основные авторы описания: И.В.Афанасьев = Ссылки = [http://webgraph.di.unimi.it...») |
ASA (обсуждение | вклад) |
||
Строка 17: | Строка 17: | ||
= Результаты прогонов = | = Результаты прогонов = | ||
− | = Литература | + | = Литература = |
<references /> | <references /> |
Текущая версия на 12:16, 14 июля 2022
Основные авторы описания: И.В.Афанасьев
Содержание
1 Ссылки
WebGraph (класс FourSweepIterativeFringeDiameter
), многопоточная реализация. Алгоритм был использован для вычисления диаметра подграфа социальной сети Facebook (149 миллионов вершин, 16 миллиардов рёбер), время работы составило 20 минут[1].
2 Локальность данных и вычислений
2.1 Локальность реализации алгоритма
2.1.1 Структура обращений в память и качественная оценка локальности
2.1.2 Количественная оценка локальности
3 Масштабируемость алгоритма и его реализации
3.1 Масштабируемость алгоритма
3.2 Масштабируемость реализации алгоритма
4 Динамические характеристики и эффективность реализации алгоритма
5 Результаты прогонов
6 Литература
- ↑ 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.