de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Sublinear Random Access Generators for Preferential Attachment Graphs

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons199710

Levi,  Reut
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons185330

Medina,  Moti
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1602.06159.pdf
(Preprint), 688KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Even, G., Levi, R., Medina, M., & Rosen, A. (2016). Sublinear Random Access Generators for Preferential Attachment Graphs. Retrieved from http://arxiv.org/abs/1602.06159.


Cite as: http://hdl.handle.net/11858/00-001M-0000-002C-5EC7-6
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.