- This event has passed.
Eindhoven SPOR Seminar
Sep 27, 2022, 15:45 - 16:45
Pieter Kleer (TiSEM)
Uniform Sampling of Graphs with given Degree Intervals
Efficiently sampling graphs with given degree constraints is an important open problem, both in theory and practice. In this talk, I will consider the problem of sampling graphs with given degree intervals. The goal is to efficiently generate a uniform random sample from the set of all graphs whose node degrees lie within a prespecified interval. This generalizes the well-known problem of sampling graphs with a given degree sequence.
We consider Markov Chain Monte Carlo methods that are based on making small random changes (to a given initial graph) that preserve the degree interval constraints. The goal is to understand how many of these small changes are needed until the resulting distribution, over the set of all graphs satisfying the given degree intervals, is close to the (uniform) stationary distribution of the induced Markov chain.
In order to analyse our Markov chains, we use a variety of tools from (discrete) Markov chain theory, such as Markov chain decomposition and the breakthrough work of Anari et al. (2019) regarding the sampling of matroid bases under strongly log-concave stationary distributions.
Based on joint ongoing work with Georgios Amanatidis (University of Essex).
For upcoming events of the SPOR seminar, as well as a history of previous talks, see: https://www.eurandom.tue.nl/eindhoven-spor-seminar/.