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_18: In 1999 Kannan, Tet ali and Vempala proposed a MCMC method to uniformly sample all possible realizations of a given graphical degree sequence and conjectured its rapidly mixing nature. Recently their conjecture was proved affirmative for regular graphs (by Cooper, Dyer and Greenhill, 2007), for regular directed graphs (by Greenhill, 2011) and for half-regular bipartite graphs (by Miklos, Erdős and Soukup, 2013). Several heuristics on counting the number of possible realizations exist (via sampling processes), and while they work well in practice, so far no approximation guarantees exist for such an approach. This paper is the first to develop a method for counting realizations with provable approximation guarantee. In fact, we solve a slightly more general problem; besides the graphical degree sequence a small set of forbidden edges is also given. We show that for the general problem (which contains the Greenhill problem and the Miklos, Erdős and Soukup problem as special cases) the derived MCMC process is rapidly mixing. Further, we show that this new problem is self-reducible therefore it provides a fully polynomial randomized approximation scheme (a.k.a. FPRAS) for counting of all realizations.
@cite_23: The problem of generating a random (0, l)-matrix with given marginals oc curs in different contexts. We mention two instances. Wilson (1987) considered the incidence and non-incidence of 56 species of birds in 28 islands of Vanuatu. The data can be represented by a 56 x 28 matrix A where the (i, j)-entry is 1 or 0 according as the z-th species is present on the j-th island or not. He wanted to test the null hypothesis that the occurrence of the species on the islands is random in the sense that all possible incidence matrices are equally likely, using cooccurrences of species. Since the chance of occurrence of a species on an island depends on how numerous the species is and on the capacity of the island which are indicated by the row total of A corresponding to the species and the column total of A corresponding to the island, he assumed that only those (0,1)-mat rices which have the same row sums as those of A and the same column sums as those of A are possible. To estimate the distribution of any statistic by simulation, one has to generate a random (0, l)-matrix with the given marginals. Another instance where one has to generate a random (0, l)-matrix with given marginals occurs in the analysis of social networks. A social network is
For any directed degree sequence @math , it follows from @cite_23 that the state space @math is connected if the set of transitions of the directed switch chain is expanded to also allow the reversal of directed 3-cycles. In the bipartite setting, this corresponds to an adaptation of the chain (for undirected graphs) which sometimes replaces 3 edges per step, rather than 2. Erd o @cite_18 proved that this chain is rapidly mixing for half-regular bipartite graphs with a forbidden matching, where a bipartite graph is half-regular if one vertex bipartition is regular. This gives an alternative Markov chain for sampling regular directed graphs, for any degree, including dense regular directed graphs.