The problem of efficiently sampling from a set of (undirected, or directed) 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, both in the undirected and directed setting. We prove that the switch chain for undirected graphs is rapidly mixing for any degree sequence with minimum degree at least 1 and with maximum degree @math which satisfies @math , where @math is the sum of the degrees. The mixing time bound obtained is only a factor @math larger than that established in the regular case, where @math is the number of vertices. Our result covers a wide range of degree sequences, including power-law graphs with parameter @math and sufficiently many edges. For directed degree sequences such that the switch chain is irreducible, we prove that the switch chain is rapidly mixing when all in-degrees and out-degrees are positive and bounded above by @math , where @math is the number of arcs, and not all in-degrees and out-degrees equal 1. The mixing time bound obtained in the directed case is an order of @math larger than that established in the regular case.
@cite_15: Let Δ and n be natural numbers such that Δn = 2m is even and Δ ⩽ (2 log n )1 2 - 1. Then as n →, the number of labelled Δ-regular graphs on n vertices is asymptotic to e − λ − λ 2 ( 2 m ) ! m ! 2 m ( Δ ! ) m where λ = (Δ -1) 2. As a consequence of the method we determine the asymptotic distribution of the number of short cycles in graphs with a given degree sequence, and give analogous formulae for hypergraphs.
@cite_13: Abstract We show how to generate k -regular graphs on n vertices uniformly at random in expected time O ( nk 3 ), provided k = O(n 1 3 ) . The algorithm employs a modification of a switching argument previously used to count such graphs asymptotically for k = o(n 1 3 ) . The asymptotic formula is re-derived, using the new switching argument. The method is applied also to graphs with given degree sequences, provided certain conditions are met. In particular, it applies if the maximum degree is O(∥E(G)∥ 1 4 ) . The method is also applied to bipartite graphs.
There are several approaches to the problem of sampling graphs (or directed graphs) with a given degree sequence, though none is known to be efficient for all degree sequences. First we consider undirected graphs. The configuration model of Bollob ' a s @cite_15 gives expected polynomial time uniform sampling if @math . McKay and Wormald @cite_13 adapted the configuration model to give an algorithm which performs uniform sampling from @math in expected polynomial time when @math .