Sampling graphs with a given degree sequence
Last updated on
Mar 23, 2019
Publications
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. …
Half-graphs, other non-stable degree sequences, and the switch Markov chain
In this paper we give a non-trivial family of degree sequences that are not $P$-stable and the switch Markov chain is still rapidly mixing on them. This family has an intimate connection to Tyshkevich-decompositions and strong stability as well.
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