title: Efficient and exact sampling of simple graphs with given arbitrary degree sequence.
abstract: Uniform sampling from graphical realizations of a given degree sequence is a fundamental component in simulation-based measurements of network observables, with applications ranging from epidemics, through social networks to Internet modeling. Existing graph sampling methods are either link-swap based (Markov-Chain Monte Carlo algorithms) or stub-matching based (the Configuration Model). Both types are ill-controlled, with typically unknown mixing times for link-swap methods and uncontrolled rejections for the Configuration Model. Here we propose an efficient, polynomial time algorithm that generates statistically independent graph samples with a given, arbitrary, degree sequence. The algorithm provides a weight associated with each sample, allowing the observable to be measured either uniformly over the graph ensemble, or, alternatively, with a desired distribution. Unlike other algorithms, this method always produces a sample, without back-tracking or rejections. Using a central limit theorem-based reasoning, we argue, that for large , and for degree sequences admitting many realizations, the sample weights are expected to have a lognormal distribution. As examples, we apply our algorithm to generate networks with degree sequences drawn from power-law distributions and from binomial distributions.
authors.affiliation: Department of Physics, University of Houston, Houston, Texas, United States of America.
authors.forename: Charo I
authors.initials: CI
authors.lastname: Del Genio
authors.forename: Hyunju
authors.initials: H
authors.lastname: Kim
authors.forename: Zoltán
authors.initials: Z
authors.lastname: Toroczkai
authors.forename: Kevin E
authors.initials: KE
authors.lastname: Bassler
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D003198:Computer Simulation; D015233:Models, Statistical; D008962:Models, Theoretical; D012494:Sampling Studies
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2005 Feb;71(2 Pt 2):027103
references.pmid: 15783457
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2003 Apr;67(4 Pt 2):046118
references.pmid: 12786447
references.citation: Nature. 2001 Jun 21;411(6840):907-8
references.pmid: 11418846
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2008 Jul;78(1 Pt 2):016114
references.pmid: 18764027
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2009 Mar;79(3 Pt 2):036114
references.pmid: 19392025
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2001 Aug;64(2 Pt 2):026118
references.pmid: 11497662