{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:30:28Z","timestamp":1772119828514,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T00:00:00Z","timestamp":1521763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"<jats:p>\n            Much of the past work on mining and modeling networks has focused on understanding the observed properties of\n            <jats:italic>single<\/jats:italic>\n            example graphs. However, in many real-life applications it is important to characterize the structure of\n            <jats:italic>populations<\/jats:italic>\n            of graphs. In this work, we analyze the distributional properties of probabilistic generative graph models (PGGMs) for network populations. PGGMs are statistical methods that model the network distribution and match common characteristics of real-world networks. Specifically, we show that most PGGMs cannot reflect the natural variability in graph properties observed\n            <jats:italic>across<\/jats:italic>\n            multiple networks because their edge generation process assumes independence among edges. Then, we propose the\n            <jats:italic>mixed Kronecker Product Graph Model<\/jats:italic>\n            (mKPGM), a scalable generalization of KPGMs that uses tied parameters to increase the variability of the sampled networks, while preserving the edge probabilities in expectation. We compare mKPGM to several other graph models. The results show that learned mKPGMs accurately represent the characteristics of real-world networks, while also effectively capturing the natural variability in network structure.\n          <\/jats:p>","DOI":"10.1145\/3161885","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T12:29:49Z","timestamp":1521808189000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Tied Kronecker Product Graph Models to Capture Variance in Network Populations"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5422-0656","authenticated-orcid":false,"given":"Sebastian","family":"Moreno","sequence":"first","affiliation":[{"name":"Universidad Adolfo Iba\u00f1ez"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jennifer","family":"Neville","sequence":"additional","affiliation":[{"name":"Purdue University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Kirshner","sequence":"additional","affiliation":[{"name":"Facebook, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,3,23]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Emergence of scaling in random networks. Science 286, 5439","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert . 1999. Emergence of scaling in random networks. Science 286, 5439 ( 1999 ), 509--512. Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of scaling in random networks. Science 286, 5439 (1999), 509--512."},{"key":"e_1_2_1_2_1","volume-title":"Generating the maximum of independent identically distributed random variables. Computers 8 Mathematics with Applications 6, 3","author":"Devroye Luc","year":"1980","unstructured":"Luc Devroye . 1980. Generating the maximum of independent identically distributed random variables. Computers 8 Mathematics with Applications 6, 3 ( 1980 ), 305--315. Luc Devroye. 1980. Generating the maximum of independent identically distributed random variables. Computers 8 Mathematics with Applications 6, 3 (1980), 305--315."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"e_1_2_1_4_1","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u00f6s Paul","year":"1960","unstructured":"Paul Erd\u00f6s and Alfr\u00e9d R\u00e9nyi . 1960 . On the evolution of random graphs . Publication of the Mathematical Institute of the Hungary Academy of Sciences 5 , 1 (1960), 17 -- 60 . Paul Erd\u00f6s and Alfr\u00e9d R\u00e9nyi. 1960. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungary Academy of Sciences 5, 1 (1960), 17--60.","journal-title":"Publication of the Mathematical Institute of the Hungary Academy of Sciences"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1986.10478342"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.680824"},{"key":"e_1_2_1_8_1","volume-title":"Retrieved","author":"Harris Kathleen","year":"2009","unstructured":"Kathleen Harris . 2009 . The National Longitudinal Study of Adolescent Health (Add Health), Waves I 8 II, 1994--1996; Wave III, 2001-2002 {machine-readable data file and documentation}. (2009) . Retrieved November 15, 2017 from http:\/\/www.cpc.unc.edu\/projects\/addhealth\/. Kathleen Harris. 2009. The National Longitudinal Study of Adolescent Health (Add Health), Waves I 8 II, 1994--1996; Wave III, 2001-2002 {machine-readable data file and documentation}. (2009). Retrieved November 15, 2017 from http:\/\/www.cpc.unc.edu\/projects\/addhealth\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/130914218"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796570"},{"key":"e_1_2_1_12_1","article-title":"Kronecker graphs: An approach to modeling networks","author":"Leskovec Jure","year":"2010","unstructured":"Jure Leskovec , Deepayan Chakrabarti , Jon Kleinberg , Christos Faloutsos , and Zoubin Ghahramani . 2010 . Kronecker graphs: An approach to modeling networks . Journal of Machine Learning Research 11 ( February 2010), 985--1042. Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. 2010. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research 11 (February 2010), 985--1042.","journal-title":"Journal of Machine Learning Research 11"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273559"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20335"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2010.5707038"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 1st Workshop on Information in Networks.","author":"Moreno Sebastian","year":"2009","unstructured":"Sebastian Moreno and Jennifer Neville . 2009 . An investigation of the distributional characteristics of generative graph models . In Proceedings of the 1st Workshop on Information in Networks. Sebastian Moreno and Jennifer Neville. 2009. An investigation of the distributional characteristics of generative graph models. In Proceedings of the 1st Workshop on Information in Networks."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487675"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2014.148"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_2_1_20_1","volume-title":"International Journal of Computer Science","volume":"9","author":"Nizam Ahmed Mehedi","year":"2012","unstructured":"Ahmed Mehedi Nizam , Nasim Adnan , Rashedul Islam , and Mohammad Akbar Kabir . 2012 . Properties of stochastic Kronecker graph . International Journal of Computer Science , volume 9 (2012). Issue 4. Ahmed Mehedi Nizam, Nasim Adnan, Rashedul Islam, and Mohammad Akbar Kabir. 2012. Properties of stochastic Kronecker graph. International Journal of Computer Science, volume 9 (2012). Issue 4."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913622"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2006.08.003"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.056109"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.23"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450149"},{"key":"e_1_2_1_26_1","volume-title":"A First Course in Probability. Pearson Education","author":"Sheldon Ross","unstructured":"Ross Sheldon . 2002. A First Course in Probability. Pearson Education , London, United Kingdom . Ross Sheldon. 2002. A First Course in Probability. Pearson Education, London, United Kingdom."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9531.2006.00176.x"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_29_1","volume-title":"Statistical Computing: A Simulation-based Approach","author":"Voss Jochen","year":"2013","unstructured":"Jochen Voss (Ed.). 2013 . An Introduction to Statistical Computing: A Simulation-based Approach . John Wiley 8 Sons, Inc., New Jersey . Jochen Voss (Ed.). 2013. An Introduction to Statistical Computing: A Simulation-based Approach. John Wiley 8 Sons, Inc., New Jersey."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(87)90015-3"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02294547"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3161885","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3161885","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3161885","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:54Z","timestamp":1750213614000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3161885"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,23]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3161885"],"URL":"https:\/\/doi.org\/10.1145\/3161885","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,23]]},"assertion":[{"value":"2016-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}