The switch Markov chain for sampling irregular graphs

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 $3\le d_{\max }\le \frac{1}{4}\sqrt{M}$, 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.

9 pages, 5 figures, to appear in proceedings of SODA 2015

References in corpus (3)

• Constructing, sampling and counting graphical realizations of restricted degree sequences
• Expand and Contract: Sampling graphs with given degrees and other combinatorial families
• Corrigendum: Sampling regular graphs and a peer-to-peer network

Cited by in corpus (8)

• The mixing time of the switch Markov chains: a unified approach
• How to determine if a random graph with a fixed degree sequence has a giant component
• Efficiently sampling the realizations of irregular, but linearly bounded bipartite and directed degree sequences
• Measuring Directed Triadic Closure with Closure Coefficients
• Uniform generation of random regular graphs
• Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
• Uniform generation of random graphs with power-law degree sequences
• Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings