Guidelines for Experimental Algorithmics: A Case Study in Network Analysis

The field of network science is a highly interdisciplinary area; for the empirical analysis of network data, it draws algorithmic methodologies from several research fields. Hence, research procedures and descriptions of the technical results often differ, sometimes widely. In this paper we focus on...

Full description

Saved in:
Bibliographic Details
Published in:Algorithms 2019, Vol.12 (7), p.127
Main Authors: Angriman, Eugenio, Grinten, Alexander van der, Looz, Moritz von, Meyerhenke, Henning, Nöllenburg, Martin, Predari, Maria, Tzovas, Charilaos
Format: Article
Language:English
Subjects:
Algorithms
applied graph algorithms
Approximation
Case studies
Computer science
Empirical analysis
Engineering
Evaluation
experimental algorithmics
Experiments
Guidelines
Mathematical programming
Modernization
Network analysis
Reproducibility
Statistical analysis
statistical analysis of algorithms
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The field of network science is a highly interdisciplinary area; for the empirical analysis of network data, it draws algorithmic methodologies from several research fields. Hence, research procedures and descriptions of the technical results often differ, sometimes widely. In this paper we focus on methodologies for the experimental part of algorithm engineering for network analysis—an important ingredient for a research area with empirical focus. More precisely, we unify and adapt existing recommendations from different fields and propose universal guidelines—including statistical analyses—for the systematic evaluation of network analysis algorithms. This way, the behavior of newly proposed algorithms can be properly assessed and comparisons to existing solutions become meaningful. Moreover, as the main technical contribution, we provide , a highly automated tool to perform and analyze experiments following our guidelines. To illustrate the merits of and our guidelines, we apply them in a case study: we design, perform, visualize and evaluate experiments of a recent algorithm for approximating betweenness centrality, an important problem in network analysis. In summary, both our guidelines and shall modernize and complement previous efforts in experimental algorithmics; they are not only useful for network analysis, but also in related contexts.
ISSN:1999-4893
1999-4893
DOI:10.3390/a12070127