Parallel Global Edge Switching for the Uniform Sampling of Simple Graphs with Prescribed Degrees

The uniform sampling of simple graphs matching a prescribed degree sequence is an important tool in network science, e.g., to construct graph generators or null-models. Here, the Edge Switching Markov Chain (ES-MC) is a common choice. Given an arbitrary simple graph with the required degree sequence...

Full description

Saved in:
Bibliographic Details
Main Authors: Allendorf, Daniel, Meyer, Ulrich, Penschuck, Manuel, Tran, Hung
Format: Conference Proceeding
Language:English
Subjects:
Data structures
degrees
Distributed processing
edge switching
Generators
markov chain
Markov processes
parallelism
random graphs
Runtime
Scalability
Switches
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The uniform sampling of simple graphs matching a prescribed degree sequence is an important tool in network science, e.g., to construct graph generators or null-models. Here, the Edge Switching Markov Chain (ES-MC) is a common choice. Given an arbitrary simple graph with the required degree sequence, ES-MC carries out a large number of small changes involving at most four edges to eventually obtain a uniform sample. In practice, reasonably short runs efficiently yield approximate uniform samples. We first engineer a simple sequential ES-MC implementation representing the graph in a hash-set. Despite its simplicity and to the best of our knowledge, our implementation significantly outperforms all openly available solutions. Secondly, we propose the Global Edge Switching Markov Chain (G-ES-MC) and show that it, too, converges to a uni-form distribution. We provide empirical evidence that G-ES-MC requires not more switches than ES-MC (and often fewer). Thirdly, we engineer shared-memory parallel algorithms for ES-MC and G-ES-MC; we find that they benefit from the easier dependency structure of the G-ES-MC. In an empirical evaluation, we demonstrate the scalability of our implementations.
ISSN:1530-2075
DOI:10.1109/IPDPS53621.2022.00034