Geometric Inhomogeneous Random Graphs for Algorithm Engineering

The design and analysis of graph algorithms is heavily based on the worst case.
In practice, however, many algorithms perform much better than the worst case would suggest.
Furthermore, various problems can be tackled more efficiently if one assumes the input to be, in a sense, realistic.
The field of network science, which studies the structure and emergence of real-world networks, identifies locality and heterogeneity as two frequently occurring properties.

A popular model that captures these properties are geometric inhomogeneous random graphs (GIRGs), which is a generalization of hyperbolic random graphs (HRGs).
Aside from their importance to network science, GIRGs can be an immensely valuable tool in algorithm engineering.
Since they convincingly mimic real-world networks, guarantees about quality and performance of an algorithm on instances of the model can be transferred to real-world applications.
They have model parameters to control the amount of heterogeneity and locality, which allows to evaluate those properties in isolation while keeping the rest fixed.
Moreover, they can be efficiently generated which allows for experimental analysis.
... mehr
While realistic instances are often rare, generated instances are readily available.
Furthermore, the underlying geometry of GIRGs helps to visualize the network, e.g.,~for debugging or to improve understanding of its structure.

The aim of this work is to demonstrate the capabilities of geometric inhomogeneous random graphs in algorithm engineering and establish them as routine tools to replace previous models like the Erd\H{o}s-R{\'e}nyi model, where each edge exists with equal probability.
We utilize geometric inhomogeneous random graphs to design, evaluate, and optimize efficient algorithms for realistic inputs.
In detail, we provide the currently fastest sequential generator for GIRGs and HRGs and describe algorithms for maximum flow, directed spanning arborescence, cluster editing, and hitting set.
For all four problems, our implementations beat the state-of-the-art on realistic inputs.

On top of providing crucial benchmark instances, GIRGs allow us to obtain valuable insights.
Most notably, our efficient generator allows us to
experimentally show sublinear running time of our flow algorithm,
investigate the solution structure of cluster editing,
complement our benchmark set of arborescence instances with a density for which there are no real-world networks available,
and generate networks with adjustable locality and heterogeneity to reveal the effects of these properties on our algorithms.