Abstract
We consider the wellstudied 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 switchbased algorithms. Even though the Curveball algorithm is expected to mix faster than switchbased 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 switchbased 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:136:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9440},
URN = {urn:nbn:de:0030drops94403},
doi = {10.4230/LIPIcs.APPROXRANDOM.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 