English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals

Amanatidis, G., & Kleer, P. (2021). Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals. Retrieved from https://arxiv.org/abs/2110.09068.

Item is

Files

show Files
hide Files
:
arXiv:2110.09068.pdf (Preprint), 359KB
Name:
arXiv:2110.09068.pdf
Description:
File downloaded from arXiv at 2022-01-05 11:36
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Amanatidis, Georgios1, Author
Kleer, Pieter2, Author           
Affiliations:
1External Organizations, ou_persistent22              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: Computer Science, Discrete Mathematics, cs.DM,Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Combinatorics, math.CO
 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 an extension of the problem, where degree intervals are specified
rather than a single degree sequence. We are interested in sampling and
counting graphs whose degree sequences satisfy the degree interval constraints.
A natural scenario where this problem arises is in hypothesis testing on social
networks that are only partially observed.
In this work, 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, in which every node $i$ has a degree from an interval not too
far away from a given $d \in \N$. In order to design our FPAUS, we rely on
various state-of-the-art tools from Markov chain theory and combinatorics. In
particular, we provide the first non-trivial algorithmic application of a
breakthrough result of Liebenau and Wormald (2017) regarding an asymptotic
formula for the number of graphs with a given near-regular degree sequence.
Furthermore, we also make use of the recent breakthrough of Anari et al. (2019)
on sampling a base of a matroid under a strongly log-concave probability
distribution.
As a more direct approach, we also study a natural Markov chain recently
introduced by Rechner, Strowick and M\"uller-Hannemann (2018), based on three
simple local operations: Switches, hinge flips, and additions/deletions of a
single edge. We obtain the first theoretical results for this Markov chain by
showing it is rapidly mixing for the case of near-regular degree intervals of
size at most one.

Details

show
hide
Language(s): eng - English
 Dates: 2021-10-182021
 Publication Status: Published online
 Pages: 26 p.
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 2110.09068
URI: https://arxiv.org/abs/2110.09068
BibTex Citekey: Amanatidis_2110.09068
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show