  Preferential attachment (PA) models of network structure are widely used due
to their explanatory power and conceptual simplicity. PA models are able to
account for the scale-free degree distributions observed in many real-world
large networks through the remarkably simple mechanism of sequentially
introducing nodes that attach preferentially to high-degree nodes. The ability
to efficiently generate instances from PA models is a key asset in
understanding both the models themselves and the real networks that they
represent. Surprisingly, little attention has been paid to the problem of
efficient instance generation. In this paper, we show that the complexity of
generating network instances from a PA model depends on the preference function
of the model, provide efficient data structures that work under any preference
function, and present empirical results from an implementation based on these
data structures. We demonstrate that, by indexing growing networks with a
simple augmented heap, we can implement a network generator which scales many
orders of magnitude beyond existing capabilities ($10^6$ -- $10^8$ nodes). We
show the utility of an efficient and general PA network generator by
investigating the consequences of varying the preference functions of an
existing model. We also provide "quicknet", a freely-available open-source
implementation of the methods described in this work.
