MCMC methods for sampling graphs with given degree constraints

MCMC methods for sampling graphs with given degree constraints

Efficiently sampling graphs with given degree constraints is an important open problem, both in theory and practice. In this talk, Pieter Kleer will give an overview of some Markov Chain Monte Carlo algorithms for various type of degree constraints: Hard degree constraints, degree interval constraints and joint degree distribution constraints.

These algorithms are based on making small random changes (to a given initial graph) that preserve the desired 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 constraints, is close to the (uniform) stationary distribution of the induced Markov chain.

Based on joint work with Georgios Amanatidis (University of Essex).

Speaker

Pieter Kleer, Tilburg University

How to attend

If not a member of the Dept. Mathematical Science at the University of Essex, you can register your interest in attending the seminar and request the Zoom’s meeting password by emailing Dr Jesus Martinez-Garcia (jesus.martinez-garcia@essex.ac.uk)