Dresden 2020 – wissenschaftliches Programm

Die DPG-Frühjahrstagung in Dresden musste abgesagt werden! Lesen Sie mehr ...

Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

SOE: Fachverband Physik sozio-ökonomischer Systeme

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

SOE 11.3: Vortrag

Mittwoch, 18. März 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.