Name
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 backtracking or rejections. Using a central limit theorem-based reasoning, we argue, that for large N, 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1371/journal.pone.0010012 | PLOS ONE |
Keywords | Field | DocType |
algorithms,statistical independence,biology,markov chain monte carlo,social network,lognormal distribution,computer simulation,sampling methods,central limit theorem,engineering,degree sequence,mixing time,computer graphics,chemistry,medicine,binomial distribution,physics,power law distribution | Monte Carlo method,Central limit theorem,Algorithm,Probability distribution,Sampling (statistics),Degree distribution,Degree (graph theory),Time complexity,Independence (probability theory),Physics | Journal |
Volume | Issue | ISSN |
5 | 4 | 1932-6203 |
Citations | PageRank | References |
24 | 1.93 | 10 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Charo I. Del Genio | 1 | 391 | 18.07 |
| Hyunju Kim | 2 | 80 | 14.37 |
| Zoltán Toroczkai | 3 | 122 | 15.89 |
| Kevin E. Bassler | 4 | 110 | 13.26 |