Applied Mathematics and Plasma Physics

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

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$.

@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}

}