{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:34Z","timestamp":1781078254162,"version":"3.54.1"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,10,4]],"date-time":"2021-10-04T00:00:00Z","timestamp":1633305600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1867\/20 and 867\/19"],"award-info":[{"award-number":["1867\/20 and 867\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,10,31]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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 a setting where one generates parts of the sampled graph on-the-fly, in response to queries, and therefore requires amounts of time, space, and random bits that are a function of the actual number of queries. Yet, the responses to the queries correspond to a graph sampled from the distribution in question.<\/jats:p>\n          <jats:p>\n            Within this framework, we focus on two random graph models: the Barab\u00e1si-Albert Preferential Attachment model (BA-graphs) (\n            <jats:italic>Science<\/jats:italic>\n            , 286 (5439):509\u2013512) (for the special case of out-degree 1) and the random recursive tree model (\n            <jats:italic>Theory of Probability and Mathematical Statistics<\/jats:italic>\n            , (51):1\u201328). We give on-the-fly generation algorithms for both models. With probability 1-1\/poly(\n            <jats:italic>n<\/jats:italic>\n            ), each and every query is answered in polylog(\n            <jats:italic>n<\/jats:italic>\n            ) time, and the increase in space and the number of random bits consumed by any single query are both polylog(\n            <jats:italic>n<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            denotes the number of vertices in the graph.\n          <\/jats:p>\n          <jats:p>Our work thus proposes a new approach for the access to huge graphs sampled from a given distribution, and our results show that, although the BA random graph model is defined by a sequential process, efficient random access to the graph\u2019s 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 on such graphs.<\/jats:p>","DOI":"10.1145\/3464958","type":"journal-article","created":{"date-parts":[[2021,10,5]],"date-time":"2021-10-05T01:10:42Z","timestamp":1633396242000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Sublinear Random Access Generators for Preferential Attachment Graphs"],"prefix":"10.1145","volume":"17","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Reut","family":"Levi","sequence":"additional","affiliation":[{"name":"The Interdisciplinary Center Herzliya (IDC), Herzliya, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moti","family":"Medina","sequence":"additional","affiliation":[{"name":"Faculty of Engineering, Bar-Ilan University, Ramat Gan, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adi","family":"Ros\u00e9n","sequence":"additional","affiliation":[{"name":"CNRS and Universit\u00e9 de Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,4]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"1","article-title":"Distributed-memory parallel algorithms for generating massive scale-free networks using preferential attachment model. In Proceedings of the International Conference for High Performance Computing","volume":"91","author":"Maksudul Alam Md.","year":"2013","journal-title":"Networking, Storage and Analysis."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.89"},{"key":"e_1_2_1_3_1","volume-title":"Emergence of scaling in random networks. Science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.71.036113"},{"key":"e_1_2_1_5_1","volume-title":"Local-access generators for basic random graph models. CoRR abs\/1711.10692","author":"Biswas Amartya Shankha","year":"2017"},{"key":"e_1_2_1_6_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Bogdanov Andrej"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0002-2"},{"key":"e_1_2_1_8_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H."},{"key":"e_1_2_1_9_1","volume-title":"Large graph models: A review. CoRR abs\/1601.06444","author":"Drakopoulos Georgios","year":"2016"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-211-75357-6"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (LIPIcs), Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl (Eds.)","volume":"80","author":"Even Guy","year":"2017"},{"key":"e_1_2_1_12_1","volume-title":"Best of two local models: Local centralized and local distributed algorithms. CoRR abs\/1402.3796","author":"Even Guy","year":"2014"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_33"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(01)00460-5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/080722771"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90214-I"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/130914218"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 41st Symposium on Foundations of Computer Science. 57\u201365","author":"Kumar Ravi","year":"2000"},{"key":"e_1_2_1_19_1","volume-title":"Constructing near spanning trees with few local inspections. CoRR abs\/1502.00413","author":"Levi Reut","year":"2015"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Approximation, Randomization, and Combinatorial Optimization Conference: Algorithms and Techniques. 826\u2013842","author":"Levi Reut","year":"2014"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755615"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_55"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40328-6_19"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974317.4"},{"key":"e_1_2_1_25_1","volume-title":"Miller and Aric Hagberg","author":"Joel","year":"2011"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 49th IEEE Symposium on Foundations of Computer Science. IEEE, 327\u2013336","author":"Huy"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1951365.1951406"},{"key":"e_1_2_1_28_1","unstructured":"Krzysztof Onak. 2010. ******New Sublinear Methods in the Struggle against Classical Problems*****. Ph.D. Thesis. Massachusetts Institute of Technology.  Krzysztof Onak. 2010. ******New Sublinear Methods in the Struggle against Classical Problems*****. Ph.D. Thesis. Massachusetts Institute of Technology."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.88"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1127132"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.05.007"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the Conference on Innovations in Computer Science. 223\u2013238","author":"Rubinfeld Ronitt","year":"2011"},{"key":"e_1_2_1_33_1","unstructured":"Martin Sauerhoff. 2016. On the entropy of models for the web graph. Manuscript. Retrieved from http:\/\/ls2-www.cs.uni-dortmund.de\/ sauerhof\/papers\/ent.pdf.  Martin Sauerhoff. 2016. On the entropy of models for the web graph. Manuscript. Retrieved from http:\/\/ls2-www.cs.uni-dortmund.de\/ sauerhof\/papers\/ent.pdf."},{"key":"e_1_2_1_34_1","first-page":"1","article-title":"A survey of recursive trees","volume":"51","author":"Smythe Robert T.","year":"1995","journal-title":"Theor. Probab. Math. Statist."},{"key":"e_1_2_1_35_1","volume-title":"Henderson","author":"Yoo Andy","year":"2010"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/110828691"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3464958","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3464958","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:11Z","timestamp":1750191431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3464958"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,4]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,10,31]]}},"alternative-id":["10.1145\/3464958"],"URL":"https:\/\/doi.org\/10.1145\/3464958","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,4]]},"assertion":[{"value":"2019-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}