License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2023.7
URN: urn:nbn:de:0030-drops-176596
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17659/
Amanatidis, Georgios ;
Kleer, Pieter
Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals
Abstract
The approximate uniform sampling of graphs with a given degree sequence is a well-known, extensively studied problem in theoretical computer science and has significant applications, e.g., in the analysis of social networks. In this work we study a generalization of the problem, where degree intervals are specified instead of a single degree sequence. We are interested in sampling and counting graphs whose degree sequences satisfy the corresponding degree interval constraints. A natural scenario where this problem arises is in hypothesis testing on networks that are only partially observed. We provide the first fully polynomial almost uniform sampler (FPAUS) as well as the first fully polynomial randomized approximation scheme (FPRAS) for sampling and counting, respectively, graphs with near-regular degree intervals, i.e., graphs in which every node has a degree from an interval not too far away from a given r ∈ ℕ. In order to design our FPAUS, we rely on various state-of-the-art tools from Markov chain theory and combinatorics. In particular, by carefully using Markov chain decomposition and comparison arguments, we reduce part of our problem to the recent breakthrough of Anari, Liu, Oveis Gharan, and Vinzant (2019) on sampling a base of a matroid under a strongly log-concave probability distribution, and we provide the first non-trivial algorithmic application of a breakthrough asymptotic enumeration formula of Liebenau and Wormald (2017). As a more direct approach, we also study a natural Markov chain recently introduced by Rechner, Strowick and Müller-Hannemann (2018), based on three local operations - switches, hinge flips, and additions/deletions of an edge. We obtain the first theoretical results for this Markov chain, showing it is rapidly mixing for the case of near-regular degree intervals of size at most one.
BibTeX - Entry
@InProceedings{amanatidis_et_al:LIPIcs.STACS.2023.7,
author = {Amanatidis, Georgios and Kleer, Pieter},
title = {{Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {7:1--7:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-266-2},
ISSN = {1868-8969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17659},
URN = {urn:nbn:de:0030-drops-176596},
doi = {10.4230/LIPIcs.STACS.2023.7},
annote = {Keywords: graph sampling, degree interval, degree sequence, Markov Chain Monte Carlo method, switch Markov chain}
}
|
Keywords: |
|
graph sampling, degree interval, degree sequence, Markov Chain Monte Carlo method, switch Markov chain |
|
Collection: |
|
40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
03.03.2023 |
