Document Open Access Logo

Sublinear Random Access Generators for Preferential Attachment Graphs

Authors Guy Even, Reut Levi, Moti Medina, Adi Rosén

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.6.pdf
  • Filesize: 0.61 MB
  • 15 pages

Document Identifiers

Author Details

Guy Even
Reut Levi
Moti Medina
Adi Rosén

Cite As Get BibTex

Guy Even, Reut Levi, Moti Medina, and Adi Rosén. Sublinear Random Access Generators for Preferential Attachment Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 6:1-6:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.6

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.

Subject Classification

Keywords
  • local computation algorithms
  • preferential attachment graphs
  • random recursive trees
  • sublinear algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Md. Maksudul Alam, Maleq Khan, and Madhav V. Marathe. Distributed-memory parallel algorithms for generating massive scale-free networks using preferential attachment model. In International Conference for High Performance Computing, Networking, Storage and Analysis, SC'13, Denver, CO, USA - November 17-21, 2013, pages 91:1-91:12, 2013. URL: http://dx.doi.org/10.1145/2503210.2503291.
  2. Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1132-1139, 2012. URL: http://dl.acm.org/citation.cfm?id=2095205.
  3. Albert-László Barabási and Reka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999. URL: http://dx.doi.org/10.1126/science.286.5439.509.
  4. Vladimir Batagelj and Ulrik Brandes. Efficient generation of large random networks. Physical Review E, 71(3):036113, 2005. Google Scholar
  5. Michael Drmota. Random Trees: An Interplay Between Combinatorics and Probability. Springer Publishing Company, Incorporated, 1st edition, 2009. Google Scholar
  6. Guy Even, Moti Medina, and Dana Ron. Best of two local models: Local centralized and local distributed algorithms. CoRR, abs/1402.3796, 2014. URL: http://arxiv.org/abs/1402.3796.
  7. Guy Even, Moti Medina, and Dana Ron. Deterministic stateless centralized local algorithms for bounded degree graphs. In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, pages 394-405, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44777-2_33.
  8. Oded Goldreich, Shafi Goldwasser, and Asaf Nussboim. On the implementation of huge random objects. SIAM J. Comput., 39(7):2761-2822, 2010. URL: http://dx.doi.org/10.1137/080722771.
  9. Tamara G. Kolda, Ali Pinar, Todd Plantenga, and C. Seshadhri. A scalable generative graph model with community structure. SIAM J. Scientific Computing, 36(5), 2014. URL: http://dx.doi.org/10.1137/130914218.
  10. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, and Eli Upfal. Random graph models for the web graph. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, pages 57-65, 2000. URL: http://dx.doi.org/10.1109/SFCS.2000.892065.
  11. Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, and Asaf Shapira. Constructing near spanning trees with few local inspections. CoRR, abs/1502.00413, 2015. URL: http://arxiv.org/abs/1502.00413.
  12. Reut Levi, Dana Ron, and Ronitt Rubinfeld. Local algorithms for sparse spanning graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain, pages 826-842, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.826.
  13. Reut Levi, Ronitt Rubinfeld, and Anak Yodpinyanee. Brief announcement: Local computation algorithms for graphs of non-constant degrees. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, pages 59-61, 2015. URL: http://dx.doi.org/10.1145/2755573.2755615.
  14. Yishay Mansour, Aviad Rubinstein, Shai Vardi, and Ning Xie. Converting online algorithms to local computation algorithms. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, pages 653-664, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_55.
  15. Yishay Mansour and Shai Vardi. A local computation approximation scheme to maximum matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, pages 260-273, 2013. URL: http://dx.doi.org/10.1007/978-3-642-40328-6_19.
  16. Ulrich Meyer and Manuel Penschuck. Generating massive scale-free networks under resource constraints. In Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments, ALENEX 2016, Arlington, Virginia, USA, January 10, 2016, pages 39-52, 2016. URL: http://dx.doi.org/10.1137/1.9781611974317.4.
  17. Huy N Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 327-336. IEEE, 2008. Google Scholar
  18. Sadegh Nobari, Xuesong Lu, Panagiotis Karras, and Stéphane Bressan. Fast random graph generation. In Proceedings of the 14th international conference on extending database technology, pages 331-342. ACM, 2011. Google Scholar
  19. Krzysztof Onak. New sublinear methods in the struggle against classical problems. Massachusetts Institute of Technology, PhD Thesis, September 2010. Google Scholar
  20. Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1123-1131, 2012. URL: http://dl.acm.org/citation.cfm?id=2095204.
  21. Omer Reingold and Shai Vardi. New techniques and tighter bounds for local computation algorithms. J. Comput. Syst. Sci., 82(7):1180-1200, 2016. URL: http://dx.doi.org/10.1016/j.jcss.2016.05.007.
  22. Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 7-9, 2011. Proceedings, pages 223-238, 2011. URL: http://conference.itcs.tsinghua.edu.cn/ICS2011/content/papers/36.html.
  23. Martin Sauerhoff. On the entropy of models for the web graph. Manuscript. URL: http://ls2-www.cs.uni-dortmund.de/~sauerhof/papers/ent.pdf.
  24. Robert T. Smythe and Hosam M. Mahmoud. A survey of recursive trees. Theory of Probability and Mathematical Statistics, (51):1-28, 1995. Google Scholar
  25. Andy Yoo and Keith W. Henderson. Parallel generation of massive scale-free graphs. CoRR, abs/1003.3684, 2010. URL: http://arxiv.org/abs/1003.3684.
  26. Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. Improved constant-time approximation algorithms for maximum matchings and other optimization problems. SIAM J. Comput., 41(4):1074-1093, 2012. URL: http://dx.doi.org/10.1137/110828691.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact