Sampling graphs with a given degree sequence
Last updated on
Mar 23, 2019
Publications
A non-P-stable class of degree sequences for which the swap Markov chain is rapidly mixing
One of the simplest methods of generating a random graph with a given degree sequence is provided by the Monte Carlo Markov Chain …
The mixing time of switch Markov chains: a unified approach
We show that the switch Markov chain is rapidly mixing on $P$-stable degree sequences of simple, bipartite, and directed graphs. …
Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs
Since 1997 a considerable effort has been spent on the study of the swap (switch) Markov chains on graphic degree sequences. All of …
Talks
On the mixing time of switch Markov chains
Generating graphs with a given degree sequence uniformly and randomly is a challenging problem. One of the popular methods is the switch Markov chain, which is a Markov chain Monte Carlo method that takes a random walk on the set of realizations via switches.
Oct 29, 2020 2:15 PM — 3:45 PM
Alfréd Rényi Insitute of Mathematics
Mixing time of the swap Markov chain and P-stability (extended version)
Extended version of the talk of the same title given at EUROCOMB19
Nov 6, 2019 1:00 PM — 2:00 PM
University of Tasmania
Mixing time of the swap Markov chain and P-stability
The aim of this paper is to confirm that $P$-stability of a family of unconstrained/bipartite/directed degree sequences is sufficient …
Aug 30, 2019 4:25 PM — 4:50 PM
Bratislava, Slovakia
A non-stable bipartite degree sequence on which the swap Markov chain is rapidly mixing
The swap Markov chain on a bipartite degree sequence $d$ operates on realizations of $d$ by taking two-two vertices from each color …
Dec 13, 2018 2:15 PM — 3:45 PM
Alfréd Rényi Institute, Budapest