T-5 HomeResearchPublications › miller-2011-efficient

Cite Details

Joel C. Miller and Aric Hagberg, "Efficient generation of networks with given expected degrees", in Algorithms and Models for the Web-Graph (WAW 2011), Alan Frieze, Paul Horn, and Pawel Pralat (Eds), pp. 115--126, 2011

Abstract

We present an efficient algorithm to generate random graphs with a given sequence of expected degrees. Existing algorithms run in $\order(N^2)$ time where $N$ is the number of nodes. We prove that our algorithm runs in $\order(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 $\order(N)$ as $N \to \infty$.

BibTeX Entry

@inproceedings{miller-2011-efficient,
author = {Joel C. Miller and Aric Hagberg},
title = {Efficient generation of networks with given expected degrees},
year = {2011},
urlpdf = {http://math.lanl.gov/~hagberg/Papers/miller-2011-efficient.pdf},
booktitle = {Algorithms and Models for the Web-Graph (WAW 2011)},
editors = {Alan Frieze, Paul Horn, and Pawel Pralat},
pages = {115--126}
}