The DPG Spring Meeting in Dresden had to be cancelled! Read more ...

Parts | Days | Selection | Search | Updates | Downloads | Help

SOE: Fachverband Physik sozio-ökonomischer Systeme

SOE 11: Networks - From Topology to Dynamics I (joint SOE/DY/BP)

SOE 11.3: Talk

Wednesday, March 18, 2020, 18:00–18:15, GÖR 226

Exact sampling of connected graphs with a given degree sequence — •Szabolcs Horvát and Carl Modes — Center for Systems Biology Dresden

Sampling random graphs with various constraints is an essential tool for network analysis and modelling, with the connectedness of graph being a common additional requirement. Here we present an algorithm to sample simple connected graphs with a given degree sequence. Most current methods fall into two categories, each with its specific limitations: 1. Rejection-based sampling, such as the configuration model, cannot handle dense graphs due to a very high rate of rejections. 2. Methods based on Markov-chain Monte Carlo cannot guarantee the independence of samples due to unknown mixing times. Recently, a new rejection-free class of methods was proposed that can sample with exact probabilities and generates the sampling weight together with each sample. We describe and implement a generalisation of these methods to sample from the set of connected realisations.