Approximate sampling of graphs with near-P-stable degree intervals

DOI10.1007/S00026-023-00678-8arXiv2204.09493OpenAlexW4390044175MaRDI QIDQ6192073FDOQ6192073

Authors: Péter L. Erdős, Tamás Róbert Mezei, István Miklós 

Publication date: 11 March 2024

Published in: Annals of Combinatorics (Search for Journal in Brave)

Abstract: The approximate uniform sampling of graph realizations with a given degree sequence is an everyday task in several social science, computer science, engineering etc. projects. One approach is using Markov chains. The best available current result about the well-studied switch Markov chain is that it is rapidly mixing on P-stable degree sequences (see DOI:10.1016/j.ejc.2021.103421). The switch Markov chain does not change any degree sequence. However, there are cases where degree intervals are specified rather than a single degree sequence. (A natural scenario where this problem arises is in hypothesis testing on social networks that are only partially observed.) Rechner, Strowick, and M"uller-Hannemann introduced in 2018 the notion of degree interval Markov chain which uses three (separately well-studied) local operations (switch, hinge-flip and toggle), and employing on degree sequence realizations where any two sequences under scrutiny have very small coordinate-wise distance. Recently Amanatidis and Kleer published a beautiful paper (arXiv:2110.09068), showing that the degree interval Markov chain is rapidly mixing if the sequences are coming from a system of very thin intervals which are centered not far from a regular degree sequence. In this paper we extend substantially their result, showing that the degree interval Markov chain is rapidly mixing if the intervals are centred at P-stable degree sequences.

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

Recommendations

• 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 strongly stable degree sequences
• Mixing time of the switch Markov chain and stable degree sequences
• Half-graphs, other non-stable degree sequences, and the switch Markov chain
• The switch Markov chain for sampling irregular graphs (extended abstract)

zbMATH Keywords

P-stabilitydegree sequencesrealizationsrapidly mixingswitch Markov chainSinclair's multi-commodity flow methodweak P-stability

Mathematics Subject Classification ID

Applications of graph theory (05C90) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Graph theory (including graph drawing) in computer science (68R10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cites Work

• Title not available (Why is that?)
• Fast uniform generation of regular graphs
• Approximating the Permanent
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Title not available (Why is that?)
• Sampling Regular Graphs and a Peer-to-Peer Network
• The switch Markov chain for sampling irregular graphs (extended abstract)
• Generating Random Networks and Graphs
• The mixing time of switch Markov chains: a unified approach
• Uniform sampling of bipartite graphs with degrees in prescribed intervals

Cited In (2)

• Approximate sampling and counting of graphs with near-regular degree intervals
• Fully graphic degree sequences and P-stable degree sequences

This page was built for publication: Approximate sampling of graphs with near-\(P\)-stable degree intervals

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