  We consider the problem of sampling from a distribution on graphs,
specifically when the distribution is defined by an evolving graph model, and
consider the time, space and randomness complexities of such samplers.
  In the standard approach, the whole graph is chosen randomly according to the
randomized evolving process, stored in full, and then queries on the sampled
graph are answered by simply accessing the stored graph. This may require
prohibitive amounts of time, space and random bits, especially when only a
small number of queries are actually issued. Instead, we propose to generate
the graph on-the-fly, in response to queries, and therefore to require amounts
of time, space, and random bits which are a function of the actual number of
queries.
  We focus on two random graph models: the Barab{\'{a}}si-Albert Preferential
Attachment model (BA-graphs) and the random recursive tree model. We give
on-the-fly generation algorithms for both models. With probability
$1-1/\mbox{poly}(n)$, each and every query is answered in $\mbox{polylog}(n)$
time, and the increase in space and the number of random bits consumed by any
single query are both $\mbox{polylog}(n)$, where $n$ denotes the number of
vertices in the graph.
  Our results show that, although the BA random graph model is defined by a
sequential process, efficient random access to the graph's nodes is possible.
In addition to the conceptual contribution, efficient on-the-fly generation of
random graphs can serve as a tool for the efficient simulation of sublinear
algorithms over large BA-graphs, and the efficient estimation of their
performance on such graphs.
