Mixing time of the switch Markov chain and stable degree sequences

DOI10.1016/J.DAM.2020.12.004MaRDI QIDQ2659068zbMATH OpenOpenAlexFDO

Authors 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 timemulticommodity flowpower-law degree sequencesstable degree sequencesswitch Markov chainswitching

Mathematics Subject Classification ID

Vertex degrees (05C07) 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)

Abstract: The switch chain is a well-studied Markov chain which can be used to sample approximately uniformly from the set $$ of all graphs with a given degree sequence $$. Polynomial mixing time (rapid mixing) has been established for the switch chain under various conditions on the degree sequences. Amanatidis and Kleer introduced the notion of strongly stable families of degree sequences, and proved that the switch chain is rapidly mixing for any degree sequence from a strongly stable family. Using a different approach, ErdH{o}s et al. recently extended this result to the (possibly larger) class of P-stable degree sequences, introduced by Jerrum and Sinclair in 1990. We define a new notion of stability for a given degree sequence, namely $k$-emph{stability}, and prove that if a degree sequence $$ is 8-stable then the switch chain on $$ is rapidly mixing. We also provide sufficient conditions for P-stability, strong stability and 8-stability. Using these sufficient conditions, we give the first proof of P-stability for various families of heavy-tailed degree sequences, including power-law degree sequences, and show that the switch chain is rapidly mixing for these families. We further extend these notions and results to directed degree sequences.

Recommendations

• Rapid mixing of the switch Markov chain for strongly stable degree sequences
• The mixing time of switch Markov chains: a unified approach
• Rapid mixing of the switch Markov chain for strongly stable degree sequences and 2-class joint degree matrices
• Half-graphs, other non-stable degree sequences, and the switch Markov chain
• The switch Markov chain for sampling irregular graphs and digraphs

Cites work

• A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
• A sequential algorithm for generating random graphs
• A theorem on flows in networks
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Enumeration of graphs with a heavy-tailed degree sequence
• Fast uniform generation of regular graphs
• Generating random regular graphs
• Generating Random Regular Graphs Quickly
• scientific article; zbMATH DE number 3878944 (Why is no real title available?)
• scientific article; zbMATH DE number 1334601 (Why is no real title available?)
• scientific article; zbMATH DE number 747036 (Why is no real title available?)
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• New classes of degree sequences with fast mixing swap Markov chain sampling
• Random graphs and complex networks. Volume 1
• 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
• The Structure and Function of Complex Networks
• The switch Markov chain for sampling irregular graphs and digraphs
• The Volume of the Giant Component of a Random Graph with Given Expected Degrees
• Towards random uniform sampling of bipartite graphs with given degree sequence
• Uniform generation of random graphs with power-law degree sequences
• Uniform generation of random regular graphs of moderate degree
• Uniform sampling of digraphs with a fixed degree sequence

Cited in

(13)

• The switch Markov chain for sampling irregular graphs and digraphs
• Half-graphs, other non-stable degree sequences, and the switch Markov chain
• The mixing time of switch Markov chains: a unified approach
• Mixing times of Markov chains on 3-orientations of planar triangulations
• On the switch Markov chain for perfect matchings
• 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
• Approximate sampling of graphs with near-P-stable degree intervals
• Mixing time of the swap Markov chain and \(P\)-stability
• 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
• Sequential stub matching for asymptotically uniform generation of directed graphs with a given degree sequence
• Degree-preserving graph dynamics: a versatile process to construct random networks

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

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