An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs

Abstract : In recent years, researchers proposed several algorithms that compute metric quantities of real-world complex networks, and that are very efficient in practice, although there is no worst-case guarantee. In this work, we propose an axiomatic framework to analyze the performances of these algorithms, by proving that they are efficient on the class of graphs satisfying certain properties. Furthermore, we prove that these properties are verified asymptotically almost surely by several probabilistic models that generate power law random graphs, such as the Configuration Model, the Chung-Lu model, and the Norros-Reittu model. Thus, our results imply average-case analyses in these models. For example, in our framework, existing algorithms can compute the diameter and the radius of a graph in subquadratic time, and sometimes even in time n 1+o(1). Moreover, in some regimes, it is possible to compute the k most central vertices according to closeness centrality in subquadratic time, and to design a distance oracle with sublinear query time and subquadratic space occupancy. In the worst case, it is impossible to obtain comparable results for any of these problems, unless widely-believed conjectures are false.
Type de document :
Communication dans un congrès
SODA 2017 - Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , Jan 2017, Barcelona, Spain. pp.920 - 939, 2017, Proceedings of the Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. 〈10.1137/1.9781611974782.58〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01525752
Contributeur : Marie-France Sagot <>
Soumis le : lundi 22 mai 2017 - 11:14:00
Dernière modification le : mercredi 11 avril 2018 - 01:52:25
Document(s) archivé(s) le : mercredi 23 août 2017 - 15:02:16

Fichier

1604.01445.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Michele Borassi, Pierluigi Crescenzi, Luca Trevisan. An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs. SODA 2017 - Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , Jan 2017, Barcelona, Spain. pp.920 - 939, 2017, Proceedings of the Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. 〈10.1137/1.9781611974782.58〉. 〈hal-01525752〉

Partager

Métriques

Consultations de la notice

73

Téléchargements de fichiers

32