Efficient sampling of graphs with arbitrary degree sequence

Uniform sampling of graphs from a given degree sequence is a fundamental component of measurements on networks, with applications ranging from epidemics through social networks to Internet modeling. Existing graph sampling methods are ill-controlled, with typically unknown mixing times for edge-swap methods and uncontrolled rejections for stub-matching ones. We propose an efficient, polynomial time algorithm that generates statistically independent graph samples from any given degree sequence. The algorithm provides a weight for each sample, allowing observables to be measured uniformly or following any desired distribution over the graph ensemble. Unlike other algorithms, this method always produces a sample, without back-trackings or rejections. For large number of nodes and degree sequences admitting many realizations, the sample weights follow a lognormal distribution. We also propose a fast implementation of the Erd\H{o}s-Gallai degree sequence graphicality test that is used in our algorithm, but is also of general utility.