# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Approximate Sampling and Counting of Graphs with Near-Regular Degree Intervals

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2110.09068.pdf

(Preprint), 359KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

Cite as: https://hdl.handle.net/21.11116/0000-0009-B839-8

##### 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.

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.