The switch Markov chain for sampling irregular graphs

DOI10.1137/1.9781611973730.103MaRDI QIDQ6257346arXivFDO

Authors Catherine Greenhill

Publication date 16 December 2014

Published in arXiv

Full work available at URL https://doi.org/10.1137/1.9781611973730.103

Mathematics Subject Classification ID

Vertex degrees (05C07) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

arXiv classification

cs.DSmath.CO

Abstract: The problem of efficiently sampling from a set of(undirected) graphs with a given degree sequence has many applications. One approach to this problem uses a simple Markov chain, which we call the switch chain, to perform the sampling. The switch chain is known to be rapidly mixing for regular degree sequences. We prove that the switch chain is rapidly mixing for any degree sequence with minimum degree at least 1 and with maximum degree $d_{max}$ which satisfies $3leq{d}_{max}leqfrac14,sqrtM$, where $M$ is the sum of the degrees. The mixing time bound obtained is only an order of $n$ larger than that established in the regular case, where $n$ is the number of vertices.

This page was built for publication: The switch Markov chain for sampling irregular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6257346)