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

DOI10.1137/1.9781611974782.58MaRDI QIDQ4575797zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

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)