Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Sublinear Random Access Generators for Preferential Attachment Graphs

MPG-Autoren
/persons/resource/persons199710

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

/persons/resource/persons185330

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

Externe Ressourcen
Es sind keine externen Ressourcen hinterlegt
Volltexte (beschränkter Zugriff)
Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.
Volltexte (frei zugänglich)

arXiv:1602.06159.pdf
(Preprint), 688KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


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