The mixing time of switch Markov chains: a unified approach
From MaRDI portal
(Redirected from Publication:2237855)
Abstract: Since 1997 a considerable effort has been spent to study the mixing time of switch Markov chains on the realizations of graphic degree sequences of simple graphs. Several results were proved on rapidly mixing Markov chains on unconstrained, bipartite, and directed sequences, using different mechanisms. The aim of this paper is to unify these approaches. We will illustrate the strength of the unified method by showing that on any -stable family of unconstrained/bipartite/directed degree sequences the switch Markov chain is rapidly mixing. This is a common generalization of every known result that shows the rapid mixing nature of the switch Markov chain on a region of degree sequences. Two applications of this general result will be presented. One is an almost uniform sampler for power-law degree sequences with exponent . The other one shows that the switch Markov chain on the degree sequence of an ErdH{o}s-R'enyi random graph is asymptotically almost surely rapidly mixing if is bounded away from 0 and 1 by at least .
Recommendations
- Mixing time of the switch Markov chain and stable degree sequences
- Rapid mixing of the switch Markov chain for strongly stable degree sequences
- Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices
- The switch Markov chain for sampling irregular graphs and digraphs
- The switch Markov chain for sampling irregular graphs (extended abstract)
Cites work
- A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
- A remark on the existence of finite graphs
- A theorem on flows in networks
- Algorithms for constructing graphs and digraphs with given valences and factors
- Approximating the Permanent
- Combinatorial Properties of Matrices of Zeros and Ones
- Enumeration of graphs with a heavy-tailed degree sequence
- Fast uniform generation of regular graphs
- scientific article; zbMATH DE number 747036 (Why is no real title available?)
- scientific article; zbMATH DE number 6472593 (Why is no real title available?)
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Mixing time of the switch Markov chain and stable degree sequences
- On counting perfect matchings in general graphs
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- On the swap-distances of different realizations of a graphical degree sequence
- On the switch Markov chain for perfect matchings
- Polynomial-time counting and sampling of two-rowed contingency tables
- Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
- Rapid mixing of the switch Markov chain for strongly stable degree sequences
- Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices
- Sampling binary contingency tables with a greedy start
- Sampling Regular Graphs and a Peer-to-Peer Network
- Statistical problems involving permutations with restricted positions
- The switch Markov chain for sampling irregular graphs (extended abstract)
- The switch Markov chain for sampling irregular graphs and digraphs
- Towards random uniform sampling of bipartite graphs with given degree sequence
- Uniform generation of random graphs with power-law degree sequences
- Uniform sampling of digraphs with a fixed degree sequence
Cited in
(23)- Half-graphs, other non-stable degree sequences, and the switch Markov chain
- Mixing time of the switch Markov chain and stable degree sequences
- On the switch Markov chain for perfect matchings
- Rapid mixing of the switch Markov chain for 2-class joint degree matrices
- Moments of uniform random multigraphs with fixed degree sequences
- Rapid mixing of the switch Markov chain for strongly stable degree sequences
- Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices
- Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
- Cutoff for rewiring dynamics on perfect matchings
- Approximate sampling of graphs with near-P-stable degree intervals
- Sampling lattice points in a polytope: a Bayesian biased algorithm with random updates
- Regularized modified log-Sobolev inequalities and comparison of Markov chains
- Mixing time of the swap Markov chain and \(P\)-stability
- Uniform generation of temporal graphs with given degrees
- Approximate sampling and counting of graphs with near-regular degree intervals
- Fully graphic degree sequences and P-stable degree sequences
- A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
- Uniformly sampling random directed hypergraphs with fixed degrees
- Sequential stub matching for asymptotically uniform generation of directed graphs with a given degree sequence
- Dense, irregular, yet always-graphic 3-uniform hypergraph degree sequences
- Degree-preserving graph dynamics: a versatile process to construct random networks
- Irreducible Markov chains on spaces of graphs with fixed degree-color sequences
- DiNgHy: null models for non-degenerate directed hypergraphs
This page was built for publication: The mixing time of switch Markov chains: a unified approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2237855)
