License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.36
URN: urn:nbn:de:0030-drops-94403
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9440/
Carstens, Corrie Jacobien ;
Kleer, Pieter
Speeding up Switch Markov Chains for Sampling Bipartite Graphs with Given Degree Sequence
Abstract
We consider the well-studied problem of uniformly sampling (bipartite) graphs with a given degree sequence, or equivalently, the uniform sampling of binary matrices with fixed row and column sums. In particular, we focus on Markov Chain Monte Carlo (MCMC) approaches, which proceed by making small changes that preserve the degree sequence to a given graph. Such Markov chains converge to the uniform distribution, but the challenge is to show that they do so quickly, i.e., that they are rapidly mixing.
The standard example of this Markov chain approach for sampling bipartite graphs is the switch algorithm, that proceeds by locally switching two edges while preserving the degree sequence. The Curveball algorithm is a variation on this approach in which essentially multiple switches (trades) are performed simultaneously, with the goal of speeding up switch-based algorithms. Even though the Curveball algorithm is expected to mix faster than switch-based algorithms for many degree sequences, nothing is currently known about its mixing time. On the other hand, the switch algorithm has been proven to be rapidly mixing for several classes of degree sequences.
In this work we present the first results regarding the mixing time of the Curveball algorithm. We give a theoretical comparison between the switch and Curveball algorithms in terms of their underlying Markov chains. As our main result, we show that the Curveball chain is rapidly mixing whenever a switch-based chain is rapidly mixing. We do this using a novel state space graph decomposition of the switch chain into Johnson graphs. This decomposition is of independent interest.
BibTeX - Entry
@InProceedings{carstens_et_al:LIPIcs:2018:9440,
author = {Corrie Jacobien Carstens and Pieter Kleer},
title = {{Speeding up Switch Markov Chains for Sampling Bipartite Graphs with Given Degree Sequence}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {36:1--36:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-085-9},
ISSN = {1868-8969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9440},
URN = {urn:nbn:de:0030-drops-94403},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.36},
annote = {Keywords: Binary matrix, graph sampling, Curveball, switch, Markov chain decomposition, Johnson graph}
}
|
Keywords: |
|
Binary matrix, graph sampling, Curveball, switch, Markov chain decomposition, Johnson graph |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
13.08.2018 |
