On the External Validity of Average-case Analyses of Graph Algorithms
Open Access
- 22 January 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 20 (1) , 1-42
Abstract
The number one criticism of average-case analysis is that we do not actually know the probability distribution of real-world inputs. Thus, analyzing an algorithm on some random model has no implications for practical performance. At its core, this criticism doubts the existence of external validity ; i.e., it assumes that algorithmic behavior on the somewhat simple and clean models does not translate beyond the models to practical performance real-world input. With this article, we provide a first step toward studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2,740 sparse real-world networks depending on two properties: heterogeneity (variance in the degree distribution) and locality (tendency of edges to connect vertices that are already close). We compare this with the performance on generated networks with varying locality and heterogeneity. We find that the performance in the idealized setting of network models translates surprisingly well to real-world networks. Moreover, heterogeneity and locality appear to be the core properties impacting the performance of many graph algorithms.Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- On computing the diameter of real-world undirected graphsTheoretical Computer Science, 2013
- Hyperbolic geometry of complex networksPhysical Review E, 2010
- Improved upper bounds for vertex coverTheoretical Computer Science, 2010
- Fast computation of empirically tight bounds for the diameter of massive graphsACM Journal of Experimental Algorithmics, 2009
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- The average distances in random graphs with given expected degreesProceedings of the National Academy of Sciences, 2002
- Connected Components in Random Graphs with Given Expected Degree SequencesAnnals of Combinatorics, 2002
- Stochastic blockmodels: First stepsSocial Networks, 1983
- A New Algorithm for Generating All the Maximal Independent SetsSIAM Journal on Computing, 1977
- A general theory of bibliometric and other cumulative advantage processesJournal of the American Society for Information Science, 1976