License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.6
URN: urn:nbn:de:0030-drops-74242
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7424/
Even, Guy ;
Levi, Reut ;
Medina, Moti ;
Rosén, Adi
Sublinear Random Access Generators for Preferential Attachment Graphs
Abstract
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á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/poly(n), each and every query is answered in polylog(n) time, and the increase in space and the number of random bits consumed by any single query are both 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.
BibTeX - Entry
@InProceedings{even_et_al:LIPIcs:2017:7424,
author = {Guy Even and Reut Levi and Moti Medina and Adi Ros{\'e}n},
title = {{Sublinear Random Access Generators for Preferential Attachment Graphs}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {6:1--6:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-041-5},
ISSN = {1868-8969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7424},
URN = {urn:nbn:de:0030-drops-74242},
doi = {10.4230/LIPIcs.ICALP.2017.6},
annote = {Keywords: local computation algorithms, preferential attachment graphs, random recursive trees, sublinear algorithms}
}
|
Keywords: |
|
local computation algorithms, preferential attachment graphs, random recursive trees, sublinear algorithms |
|
Collection: |
|
44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
07.07.2017 |
