hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
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 Barab{\'{a}}si-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, on-the-fly generation of random graphs
can serve as a tool for simulating sublinear algorithms over large BA-graphs.
