The last decade and a half has seen the introduction of a wide variety of random graph models. Random graph models allow for theoretical analysis of network properties as well as simulation on random instances of the model. Thus the most useful random graph models (a) capture the percieved important characteristics of real networks, (b) are mathematically tractible, and (c) allow for quick generation of random instances. We concentrate on this third point: fast generation. As real world networks are usually sparse and large, it is important for the running time of generation algorithms to scale linearly in the number of edges of the generated graph as opposed to quadratically in the number of vertices. Recently, Bollobas, Janson and Riordan introduced an extremely general random graph model, the random kernel graph. This model generalizes several well known models while remaining mathematically tractable. We describe an algorithm to randomly generate instances of this model which runs in time O(m+n) for many kernels of interest. (Here n is the number of vertices and m the expected number of edges in the graph.)

Nathan Lemons is currently a postdoctoral researcher at the Center for Nonlinear Studies (CNLS) at Los Alamos National Laboratory and was previously at the Central European University, where he completed his Ph.D. in 2008. His research interests include graph algorithms, combinatorics of networks, extremal combinatorics, and all things finite.