License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.21
URN: urn:nbn:de:0030-drops-169590
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16959/
Go to the corresponding LIPIcs Volume Portal

Bläsius, Thomas ; Fischbeck, Philipp

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

pdf-format:
LIPIcs-ESA-2022-21.pdf (1 MB)

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 paper, we provide a first step towards studying the question of external validity systematically. To this end, we evaluate the performance of six graph algorithms on a collection of 2751 sparse real-world networks depending on two properties; the 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.

BibTeX - Entry

@InProceedings{blasius_et_al:LIPIcs.ESA.2022.21,
  author =	{Bl\"{a}sius, Thomas and Fischbeck, Philipp},
  title =	{{On the External Validity of Average-Case Analyses of Graph Algorithms}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16959},
  URN =		{urn:nbn:de:0030-drops-169590},
  doi =		{10.4230/LIPIcs.ESA.2022.21},
  annote =	{Keywords: Average Case, Network Models, Empirical Evaluation}
}

Keywords: Average Case, Network Models, Empirical Evaluation
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022
Supplementary Material: We provide our source code, a docker image for easier reproducibility, the real-world network data set as well as all generated data (networks and statistics):
Software (Source Code): https://github.com/thobl/external-validity
Dataset (Source Code Archive): https://doi.org/10.5281/zenodo.6587324

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI