A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix

DOI10.1137/130929874zbMath1311.05084arXiv1307.5295OpenAlexW3100769682MaRDI QIDQ5251622

István Miklós, Péter L. Erdős, Zoltán Toroczkai

Publication date: 20 May 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

joint degree matrixgraph samplingrapidly mixing Markov chains

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Random walks on graphs (05C81)

Related Items (8)

Unnamed Item ⋮ The switch Markov chain for sampling irregular graphs and digraphs ⋮ A survey of discrete methods in (algebraic) statistics for networks ⋮ Exact sampling of graphs with prescribed degree correlations ⋮ New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling ⋮ Half-graphs, other non-stable degree sequences, and the switch Markov chain ⋮ An algebraic Monte-Carlo algorithm for the partition adjacency matrix realization problem ⋮ Rapid Mixing of the Switch Markov Chain for 2-Class Joint Degree Matrices

Cites Work

• Unnamed Item
• Unnamed Item
• On realizations of a joint degree matrix
• On the Diaconis-Gangolli Markov chain for sampling contingency tables with cell-bounded entries
• Geometric bounds for eigenvalues of Markov chains
• Relations between graphs and integer-pair sequences
• Comparison theorems for reversible Markov chains
• Markov chain decomposition for convergence rate analysis
• Negative examples for sequential importance sampling of binary contingency tables
• Towards random uniform sampling of bipartite graphs with given degree sequence
• Efficient importance sampling for binary contingency tables
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• Approximating the Permanent
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• Robust Mixing
• Degree-based graph construction
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• A general limitation on Monte Carlo algorithms of the Metropolis type
• Constructing and sampling directed graphs with given degree sequences
• Approximately Counting Integral Flows and Cell-Bounded Contingency Tables
• Constructing and sampling graphs with a prescribed joint degree distribution
• Sampling Regular Graphs and a Peer-to-Peer Network
• Disjoint Decomposition of Markov Chains and Sampling Circuits in Cayley Graphs
• Sequential Monte Carlo Methods for Statistical Analysis of Tables
• Sampling binary contingency tables with a greedy start

This page was built for publication: A Decomposition Based Proof for Fast Mixing of a Markov Chain over Balanced Realizations of a Joint Degree Matrix