The switch Markov chain for sampling irregular graphs and digraphs
From MaRDI portal
Publication:1704570
DOI10.1016/j.tcs.2017.11.010zbMath1395.60079arXiv1701.07101OpenAlexW2963129838MaRDI QIDQ1704570
Matteo Sfragara, Catherine Greenhill
Publication date: 12 March 2018
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1701.07101
Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Vertex degrees (05C07)
Related Items (12)
I/O-Efficient Generation of Massive Graphs Following the LFR Benchmark ⋮ Mixing time of the switch Markov chain and stable degree sequences ⋮ Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs ⋮ Unnamed Item ⋮ Network-Ensemble Comparisons with Stochastic Rewiring and Von Neumann Entropy ⋮ Sampling hypergraphs with given degrees ⋮ Empirical spectral distributions of sparse random graphs ⋮ The mixing time of switch Markov chains: a unified approach ⋮ Half-graphs, other non-stable degree sequences, and the switch Markov chain ⋮ Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings ⋮ Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices ⋮ A triangle process on regular graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A sequential algorithm for generating random graphs
- A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
- Enumeration of graphs with a heavy-tailed degree sequence
- Fast uniform generation of regular graphs
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- Decomposition of graphical sequences and unigraphs
- Algebraic algorithms for sampling from conditional distributions
- Towards random uniform sampling of bipartite graphs with given degree sequence
- Subgraphs of Dense Random Graphs with Specified Degrees
- Random dense bipartite graphs and directed graphs with specified degrees
- Uniform Sampling of Digraphs with a Fixed Degree Sequence
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- Combinatorial Properties of Matrices of Zeros and Ones
- Uniform generation of random regular graphs of moderate degree
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Generating Random Regular Graphs Quickly
- Generalized Monte Carlo significance tests
- The number of graphs and a random graph with a given degree sequence
- A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix
- The switch Markov chain for sampling irregular graphs (Extended Abstract)
- Sampling Regular Graphs and a Peer-to-Peer Network
- A Short Proof of the Factor Theorem for Finite Graphs
- Generating random regular graphs
This page was built for publication: The switch Markov chain for sampling irregular graphs and digraphs