{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T10:25:04Z","timestamp":1775039104947,"version":"3.50.1"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T00:00:00Z","timestamp":1533772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG","award":["ME 2088\/3-2 and WA 654\/22-2"],"award-info":[{"award-number":["ME 2088\/3-2 and WA 654\/22-2"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2018,11,15]]},"abstract":"<jats:p>\n            <jats:italic>LFR<\/jats:italic>\n            is a popular benchmark graph generator used to evaluate community detection algorithms. We present\n            <jats:italic>EM-LFR<\/jats:italic>\n            , the first external memory algorithm able to generate massive complex networks following the\n            <jats:italic>LFR<\/jats:italic>\n            benchmark. Its most expensive component is the generation of random graphs with prescribed degree sequences which can be divided into two steps: the graphs are first materialized deterministically using the Havel-Hakimi algorithm, and then randomized. Our main contributions are\n            <jats:italic>EM-HH<\/jats:italic>\n            and\n            <jats:italic>EM-ES<\/jats:italic>\n            , two I\/O-efficient external memory algorithms for these two steps. We also propose\n            <jats:italic>EM-CM\/ES<\/jats:italic>\n            , an alternative sampling scheme using the Configuration Model and rewiring steps to obtain a random simple graph. In an experimental evaluation, we demonstrate their performance; our implementation is able to handle graphs with more than 37 billion edges on a single machine, is competitive with a massively parallel distributed algorithm, and is faster than a state-of-the-art internal memory implementation even on instances fitting in main memory.\n            <jats:italic>EM-LFR<\/jats:italic>\n            \u2019s implementation is capable of generating large graph instances orders of magnitude faster than the original implementation. We give evidence that both implementations yield graphs with matching properties by applying clustering algorithms to generated instances. Similarly, we analyze the evolution of graph properties as\n            <jats:italic>EM-ES<\/jats:italic>\n            is executed on networks obtained with\n            <jats:italic>EM-CM\/ES<\/jats:italic>\n            and find that the alternative approach can accelerate the sampling process.\n          <\/jats:p>","DOI":"10.1145\/3230743","type":"journal-article","created":{"date-parts":[[2018,8,9]],"date-time":"2018-08-09T15:25:51Z","timestamp":1533828351000},"page":"1-33","source":"Crossref","is-referenced-by-count":8,"title":["I\/O-Efficient Generation of Massive Graphs Following the\n            <i>LFR<\/i>\n            Benchmark"],"prefix":"10.1145","volume":"23","author":[{"given":"Michael","family":"Hamann","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}]},{"given":"Ulrich","family":"Meyer","sequence":"additional","affiliation":[{"name":"Goethe University Frankfurt, Frankfurt, Germany"}]},{"given":"Manuel","family":"Penschuck","sequence":"additional","affiliation":[{"name":"Goethe University Frankfurt, Frankfurt, Germany"}]},{"given":"Hung","family":"Tran","sequence":"additional","affiliation":[{"name":"Goethe University Frankfurt, Frankfurt, Germany"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}]}],"member":"320","published-online":{"date-parts":[[2018,8,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_1_2_1","unstructured":"Omer Angel Remco van der Hofstad and Cecilia Holmgren. 2016. Limit laws for self-loops and multiple edges in the configuration model. arxiv:1603.07172.  Omer Angel Remco van der Hofstad and Cecilia Holmgren. 2016. Limit laws for self-loops and multiple edges in the configuration model. arxiv:1603.07172."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Lars Arge. 1995. The buffer tree: A new technique for optimal I\/O-algorithms. In WADS\u201995.  Lars Arge. 1995. The buffer tree: A new technique for optimal I\/O-algorithms. In WADS\u201995.","DOI":"10.1007\/3-540-60220-8_74"},{"key":"e_1_2_1_4_1","volume-title":"Encyclopedia of Social Network Analysis and Mining","author":"Bader David A.","unstructured":"David A. Bader , Henning Meyerhenke , Peter Sanders , Christian Schulz , Andrea Kappes , and Dorothea Wagner . 2014. Encyclopedia of Social Network Analysis and Mining . Springer , Chapter Benchmarking for Graph Clustering and Partitioning, 73--82. David A. Bader, Henning Meyerhenke, Peter Sanders, Christian Schulz, Andrea Kappes, and Dorothea Wagner. 2014. Encyclopedia of Social Network Analysis and Mining. Springer, Chapter Benchmarking for Graph Clustering and Partitioning, 73--82."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2807591.2807668"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/355900.355907"},{"key":"e_1_2_1_8_1","volume-title":"Marathe","author":"Bhuiyan Hasanuzzaman","year":"2014","unstructured":"Hasanuzzaman Bhuiyan , Jiangzhuo Chen , Maleq Khan , and Madhav V . Marathe . 2014 . Fast parallel algorithms for edge-switching to achieve a target visit rate in heterogeneous graphs. In ICPP\u2019 14. Hasanuzzaman Bhuiyan, Jiangzhuo Chen, Maleq Khan, and Madhav V. Marathe. 2014. Fast parallel algorithms for edge-switching to achieve a target visit rate in heterogeneous graphs. In ICPP\u201914."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2014.158"},{"key":"e_1_2_1_11_1","volume-title":"Complex Networks","author":"Chykhradze Kyrylo","unstructured":"Kyrylo Chykhradze , Anton Korshunov , Nazar Buzun , Roman Pastukhov , Nikolay Kuzyurin , Denis Turdakov , and Hangkyu Kim . 2014. Distributed generation of billion-node social graphs with overlapping community struscture . In Complex Networks . Springer International , 199--208. Kyrylo Chykhradze, Anton Korshunov, Nazar Buzun, Roman Pastukhov, Nikolay Kuzyurin, Denis Turdakov, and Hangkyu Kim. 2014. Distributed generation of billion-node social graphs with overlapping community struscture. In Complex Networks. Springer International, 199--208."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1361730.1361733"},{"key":"e_1_2_1_13_1","series-title":"Lecture Notes in Mathematics","volume-title":"Eggleton and Derek Allan Holton","author":"Roger","year":"1980","unstructured":"Roger B. Eggleton and Derek Allan Holton . 1980 . Simple and multigraphic realizations of degree sequences. In ACCM\u201980, Lecture Notes in Mathematics . Springer , 155--172. Roger B. Eggleton and Derek Allan Holton. 1980. Simple and multigraphic realizations of degree sequences. In ACCM\u201980, Lecture Notes in Mathematics. Springer, 155--172."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0159161"},{"key":"e_1_2_1_15_1","unstructured":"Alcides Viamontes Esquivel and Martin Rosvall. 2012. Comparing network covers using mutual information. arxiv:1202.0425  Alcides Viamontes Esquivel and Martin Rosvall. 2012. Comparing network covers using mutual information. arxiv:1202.0425"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0605965104"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2016.09.002"},{"key":"e_1_2_1_19_1","volume-title":"Zegura","author":"Gkantsidis Christos","year":"2003","unstructured":"Christos Gkantsidis , Milena Mihail , and Ellen W . Zegura . 2003 . The Markov chain simulation method for generating connected power law random graphs. In ALENEX\u201903. SIAM , 16--25. Christos Gkantsidis, Milena Mihail, and Ellen W. Zegura. 2003. The Markov chain simulation method for generating connected power law random graphs. In ALENEX\u201903. SIAM, 16--25."},{"key":"e_1_2_1_20_1","volume-title":"Greenhill and Matteo Sfragara","author":"Catherine","year":"2017","unstructured":"Catherine S. Greenhill and Matteo Sfragara . 2017 . The switch Markov chain for sampling irregular graphs and digraphs. arxiv:1701.07101 Catherine S. Greenhill and Matteo Sfragara. 2017. The switch Markov chain for sampling irregular graphs and digraphs. arxiv:1701.07101"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0110037"},{"key":"e_1_2_1_22_1","volume-title":"ALENEX\u201917","author":"Hamann Michael","unstructured":"Michael Hamann , Ulrich Meyer , Manuel Penschuck , and Dorothea Wagner . 2017. I\/O-efficient generation of massive graphs following the LFR benchmark. In ALENEX\u201917 . SIAM , 58--72. Michael Hamann, Ulrich Meyer, Manuel Penschuck, and Dorothea Wagner. 2017. I\/O-efficient generation of massive graphs following the LFR benchmark. In ALENEX\u201917. SIAM, 58--72."},{"key":"e_1_2_1_23_1","unstructured":"Michael Hamann Ben Strasser Dorothea Wagner and Tim Zeitz. 2017. Simple distributed graph clustering using modularity and map equation. arxiv:1710.09605  Michael Hamann Ben Strasser Dorothea Wagner and Tim Zeitz. 2017. Simple distributed graph clustering using modularity and map equation. arxiv:1710.09605"},{"key":"e_1_2_1_24_1","volume-title":"Community detection in large-scale networks: A survey and empirical evaluation. WIREs Computational Statistics 6","author":"Harenberg Steve","year":"2014","unstructured":"Steve Harenberg , Gonzalo Bello , L. Gjeltema , Stephen Ranshous , Jitendra Harlalka , Ramona Seay , Kanchana Padmanabhan , and Nagiza Samatova . 2014. Community detection in large-scale networks: A survey and empirical evaluation. WIREs Computational Statistics 6 ( 2014 ). Steve Harenberg, Gonzalo Bello, L. Gjeltema, Stephen Ranshous, Jitendra Harlalka, Ramona Seay, Kanchana Padmanabhan, and Nagiza Samatova. 2014. Community detection in large-scale networks: A survey and empirical evaluation. WIREs Computational Statistics 6 (2014)."},{"key":"e_1_2_1_25_1","volume-title":"Pozn\u00e1mka o existenci kone\u010dn\u00fdch graf\u016f. \u010casopis pro p\u011bstov\u00e1n\u00ed Matematiky 080, 4","author":"Havel V\u00e1clav","year":"1955","unstructured":"V\u00e1clav Havel . 1955. Pozn\u00e1mka o existenci kone\u010dn\u00fdch graf\u016f. \u010casopis pro p\u011bstov\u00e1n\u00ed Matematiky 080, 4 ( 1955 ), 477--480. http:\/\/eudml.org\/doc\/19050 V\u00e1clav Havel. 1955. Pozn\u00e1mka o existenci kone\u010dn\u00fdch graf\u016f. \u010casopis pro p\u011bstov\u00e1n\u00ed Matematiky 080, 4 (1955), 477--480. http:\/\/eudml.org\/doc\/19050"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01908075"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/10\/8\/083042"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.91.012809"},{"key":"e_1_2_1_29_1","volume-title":"Verr\u00e8s, Italy","author":"Kumar Panqanamala Ramana","year":"2009","unstructured":"Panqanamala Ramana Kumar , Martin J. Wainwright , and Riccardo Zecchina . 2015. Mathematical Foundations of Complex Networked Information Systems: Politecnico Di Torino , Verr\u00e8s, Italy 2009 . Vol. 2141 . Springer . Panqanamala Ramana Kumar, Martin J. Wainwright, and Riccardo Zecchina. 2015. Mathematical Foundations of Complex Networked Information Systems: Politecnico Di Torino, Verr\u00e8s, Italy 2009. Vol. 2141. Springer."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.016118"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.056117"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.046110"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0018961"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Anil Maheshwari and Norbert Zeh. 2003. A survey of techniques for designing I\/O-Efficient algorithms. In Algorithms for Memory Hierarchies. 36--61.  Anil Maheshwari and Norbert Zeh. 2003. A survey of techniques for designing I\/O-Efficient algorithms. In Algorithms for Memory Hierarchies. 36--61.","DOI":"10.1007\/3-540-36574-5_3"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Ulrich Meyer and Manuel Penschuck. 2016. Generating massive scale-free networks under resource constraints. In ALENEX\u201916. 39--52.  Ulrich Meyer and Manuel Penschuck. 2016. Generating massive scale-free networks under resource constraints. In ALENEX\u201916. 39--52.","DOI":"10.1137\/1.9781611974317.4"},{"key":"e_1_2_1_37_1","volume-title":"Advanced Lectures. Lecture Notes in Computer Science","volume":"2625","author":"Meyer Ulrich","unstructured":"Ulrich Meyer , Peter Sanders , and Jop F . Sibeyn (Eds.). 2003. Algorithms for Memory Hierarchies , Advanced Lectures. Lecture Notes in Computer Science , Vol. 2625 . Springer. Ulrich Meyer, Peter Sanders, and Jop F. Sibeyn (Eds.). 2003. Algorithms for Memory Hierarchies, Advanced Lectures. Lecture Notes in Computer Science, Vol. 2625. Springer."},{"key":"e_1_2_1_38_1","unstructured":"Ron Milo Nadav Kashtan Shalev Itzkovitz Mark E. J. Newman and Uri. Alon. 2003. On the uniform generation of random graphs with prescribed degree sequences. arxiv:cond-mat\/0312028  Ron Milo Nadav Kashtan Shalev Itzkovitz Mark E. J. Newman and Uri. Alon. 2003. On the uniform generation of random graphs with prescribed degree sequences. arxiv:cond-mat\/0312028"},{"key":"e_1_2_1_39_1","volume-title":"Randomized Algorithms","author":"Motwani Rajeev","unstructured":"Rajeev Motwani and Prabhakar Raghavan . 2010. Randomized Algorithms . Chapman 8 Hall\/CRC. Rajeev Motwani and Prabhakar Raghavan. 2010. Randomized Algorithms. Chapman 8 Hall\/CRC."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199206650.001.0001"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_2_1_42_1","volume-title":"Algorithms for Memory Hierarchies","author":"Pagh Rasmus","unstructured":"Rasmus Pagh . 2003. Basic external memory data structures . In Algorithms for Memory Hierarchies . Springer , 14--35. Rasmus Pagh. 2003. Basic external memory data structures. In Algorithms for Memory Hierarchies. Springer, 14--35."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30541-2_12"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjst\/e2010-01179-1"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00127-6"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384249"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-015-0267-z"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2016.20"},{"key":"e_1_2_1_50_1","volume-title":"ClueWeb12 Web Graph. Retrieved","author":"Project The Lemur","year":"2013","unstructured":"The Lemur Project . 2013. ClueWeb12 Web Graph. Retrieved Nov. 2013 from http:\/\/www.lemurproject.org\/clueweb12\/webgraph.php. The Lemur Project. 2013. ClueWeb12 Web Graph. Retrieved Nov. 2013 from http:\/\/www.lemurproject.org\/clueweb12\/webgraph.php."},{"key":"e_1_2_1_51_1","unstructured":"Johan Ugander Brian Karrer Lars Backstrom and Cameron Marlow. 2011. The anatomy of the facebook social graph. arxiv:1111.4503  Johan Ugander Brian Karrer Lars Backstrom and Cameron Marlow. 2011. The anatomy of the facebook social graph. arxiv:1111.4503"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Fabien Viger and Matthieu Latapy. 2005. Fast generation of random connected graphs with prescribed degrees. arXiv:cs\/0502085. Source code available at https:\/\/www-complexnetworks.lip6.fr\/ latapy\/FV\/generation.html.  Fabien Viger and Matthieu Latapy. 2005. Fast generation of random connected graphs with prescribed degrees. arXiv:cs\/0502085. Source code available at https:\/\/www-complexnetworks.lip6.fr\/ latapy\/FV\/generation.html.","DOI":"10.1007\/11533719_45"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/23002.23003"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2016.05.008"},{"key":"e_1_2_1_55_1","unstructured":"James Y. Zhao. 2013. Expand and contract: Sampling graphs with given degrees and other combinatorial families. arxiv:1308.6627  James Y. Zhao. 2013. Expand and contract: Sampling graphs with given degrees and other combinatorial families. arxiv:1308.6627"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3230743","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3230743","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:30Z","timestamp":1750208250000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3230743"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,9]]},"references-count":54,"alternative-id":["10.1145\/3230743"],"URL":"https:\/\/doi.org\/10.1145\/3230743","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,9]]}}}