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, ES-MC carries out a large number of small changes, called edge switches, to eventually obtain a uniform sample. In practice, reasonably short runs efficiently yield approximate uniform samples. In this work, we study the problem of executing edge switches in parallel. We discuss parallelizations of ES-MC, but find that this approach suffers from complex dependencies between edge switches. For this reason, we propose the Global Edge Switching Markov Chain (G-ES-MC), an ES-MC variant with simpler dependencies. We show that G-ES-MC converges to the uniform distribution and design shared-memory parallel algorithms for ES-MC and G-ES-MC. In an empirical evaluation, we provide evidence that G-ES-MC requires not more switches than ES-MC (and often fewer), and demonstrate the efficiency and scalability of our parallel G-ES-MC implementation.
Author: | Daniel AllendorfORCiD, Ulrich MeyerORCiDGND, Manuel PenschuckORCiDGND, Hung TranGND |
---|---|
URN: | urn:nbn:de:hebis:30:3-865117 |
URL: | https://arxiv.org/abs/2111.03005v2 |
DOI: | https://doi.org/10.48550/ARXIV.2111.03005 |
ArXiv Id: | http://arxiv.org/abs/2111.03005v2 |
Parent Title (English): | arXiv |
Publisher: | arXiv |
Document Type: | Preprint |
Language: | English |
Date of Publication (online): | 2023/02/15 |
Date of first Publication: | 2023/02/15 |
Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Release Date: | 2024/08/14 |
Tag: | Edge Switching; Markov Chain; Parallelism; Random Graph; Uniform Sampling |
Issue: | 2111.03005v2 |
Edition: | Version 2 |
Page Number: | 24 |
Institutes: | Informatik und Mathematik / Informatik |
Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Sammlungen: | Universitätspublikationen |
Licence (German): | Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International |