Efficiently sampling the realizations of irregular, but linearly bounded bipartite and directed degree sequences
arXiv:1712.01709 · doi:10.1371/journal.pone.0201995
Abstract
Since 1997 a considerable effort has been spent on the study of the swap (switch) Markov chains on graphic degree sequences. Several results were proved on rapidly mixing Markov chains on regular simple, on regular directed, on half-regular directed and on half-regular bipartite degree sequences. In this paper, the main result is the following: Let and be disjoint finite sets, and let and be integers. Furthermore, assume that the bipartite degree sequence on satisfies and . Finally assume that . Then the swap Markov chain on this bipartite degree sequence is rapidly mixing. The technique applies on directed degree sequences as well, with very similar parameter values. These results are germane to the recent results of Greenhill and Sfragara about fast mixing MCMC processes on simple and directed degree sequences, where the maximum degrees are $O(\sqrt{\# \mbox{ of edges}})$. The results are somewhat comparable on directed degree sequences: while the GS results are better applicable for degree sequences developed under some scale-free random process, our new results are better fitted to degree sequences developed under the Erdős -- Rényi model. For example our results cover all regular degree sequences, the GS model is not applicable when the average degree is
arXiv comment20 pages. arXiv admin note: text overlap with arXiv:1301.7523
References in corpus (5)
- On the swap-distances of different realizations of a graphical degree sequence
- Constructing, sampling and counting graphical realizations of restricted degree sequences
- The switch Markov chain for sampling irregular graphs
- A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
- A decomposition based proof for fast mixing of a Markov chain over balanced realizations of a joint degree matrix