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

DOI10.1007/S00026-023-00678-8MaRDI QIDQ6192073zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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)

Cites work

• scientific article; zbMATH DE number 1334601 (Why is no real title available?)
• scientific article; zbMATH DE number 747036 (Why is no real title available?)
• Approximating the Permanent
• Fast uniform generation of regular graphs
• Generating Random Networks and Graphs
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Sampling Regular Graphs and a Peer-to-Peer Network
• The mixing time of switch Markov chains: a unified approach
• The switch Markov chain for sampling irregular graphs (extended abstract)
• 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)