MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

The switch Markov chain for the uniform sampling of graphs with given degrees

Pieter Kleer
CWI, Amsterdam
AG1 Mittagsseminar (own work)
AG 1, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 25 June 2019
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

The uniform generation of graphs with given degrees is an important problem in the analysis of complex networks. One of the simplest approaches to this problem is the switch Markov chain. Here, one repeatedly switches two edges uniformly at random, while preserving the degree sequence. How many switches are needed before the resulting network is close to a uniform sample from the set of all graphs with the given degrees? The answer to this question is still open for general degree sequences. In this talk we will present a novel proof approach for the analysis of the switch Markov chain, based on Sinclair's multi-commodity flow method. The analysis relies on combinatorial arguments (no knowledge of Markov chains is required beyond the basic definition). In particular, our proof approach allows us to extend the existing range of degree sequences for which the switch Markov chain is known to be rapidly mixing (the chain is called rapidly mixing if only a polynomial number of switches is needed to get close to a uniform sample). If time permits, we will also discuss an extension of the generation problem, where, in addition to the degree sequence, also degree correlations are specified.

Contact

Nitin Saurabh
--email hidden
passcode not visible
logged in users only

Nitin Saurabh, 06/24/2019 13:49
Nitin Saurabh, 06/21/2019 09:44
Nitin Saurabh, 03/19/2019 10:54 -- Created document.