The switch Markov chain for sampling irregular graphs (extended abstract)

DOI10.1137/1.9781611973730.103MaRDI QIDQ5363053zbMATH OpenOpenAlexFDO

Authors Catherine Greenhill

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.103

Mathematics Subject Classification ID

Vertex degrees (05C07) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Recommendations

• The switch Markov chain for sampling irregular graphs and digraphs
• 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
• Rapid mixing of the switch Markov chain for 2-class joint degree matrices
• A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs

Cited in

(29)

• Mixing times of random walks on dynamic configuration models
• The switch Markov chain for sampling irregular graphs and digraphs
• Towards random uniform sampling of bipartite graphs with given degree sequence
• Switch-based Markov chains for sampling Hamiltonian cycles in dense graphs
• The mixing time of switch Markov chains: a unified approach
• Sampling regular graphs and a peer-to-peer network
• A survey of discrete methods in (algebraic) statistics for networks
• Uniform sampling of digraphs with a fixed degree sequence
• Sampling Edge Covers in 3-Regular Graphs
• Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
• Configuring random graph models with fixed degree sequences
• New classes of degree sequences with fast mixing swap Markov chain sampling
• Uniform generation of random regular graphs
• Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
• Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence
• Parallel and I/O-efficient randomisation of massive networks using global curveball trades
• Rapid mixing of the switch Markov chain for 2-class joint degree matrices
• Moments of uniform random multigraphs with fixed degree sequences
• Fast sequential creation of random realizations of degree sequences
• Fast uniform generation of random graphs with given degree sequences
• Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs
• Improved baselines for causal structure learning on interventional data
• Approximate sampling of graphs with near-P-stable degree intervals
• The switch Markov chain for sampling irregular graphs
• Regularized modified log-Sobolev inequalities and comparison of Markov chains
• Linear-time uniform generation of random sparse contingency tables with specified marginals
• A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
• How to determine if a random graph with a fixed degree sequence has a giant component
• Hypercurveball algorithm for sampling hypergraphs with fixed degrees

This page was built for publication: The switch Markov chain for sampling irregular graphs (extended abstract)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363053)