{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T17:30:15Z","timestamp":1792171815309,"version":"4.4.0"},"reference-count":50,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Network data is ubiquitous and growing, yet we lack realistic generative network models that can be calibrated to match real-world data. The recently proposed block two-level Erd\u00f6s--R\u00e9nyi (BTER) model can be tuned to capture two fundamental properties: degree distribution and clustering coefficients. The latter is particularly important for reproducing graphs with community structure, such as social networks. In this paper, we compare BTER to other scalable models and show that it gives a better fit to real data. We provide a scalable implementation that requires only $O(d_{\\rm max})$ storage, where $d_{\\rm max}$ is the maximum number of neighbors for a single node. The generator is trivially parallelizable, and we show results for a Hadoop MapReduce implementation for modeling a real-world Web graph with over 4.6 billion edges. We propose that the BTER model can be used as a graph generator for benchmarking purposes and provide idealized degree distributions and clustering coefficient profiles that can be tuned for user specifications.<\/jats:p>","DOI":"10.1137\/130914218","type":"journal-article","created":{"date-parts":[[2014,9,25]],"date-time":"2014-09-25T15:04:56Z","timestamp":1411657496000},"page":"C424-C452","source":"Crossref","is-referenced-by-count":111,"title":["A Scalable Generative Graph Model with Community Structure"],"prefix":"10.1137","volume":"36","author":[{"given":"Tamara G.","family":"Kolda","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ali","family":"Pinar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Todd","family":"Plantenga","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,9,25]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.2001.10504428"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"atypb3","first-page":"547","volume":"13","author":"Barrat A.","year":"2000","journal-title":"Eur. Phys. J. B Condens. Matter"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502521"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1145\/1480506.1480511"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.43"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557049"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.252631999"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/PL00012580"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1038\/nature06830"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16720-1_4"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/NSW.2013.6609190"},{"key":"atypb16","first-page":"17","volume":"5","author":"Erd\u00f6s P.","year":"1960","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl"},{"key":"atypb17","volume-title":"An Introduction to Probability Theory and Applications","author":"Feller W.","year":"1968","edition":"3"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.680824"},{"key":"atypb20","volume-title":"http:\/\/www.graph500.org\/specifications(accessed","author":"Benchmark 0","year":"2014"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1109\/CASoN.2009.13"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554840"},{"key":"atypb23","unstructured":"A. Gutfraind, L. A. Meyers, and I. Safro,\n                      Multiscale Network Generation\n                      , preprint, http:\/\/arxiv.org\/abs\/1207.4266, 2012."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719918.ch10"},{"key":"atypb25","series-title":"SIAM J. Sci. Comput., to appear.","volume-title":"Counting triangles in massive graphs with MapReduce","author":"Kolda T. G."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892065"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"atypb28","first-page":"985","volume":"11","author":"Leskovec J.","year":"2010","journal-title":"J. Mach. Learn. Res."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"atypb30","unstructured":"LWA: Laboratory for Web Algorithms\n                      , http:\/\/law.di.unimi.it\/datasets.php (accessed April 2, 2014)."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_20"},{"key":"atypb32","first-page":"1633","volume-title":"NIPS 2010: Advances in Neural Information Processing Systems, 2010","author":"Miller B.","year":"2010"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2012.6288612"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1145\/2320765.2320818"},{"key":"atypb35","first-page":"1137","volume-title":"Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing, 2010","author":"Moreno S.","year":"2010"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.045101"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.012582999"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.68.026121"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036104"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.92"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772778"},{"key":"atypb43","volume-title":"Revisiting Degree Distribution Models for Social Graph Analysis, preprint, arXiv:1108.0027","author":"Sala A.","year":"2011"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.056109"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.23"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450149"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.2"},{"key":"atypb48","unstructured":"SNAP: Stanford Network Analysis Project\n                      , http:\/\/snap.stanford.edu\/ (accessed April 2, 2014)."},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1002\/wics.184"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1038\/30918"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130914218","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:44:07Z","timestamp":1787327047000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130914218"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":50,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/130914218"],"URL":"https:\/\/doi.org\/10.1137\/130914218","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}