The switch Markov chain for sampling irregular graphs and digraphs

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

zbMATH Keywords

graphMarkov chaindirected graphdegree sequence

Mathematics Subject Classification ID

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