MCMC methods for sampling graphs with given degree constraints

  • Thu 18 Nov 21

    15:00 - 16:00

  • Online


  • Event speaker

    Pieter Kleer

  • Event type

    Lectures, talks and seminars

  • Event organiser

    Mathematics, Statistics and Actuarial Science, School of

  • Contact details

    Jesus Martinez-Garcia

These Departmental Seminars are for everyone in Maths. We encourage anyone interested in the subject in general, or in the particular subject of the seminar, to come along. It's a great opportunity to meet people in the Maths Department and join in with our community.

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


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)