Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The switch Markov chain for the uniform sampling of graphs with given degrees
Speaker:Pieter Kleer
coming from:CWI, Amsterdam
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 25 June 2019
Time:13:00
Duration:30 Minutes
Location:Saarbr├╝cken
Building:E1 4
Room:024
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
Name(s):Nitin Saurabh
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Nitin Saurabh, 06/24/2019 01:49 PM
  • Nitin Saurabh, 06/21/2019 09:44 AM
  • Nitin Saurabh, 03/19/2019 10:54 AM -- Created document.