We consider the problem of generating random graphs in evolving random graph models. In the standard approach, the whole graph is chosen randomly according to the distribution of the model before answering queries to the adjacency lists of the graph. Instead, we propose to answer queries by generating the graphs on-the-fly while respecting the probability space of the random graph model. We focus on two random graph models: the Barabasi-Albert Preferential Attachment model (BA-graphs) and the random recursive tree model. We present sublinear randomized generating algorithms for both models. Per query, the running time, the increase in space, and the number of random bits consumed are Poly log(n) with probability 1 1/Poly(n), where n denotes the number of vertices. This result shows that, although the BA random graph model is defined sequentially, random access is possible without chronological evolution. In addition to a conceptual contribution, onthe-fly generation of random graphs can serve as a tool for simulating sublinear algorithms over large BA-graphs.
['Guy Even', 'Reut Levi', 'Moti Medina', 'Adi Rosén']
Sublinear Random Access Generators for Preferential Attachment Graphs