Mixing time of the switch Markov chain and stable degree sequences

DOI10.1016/j.dam.2020.12.004zbMath1460.05038arXiv2003.08497OpenAlexW3115223890MaRDI QIDQ2659068

Pu Gao, Catherine Greenhill

Publication date: 25 March 2021

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.08497

zbMATH Keywords

mixing timeswitchingmulticommodity flowswitch Markov chainpower-law degree sequencesstable degree sequences

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Discrete-time Markov processes on general state spaces (60J05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Vertex degrees (05C07)

Related Items (2)

The mixing time of switch Markov chains: a unified approach ⋮ Half-graphs, other non-stable degree sequences, and the switch Markov chain

Cites Work

• 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
• A theorem on flows in networks
• Enumeration of graphs with a heavy-tailed degree sequence
• Fast uniform generation of regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• The switch Markov chain for sampling irregular graphs and digraphs
• Towards random uniform sampling of bipartite graphs with given degree sequence
• Random Graphs and Complex Networks
• Uniform Sampling of Digraphs with a Fixed Degree Sequence
• The Volume of the Giant Component of a Random Graph with Given Expected Degrees
• Uniform generation of random regular graphs of moderate degree
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• The Structure and Function of Complex Networks
• Uniform generation of random graphs with power-law degree sequences
• New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling
• Generating Random Regular Graphs Quickly
• Rapid Mixing of the Switch Markov Chain for Strongly Stable Degree Sequences and 2-Class Joint Degree Matrices
• Sampling Regular Graphs and a Peer-to-Peer Network
• Generating random regular graphs

This page was built for publication: Mixing time of the switch Markov chain and stable degree sequences