Name
Abstract | ||
|---|---|---|
We present an efficient algorithm to generate random graphs with a given sequence of expected degrees. Existing algorithms run in O(N2) time where N is the number of nodes. We prove that our algorithm runs in O(N +M) expected time where M is the expected number of edges. If the expected degrees are chosen from a distribution with finite mean, this is O(N) as N → ∞. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-21286-4_10 | WAW |
Keywords | Field | DocType |
random graph,expected number,efficient generation,expected time,expected degree,efficient algorithm,finite mean | Discrete mathematics,Combinatorics,Random graph,Expected value,Mathematics | Conference |
Volume | ISSN | Citations |
6732 | 0302-9743 | 19 |
PageRank | References | Authors |
0.95 | 9 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joel C. Miller | 1 | 75 | 6.24 |
| Hagberg Aric | 2 | 152 | 9.03 |