An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs

DOI10.1137/1.9781611974782.58zbMATH Open1410.68155arXiv1604.01445OpenAlexW2340785412MaRDI QIDQ4575797FDOQ4575797

Authors: Michele Borassi, Pilu Crescenzi, Luca Trevisan 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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 axioms. Furthermore, we prove that the axioms are verified asymptotically almost surely by several probabilistic models that generate power law random graphs, such as the 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.

Full work available at URL: https://arxiv.org/abs/1604.01445

Recommendations

• Algorithmic complexity of power law networks
• Computing giant graph diameters
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Fast Approximation of Centrality
• Subcubic equivalences between graph centrality problems, APSP and diameter

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cited In (9)

• Average distance queries through weighted samples in graphs and metric spaces: high scalability with tight statistical guarantees
• KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
• The diameter of AT‐free graphs
• Deterministic performance guarantees for bidirectional BFS on real-world networks
• Finding cliques in social networks: a new distribution-free model
• Fast approximation of eccentricities and distances in hyperbolic graphs
• Parameterized complexity of diameter
• Beyond Helly graphs: the diameter problem on absolute retracts
• Greed is good for deterministic scale-free networks

This page was built for publication: An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575797)