On the External Validity of Average-case Analyses of Graph Algorithms

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 algorith-
mic 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 (ten-
dency 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.