{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:30:37Z","timestamp":1772119837818,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,4,1]],"date-time":"2013-04-01T00:00:00Z","timestamp":1364774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004317","name":"Lockheed Martin Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100004317","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,4]]},"abstract":"<jats:p>Graph analysis is playing an increasingly important role in science and industry. Due to numerous limitations in sharing real-world graphs, models for generating massive graphs are critical for developing better algorithms. In this article, we analyze the stochastic Kronecker graph model (SKG), which is the foundation of the Graph500 supercomputer benchmark due to its favorable properties and easy parallelization. Our goal is to provide a deeper understanding of the parameters and properties of this model so that its functionality as a benchmark is increased. We develop a rigorous mathematical analysis that shows this model cannot generate a power-law distribution or even a lognormal distribution. However, we formalize an enhanced version of the SKG model that uses random noise for smoothing. We prove both in theory and in practice that this enhancement leads to a lognormal distribution. Additionally, we provide a precise analysis of isolated vertices, showing that the graphs that are produced by SKG might be quite different than intended. For example, between 50% and 75% of the vertices in the Graph500 benchmarks will be isolated. Finally, we show that this model tends to produce extremely small core numbers (compared to most social networks and other real graphs) for common parameter choices.<\/jats:p>","DOI":"10.1145\/2450142.2450149","type":"journal-article","created":{"date-parts":[[2013,5,1]],"date-time":"2013-05-01T19:47:09Z","timestamp":1367437629000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["An in-depth analysis of stochastic Kronecker graphs"],"prefix":"10.1145","volume":"60","author":[{"given":"C.","family":"Seshadhri","sequence":"first","affiliation":[{"name":"Sandia National Laboratories, Livermore, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ali","family":"Pinar","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Livermore, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tamara G.","family":"Kolda","sequence":"additional","affiliation":[{"name":"Sandia National Laboratories, Livermore, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,5,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.3934\/nhm.2008.3.371"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1941-0003498-3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502521"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0701175104"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132952.1132954"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of SDM'04","author":"Chakrabarti D.","unstructured":"Chakrabarti , D. , Zhan , Y. , and Faloutsos , C . 2004. R-MAT: A recursive model for graph mining . In Proceedings of SDM'04 . 442--446. Chakrabarti, D., Zhan, Y., and Faloutsos, C. 2004. R-MAT: A recursive model for graph mining. In Proceedings of SDM'04. 442--446."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"key":"e_1_2_1_9_1","first-page":"160","article-title":"A moment inequality with an application to the central limit theorem","volume":"39","author":"Esseen C.-G.","year":"1942","unstructured":"Esseen , C.-G. 1942 . A moment inequality with an application to the central limit theorem . Skand. Aktuarietidskr 39 , 160 -- 170 . Esseen, C.-G. 1942. A moment inequality with an application to the central limit theorem. Skand. Aktuarietidskr 39, 160--170.","journal-title":"Skand. Aktuarietidskr"},{"key":"e_1_2_1_10_1","volume-title":"An Introduction to Probability Theory and Applications: Vol I","author":"Feller W.","unstructured":"Feller , W. 1968. An Introduction to Probability Theory and Applications: Vol I . 3 rd Ed. Wiley . Feller, W. 1968. An Introduction to Probability Theory and Applications: Vol I. 3rd Ed. Wiley.","edition":"3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/276627.276652"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of INFOCOM","author":"Gkantsidis C.","year":"2003","unstructured":"Gkantsidis , C. , Mihail , M. , and Zegura , E. W . 2003. Spectral analysis of internet topologies . In Proceedings of INFOCOM 2003 . IEEE, 364--374. Gkantsidis, C., Mihail, M., and Zegura, E. W. 2003. Spectral analysis of internet topologies. In Proceedings of INFOCOM 2003. IEEE, 364--374."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.73.056101"},{"key":"e_1_2_1_14_1","unstructured":"Graph500 Steering Committee. 2010. Graph 500 benchmark. http:\/\/www.graph500.org\/specifications.  Graph500 Steering Committee. 2010. Graph 500 benchmark. http:\/\/www.graph500.org\/specifications."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.20417"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Ibragimov I. A. 1956. On the composition of unimodal distributions. Theory Probability its App. 1 2 255--260.  Ibragimov I. A. 1956. On the composition of unimodal distributions. Theory Probability its App. 1 2 255--260.","DOI":"10.1137\/1101021"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Kim M. and Leskovec J. 2010. Multiplicative attribute graph model of real-world networks. arXiv:1009.3499v2.  Kim M. and Leskovec J. 2010. Multiplicative attribute graph model of real-world networks. arXiv:1009.3499v2.","DOI":"10.2172\/1124904"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Kumar R. Novak J. and Tomkins A. 2010. Structure and evolution of online social networks. In Link Mining: Models Algorithms and Applications Springer 337--357.  Kumar R. Novak J. and Tomkins A. 2010. Structure and evolution of online social networks. In Link Mining: Models Algorithms and Applications Springer 337--357.","DOI":"10.1007\/978-1-4419-6515-8_13"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3121445.3121464"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1756039"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273559"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Mahdian M. and Xu Y. 2007. Stochastic kronecker graphs. In Algorithms and Models for the Web-Graph Springer 179--186.   Mahdian M. and Xu Y. 2007. Stochastic kronecker graphs. In Algorithms and Models for the Web-Graph Springer 179--186.","DOI":"10.1007\/978-3-540-77004-6_14"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20335"},{"key":"e_1_2_1_25_1","first-page":"148","article-title":"On the method of bounded differences","volume":"141","author":"McDiarmid C.","year":"1989","unstructured":"McDiarmid , C. 1989 . On the method of bounded differences . Surv. Combinat. 141 , 148 -- 188 . McDiarmid, C. 1989. On the method of bounded differences. Surv. Combinat. 141, 148--188.","journal-title":"Surv. Combinat."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of NIPS","author":"Miller B.","year":"2010","unstructured":"Miller , B. , Bliss , N. , and Wolfe , P . 2010. Subgraph detection using eigenvector L1 norms . In Proceedings of NIPS 2010 . 1633--1641. Miller, B., Bliss, N., and Wolfe, P. 2010. Subgraph detection using eigenvector L1 norms. In Proceedings of NIPS 2010. 1633--1641."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129088"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129112"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing. 1137--1144","author":"Moreno S.","unstructured":"Moreno , S. , Kirshner , S. , Neville , J. , and Vishwanathan , S. V. N. 2010. Tied Kronecker product graph models to capture variance in network populations . In Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing. 1137--1144 . Moreno, S., Kirshner, S., Neville, J., and Vishwanathan, S. V. N. 2010. Tied Kronecker product graph models to capture variance in network populations. In Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing. 1137--1144."},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.032085699"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772778"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2450142.2450149","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2450142.2450149","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:49Z","timestamp":1750234729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2450142.2450149"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.1145\/2450142.2450149"],"URL":"https:\/\/doi.org\/10.1145\/2450142.2450149","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4]]},"assertion":[{"value":"2011-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}