{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,1]],"date-time":"2023-04-01T09:41:46Z","timestamp":1680342106981},"reference-count":47,"publisher":"Walter de Gruyter GmbH","issue":"3-4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,5,27]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The selection of input data is a crucial step in virtually every empirical study. Experimental campaigns in algorithm engineering, experimental algorithmics, network analysis, and many other fields often require suited network data. In this context, synthetic graphs play an important role, as data sets of observed networks are typically scarce, biased, not sufficiently understood, and may pose logistic and legal challenges. Just like processing huge graphs becomes challenging in the big data setting, new algorithmic approaches are necessary to generate such massive instances efficiently. Here, we update our previous survey [35] on results for large-scale graph generation obtained within the DFG priority programme SPP 1736 (Algorithms for Big Data); to this end, we broaden the scope and include recently published results.<\/jats:p>","DOI":"10.1515\/itit-2019-0041","type":"journal-article","created":{"date-parts":[[2020,3,7]],"date-time":"2020-03-07T09:00:55Z","timestamp":1583571655000},"page":"135-144","source":"Crossref","is-referenced-by-count":0,"title":["Large-scale graph generation: Recent results of the SPP 1736 \u2013 Part II"],"prefix":"10.1515","volume":"62","author":[{"given":"Ulrich","family":"Meyer","sequence":"first","affiliation":[{"name":"Goethe University , Institute for Computer Science , Frankfurt am Main , Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manuel","family":"Penschuck","sequence":"additional","affiliation":[{"name":"Goethe University , Institute for Computer Science , Frankfurt am Main , Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2020,3,7]]},"reference":[{"key":"2023033120254874739_j_itit-2019-0041_ref_001_w2aab3b7d668b1b6b1ab2ab1Aa","doi-asserted-by":"crossref","unstructured":"Alok Aggarwal and Jeffrey Scott Vitter. The input\/output complexity of sorting and related problems. Communications of the ACM, 31(9), 1988.","DOI":"10.1145\/48529.48535"},{"key":"2023033120254874739_j_itit-2019-0041_ref_002_w2aab3b7d668b1b6b1ab2ab2Aa","doi-asserted-by":"crossref","unstructured":"M. Alam, M. Khan, and M. Marathe. Distributed-memory parallel algorithms for generating massive scale-free networks using preferential attachment model. In P. of the Int. Conf. on High Performance Computing, Networking, Storage and Analysis, page 91. ACM, 2013.","DOI":"10.1145\/2503210.2503291"},{"key":"2023033120254874739_j_itit-2019-0041_ref_003_w2aab3b7d668b1b6b1ab2ab3Aa","doi-asserted-by":"crossref","unstructured":"R\u00e9ka Albert and Albert-L\u00e1szl\u00f3 Barab\u00e1si. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.","DOI":"10.1103\/RevModPhys.74.47"},{"key":"2023033120254874739_j_itit-2019-0041_ref_004_w2aab3b7d668b1b6b1ab2ab4Aa","doi-asserted-by":"crossref","unstructured":"Eugenio Angriman, Alexander van der Grinten, Moritz von Looz, Henning Meyerhenke, Martin N\u00f6llenburg, Maria Predari, and Charilaos Tzovas. Guidelines for experimental algorithmics: A case study in network analysis. Algorithms, 12(7):127, 2019. doi:10.3390\/a12070127.","DOI":"10.3390\/a12070127"},{"key":"2023033120254874739_j_itit-2019-0041_ref_005_w2aab3b7d668b1b6b1ab2ab5Aa","doi-asserted-by":"crossref","unstructured":"Lars Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1\u201324, 2003. doi:10.1007\/s00453-003-1021-x.","DOI":"10.1007\/s00453-003-1021-x"},{"key":"2023033120254874739_j_itit-2019-0041_ref_006_w2aab3b7d668b1b6b1ab2ab6Aa","doi-asserted-by":"crossref","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. Emergence of scaling in random networks. Science, 286(5439):509\u2013512, Oct. 1999. doi:10.1126\/science.286.5439.509.","DOI":"10.1126\/science.286.5439.509"},{"key":"2023033120254874739_j_itit-2019-0041_ref_007_w2aab3b7d668b1b6b1ab2ab7Aa","doi-asserted-by":"crossref","unstructured":"Vladimir Batagelj and Ulrik Brandes. Efficient generation of large random networks. Phys. Rev. E, 71:036113, Mar. 2005. doi:10.1103\/PhysRevE.71.036113.","DOI":"10.1103\/PhysRevE.71.036113"},{"key":"2023033120254874739_j_itit-2019-0041_ref_008_w2aab3b7d668b1b6b1ab2ab8Aa","doi-asserted-by":"crossref","unstructured":"Edward Bender and Rodney Canfield. The asymptotic number of labeled graphs with given degree sequences. J. Comb. Theory, Ser. A, 24(3):296\u2013307, 1978.","DOI":"10.1016\/0097-3165(78)90059-6"},{"key":"2023033120254874739_j_itit-2019-0041_ref_009_w2aab3b7d668b1b6b1ab2ab9Aa","unstructured":"Thomas Bl\u00e4sius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently generating geometric inhomogeneous and hyperbolic random graphs. In ESA 2019, pages 21:1\u201321:14, 2019. doi:10.4230\/LIPIcs.ESA.2019.21."},{"key":"2023033120254874739_j_itit-2019-0041_ref_010_w2aab3b7d668b1b6b1ab2ac10Aa","unstructured":"Bela Bollob\u00e1s. Random graphs. Academic Press, 1985."},{"key":"2023033120254874739_j_itit-2019-0041_ref_011_w2aab3b7d668b1b6b1ab2ac11Aa","unstructured":"B\u00e9la Bollob\u00e1s, Christian Borgs, Jennifer Chayes, and Oliver Riordan. Directed scale-free graphs. In ACM-SIAM symposium on Discrete algorithms, pages 132\u2013139, 2003."},{"key":"2023033120254874739_j_itit-2019-0041_ref_012_w2aab3b7d668b1b6b1ab2ac12Aa","doi-asserted-by":"crossref","unstructured":"Karl Bringmann, Ralph Keusch, and Johannes Lengler. Geometric inhomogeneous random graphs. Theor. Comput. Sci., 760:35\u201354, 2019. doi:10.1016\/j.tcs.2018.08.014.","DOI":"10.1016\/j.tcs.2018.08.014"},{"key":"2023033120254874739_j_itit-2019-0041_ref_013_w2aab3b7d668b1b6b1ab2ac13Aa","unstructured":"Corrie J. Carstens. Topology of Complex Networks: Models and Analysis. PhD thesis, RMIT University, 2016."},{"key":"2023033120254874739_j_itit-2019-0041_ref_014_w2aab3b7d668b1b6b1ab2ac14Aa","unstructured":"Corrie J. Carstens, Annabell Berger, and Giovanni Strona. Curveball: a new generation of sampling algorithms for graphs with fixed degree sequence. CoRR, 2016. arXiv:1609.05137."},{"key":"2023033120254874739_j_itit-2019-0041_ref_015_w2aab3b7d668b1b6b1ab2ac15Aa","unstructured":"Corrie J. Carstens, Michael Hamann, Ulrich Meyer, Manuel Penschuck, Hung Tran, and Dorothea Wagner. Parallel and I\/O-efficient randomisation of massive networks using global curveball trades. In ESA 2018, 2018. doi:10.4230\/LIPIcs.ESA.2018.11."},{"key":"2023033120254874739_j_itit-2019-0041_ref_016_w2aab3b7d668b1b6b1ab2ac16Aa","doi-asserted-by":"crossref","unstructured":"Kyrylo Chykhradze, Anton Korshunov, Nazar Buzun, Roman Pastukhov, Nikolay Kuzyurin, Denis Turdakov, and Hangkyu Kim. Distributed Generation of Billion-node Social Graphs with Overlapping Community Structure. In CompleNet 2014, 2014. doi:10.1007\/978-3-319-05401-8_19.","DOI":"10.1007\/978-3-319-05401-8_19"},{"key":"2023033120254874739_j_itit-2019-0041_ref_017_w2aab3b7d668b1b6b1ab2ac17Aa","unstructured":"DFG, German Research Foundation. Priority Programmes. URL: http:\/\/www.dfg.de\/en\/research_funding\/programmes\/coordinated_programmes\/priority_programmes\/index.html."},{"key":"2023033120254874739_j_itit-2019-0041_ref_018_w2aab3b7d668b1b6b1ab2ac18Aa","doi-asserted-by":"crossref","unstructured":"Sergey Dorogovtsev, Jos\u2019e F.\u2009F. Mendes, and A.\u2009N. Samukhin. Anomalous percolation properties of growing networks. Phys. Rev. E, 64:066110, Nov. 2001.","DOI":"10.1103\/PhysRevE.64.066110"},{"key":"2023033120254874739_j_itit-2019-0041_ref_019_w2aab3b7d668b1b6b1ab2ac19Aa","doi-asserted-by":"crossref","unstructured":"Daniel Funke, Sebastian Lamm, Ulrich Meyer, Manuel Penschuck, Peter Sanders, Christian Schulz, Darren Strash, and Moritz von Looz. Communication-free massively distributed graph generation. J. Parallel Distrib. Comput., 131:200\u2013217, 2019. doi:10.1016\/j.jpdc.2019.03.011.","DOI":"10.1016\/j.jpdc.2019.03.011"},{"key":"2023033120254874739_j_itit-2019-0041_ref_020_w2aab3b7d668b1b6b1ab2ac20Aa","doi-asserted-by":"crossref","unstructured":"Daniel Funke, Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Moritz von Looz. Communication-free massively distributed graph generation. In IPDPS 2018, 2018.","DOI":"10.1109\/IPDPS.2018.00043"},{"key":"2023033120254874739_j_itit-2019-0041_ref_021_w2aab3b7d668b1b6b1ab2ac21Aa","doi-asserted-by":"crossref","unstructured":"Minos N. Garofalakis, Johannes Gehrke, and Rajeev Rastogi, editors. Data Stream Management \u2013 Processing High-Speed Data Streams. Data-Centric Systems and Applications. Springer, 2016. doi:10.1007\/978-3-540-28608-0.","DOI":"10.1007\/978-3-540-28608-0"},{"key":"2023033120254874739_j_itit-2019-0041_ref_022_w2aab3b7d668b1b6b1ab2ac22Aa","unstructured":"Nicholas J. Gotelli and Gary R. Graves. Null models in ecology. Smithsonian Institution, 1996."},{"key":"2023033120254874739_j_itit-2019-0041_ref_023_w2aab3b7d668b1b6b1ab2ac23Aa","doi-asserted-by":"crossref","unstructured":"Luca Gugelmann, Konstantinos Panagiotou, and Ueli Peter. Random hyperbolic graphs: Degree sequence and clustering \u2013 (extended abstract). In ICALP 2012, pages 573\u2013585, 2012. doi:10.1007\/978-3-642-31585-5_51.","DOI":"10.1007\/978-3-642-31585-5_51"},{"key":"2023033120254874739_j_itit-2019-0041_ref_024_w2aab3b7d668b1b6b1ab2ac24Aa","doi-asserted-by":"crossref","unstructured":"Seifollah L. Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph. I. Journal of the Society for Industrial and Applied Mathematics, 10(3):496\u2013506, 1962. doi:10.1137\/0110037.","DOI":"10.1137\/0110037"},{"key":"2023033120254874739_j_itit-2019-0041_ref_025_w2aab3b7d668b1b6b1ab2ac25Aa","doi-asserted-by":"crossref","unstructured":"Michael Hamann, Ulrich Meyer, Manuel Penschuck, Hung Tran, and Dorothea Wagner. I\/O-efficient generation of massive graphs following the LFR benchmark. ACM Journal of Experimental Algorithmics, 23, 2018. doi:10.1145\/3230743.","DOI":"10.1145\/3230743"},{"key":"2023033120254874739_j_itit-2019-0041_ref_026_w2aab3b7d668b1b6b1ab2ac26Aa","doi-asserted-by":"crossref","unstructured":"Michael Hamann, Ulrich Meyer, Manuel Penschuck, and Dorothea Wagner. I\/O-efficient generation of massive graphs following the LFR benchmark. In ALENEX 2017, pages 58\u201372, 2017. doi:10.1137\/1.9781611974768.5.","DOI":"10.1137\/1.9781611974768.5"},{"key":"2023033120254874739_j_itit-2019-0041_ref_027_w2aab3b7d668b1b6b1ab2ac27Aa","doi-asserted-by":"crossref","unstructured":"V\u00e1clav Havel. Pozn\u00e1mka o existenci kone\u010dn\u00fdch graf\u016f. \u010casopis pro p\u011bstov\u00e1n\u00ed matematiky, 080(4):477\u2013480, 1955. URL: http:\/\/eudml.org\/doc\/19050.","DOI":"10.21136\/CPM.1955.108220"},{"key":"2023033120254874739_j_itit-2019-0041_ref_028_w2aab3b7d668b1b6b1ab2ac28Aa","doi-asserted-by":"crossref","unstructured":"Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. The web as a graph: Measurements, models, and methods. In COCOON \u201999, pages 1\u201317, 1999. doi:10.1007\/3-540-48686-0_1.","DOI":"10.1007\/3-540-48686-0_1"},{"key":"2023033120254874739_j_itit-2019-0041_ref_029_w2aab3b7d668b1b6b1ab2ac29Aa","doi-asserted-by":"crossref","unstructured":"Pavel Krapivsky, Geoff Rodgers, and Sidney Redner. Degree distributions of growing networks. Physical Review Letters, 86(23):5401, 2001.","DOI":"10.1103\/PhysRevLett.86.5401"},{"key":"2023033120254874739_j_itit-2019-0041_ref_030_w2aab3b7d668b1b6b1ab2ac30Aa","doi-asserted-by":"crossref","unstructured":"Dmitri V. Krioukov, Fragkiskos Papadopoulos, Maksim Kitsak, Amin Vahdat, and Mari\u00e1n Bogu\u00f1\u00e1. Hyperbolic geometry of complex networks. Phys. Rev. E, 82:036106, Sep. 2010. doi:10.1103\/PhysRevE.82.036106.","DOI":"10.1103\/PhysRevE.82.036106"},{"key":"2023033120254874739_j_itit-2019-0041_ref_031_w2aab3b7d668b1b6b1ab2ac31Aa","doi-asserted-by":"crossref","unstructured":"Andrea Lancichinetti and Santo Fortunato. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities. Phys. Rev. E, 80:016118, Jul. 2009. doi:10.1103\/PhysRevE.80.016118.","DOI":"10.1103\/PhysRevE.80.016118"},{"key":"2023033120254874739_j_itit-2019-0041_ref_032_w2aab3b7d668b1b6b1ab2ac32Aa","doi-asserted-by":"crossref","unstructured":"Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi. Benchmark graphs for testing community detection algorithms. Phys. Rev. E, 78:046110, Oct. 2008. doi:10.1103\/PhysRevE.78.046110.","DOI":"10.1103\/PhysRevE.78.046110"},{"key":"2023033120254874739_j_itit-2019-0041_ref_033_w2aab3b7d668b1b6b1ab2ac33Aa","doi-asserted-by":"crossref","unstructured":"Anil Maheshwari and Norbert Zeh. A survey of techniques for designing I\/O-efficient algorithms. In Algorithms for Memory Hierarchies, pages 36\u201361, 2003. doi:10.1007\/3-540-36574-5_3.","DOI":"10.1007\/3-540-36574-5_3"},{"key":"2023033120254874739_j_itit-2019-0041_ref_034_w2aab3b7d668b1b6b1ab2ac34Aa","doi-asserted-by":"crossref","unstructured":"Ulrich Meyer and Manuel Penschuck. Generating massive scale-free networks under resource constraints. In ALENEX 2016, pages 39\u201352, 2016. doi:10.1137\/1.9781611974317.4.","DOI":"10.1137\/1.9781611974317.4"},{"key":"2023033120254874739_j_itit-2019-0041_ref_035_w2aab3b7d668b1b6b1ab2ac35Aa","unstructured":"Ulrich Meyer and Manuel Penschuck. Large-scale graph generation and big data: An overview on recent results. Bulletin of the EATCS, 122, 2017. URL: http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/494."},{"key":"2023033120254874739_j_itit-2019-0041_ref_036_w2aab3b7d668b1b6b1ab2ac36Aa","doi-asserted-by":"crossref","unstructured":"Ulrich Meyer, Peter Sanders, and Jop F. Sibeyn, editors. Algorithms for Memory Hierarchies, Advanced Lectures, volume 2625 of LNCS. Springer, 2003.","DOI":"10.1007\/3-540-36574-5"},{"key":"2023033120254874739_j_itit-2019-0041_ref_037_w2aab3b7d668b1b6b1ab2ac37Aa","doi-asserted-by":"crossref","unstructured":"Ron Milo, Shai S. Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: Simple building blocks of complex networks. Science, 298(5594):824\u2013827, 2002. doi:10.1126\/science.298.5594.824.","DOI":"10.1126\/science.298.5594.824"},{"key":"2023033120254874739_j_itit-2019-0041_ref_038_w2aab3b7d668b1b6b1ab2ac38Aa","unstructured":"Manuel Penschuck. Generating practical random hyperbolic graphs in near-linear time and with sub-linear memory. In 16th Int. Symposium on Experimental Algorithms, SEA 2017, 2017."},{"key":"2023033120254874739_j_itit-2019-0041_ref_039_w2aab3b7d668b1b6b1ab2ac39Aa","doi-asserted-by":"crossref","unstructured":"Derek De Solla Price. A general theory of bibliometric and other cumulative advantage processes. JASIS, 27(5):292\u2013306, 1976. doi:10.1002\/asi.4630270505.","DOI":"10.1002\/asi.4630270505"},{"key":"2023033120254874739_j_itit-2019-0041_ref_040_w2aab3b7d668b1b6b1ab2ac40Aa","doi-asserted-by":"crossref","unstructured":"Peter Sanders and Christian Schulz. Scalable generation of scale-free graphs. Inf. Process. Lett., 116(7):489\u2013491, 2016. doi:10.1016\/j.ipl.2016.02.004.","DOI":"10.1016\/j.ipl.2016.02.004"},{"key":"2023033120254874739_j_itit-2019-0041_ref_041_w2aab3b7d668b1b6b1ab2ac41Aa","doi-asserted-by":"crossref","unstructured":"Wolfgang E. Schlauch, Em\u0151ke \u00c1gnes Horv\u00e1t, and Katharina A. Zweig. Different flavors of randomness: comparing random graph models with fixed degree sequences. Social Network Analysis and Mining, 5(1):1\u201314, 2015. doi:10.1007\/s13278-015-0267-z.","DOI":"10.1007\/s13278-015-0267-z"},{"key":"2023033120254874739_j_itit-2019-0041_ref_042_w2aab3b7d668b1b6b1ab2ac42Aa","doi-asserted-by":"crossref","unstructured":"Christian Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. Networkit: A tool suite for large-scale complex network analysis. Network Science, 4(4):508\u2013530, 2016. doi:10.1017\/nws.2016.20.","DOI":"10.1017\/nws.2016.20"},{"key":"2023033120254874739_j_itit-2019-0041_ref_043_w2aab3b7d668b1b6b1ab2ac43Aa","doi-asserted-by":"crossref","unstructured":"Christian L. Staudt, Michael Hamann, Ilya Safro, Alexander Gutfraind, and Henning Meyerhenke. Generating Scaled Replicas of Real-World Complex Networks, pages 17\u201328. Springer International Publishing, Cham, 2017. doi:10.1007\/978-3-319-50901-3_2.","DOI":"10.1007\/978-3-319-50901-3_2"},{"key":"2023033120254874739_j_itit-2019-0041_ref_044_w2aab3b7d668b1b6b1ab2ac44Aa","unstructured":"Remco Van Der Hofstad. Random graphs and complex networks. Available on http:\/\/www.win.tue.nl\/rhofstad\/NotesRGCN.pdf, page 11, 2009."},{"key":"2023033120254874739_j_itit-2019-0041_ref_045_w2aab3b7d668b1b6b1ab2ac45Aa","doi-asserted-by":"crossref","unstructured":"Moritz von Looz and Henning Meyerhenke. Querying probabilistic neighborhoods in spatial data sets efficiently. In IWOCA 2016, pages 449\u2013460, 2016. doi:10.1007\/978-3-319-44543-4_35.","DOI":"10.1007\/978-3-319-44543-4_35"},{"key":"2023033120254874739_j_itit-2019-0041_ref_046_w2aab3b7d668b1b6b1ab2ac46Aa","doi-asserted-by":"crossref","unstructured":"Moritz von Looz, Henning Meyerhenke, and Roman Prutkin. Generating random hyperbolic graphs in subquadratic time. In ISAAC 2015, pages 467\u2013478, 2015. doi:10.1007\/978-3-662-48971-0_40.","DOI":"10.1007\/978-3-662-48971-0_40"},{"key":"2023033120254874739_j_itit-2019-0041_ref_047_w2aab3b7d668b1b6b1ab2ac47Aa","doi-asserted-by":"crossref","unstructured":"Moritz von Looz, Mustafa Safa \u00d6zdayi, S\u00f6ren Laue, and Henning Meyerhenke. Generating massive complex networks with hyperbolic geometry faster in practice. In HPEC 2016, pages 1\u20136, 2016. doi:10.1109\/HPEC.2016.7761644.","DOI":"10.1109\/HPEC.2016.7761644"}],"container-title":["it - Information Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/itit\/62\/3-4\/article-p135.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2019-0041\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2019-0041\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,1]],"date-time":"2023-04-01T09:27:51Z","timestamp":1680341271000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2019-0041\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,7]]},"references-count":47,"journal-issue":{"issue":"3-4","published-online":{"date-parts":[[2020,4,1]]},"published-print":{"date-parts":[[2020,5,27]]}},"alternative-id":["10.1515\/itit-2019-0041"],"URL":"https:\/\/doi.org\/10.1515\/itit-2019-0041","relation":{},"ISSN":["2196-7032","1611-2776"],"issn-type":[{"value":"2196-7032","type":"electronic"},{"value":"1611-2776","type":"print"}],"subject":[],"published":{"date-parts":[[2020,3,7]]}}}