Title |
Efficient and Exact Sampling of Simple Graphs with Given Arbitrary Degree Sequence
|
---|---|
Published in |
PLOS ONE, April 2010
|
DOI | 10.1371/journal.pone.0010012 |
Pubmed ID | |
Authors |
Charo I. Del Genio, Hyunju Kim, Zoltán Toroczkai, Kevin E. Bassler |
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. |
Mendeley readers
Geographical breakdown
Country | Count | As % |
---|---|---|
United States | 6 | 5% |
Italy | 3 | 3% |
Germany | 3 | 3% |
China | 2 | 2% |
France | 1 | <1% |
United Kingdom | 1 | <1% |
Spain | 1 | <1% |
Russia | 1 | <1% |
Unknown | 102 | 85% |
Demographic breakdown
Readers by professional status | Count | As % |
---|---|---|
Student > Ph. D. Student | 43 | 36% |
Researcher | 30 | 25% |
Student > Master | 12 | 10% |
Student > Bachelor | 8 | 7% |
Professor | 7 | 6% |
Other | 17 | 14% |
Unknown | 3 | 3% |
Readers by discipline | Count | As % |
---|---|---|
Computer Science | 31 | 26% |
Physics and Astronomy | 25 | 21% |
Mathematics | 19 | 16% |
Agricultural and Biological Sciences | 11 | 9% |
Engineering | 8 | 7% |
Other | 14 | 12% |
Unknown | 12 | 10% |