Connectivity matters: Construction and exact random sampling of connected graphs

Horv'at, Szabolcs; Modes, Carl D.

We describe a new method for the random sampling of connected graphs with a specified degree sequence. We consider both the case of simple graphs and that of loopless multigraphs. Our method builds on a recently introduced novel sampling approach that constructs graphs independently (unlike edge-switching Markov Chain Monte Carlo methods) and efficiently (unlike the configuration model), and extends it to incorporate the constraint of connectivity. Additionally, we present a simple and elegant algorithm for directly constructing a single connected realization of a degree sequence, either as a simple graph or a multigraph. Finally, we demonstrate our sampling method on a realistic scale-free example, as well as on degree sequences of connected real-world networks.