{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T00:46:31Z","timestamp":1776386791773,"version":"3.51.2"},"reference-count":61,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T00:00:00Z","timestamp":1695686400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"funder":[{"name":"U.S. National Science Foundation DMS","award":["#2113671"],"award-info":[{"award-number":["#2113671"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,9,13]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Many statistical models for networks overlook the fact that most real-world networks are formed through a growth process. To address this, we introduce the Preferential Attachment Plus Erd\u0151s\u2013R\u00e9nyi model, where we let a random network G be the union of a preferential attachment (PA) tree T and additional Erd\u0151s\u2013R\u00e9nyi (ER) random edges. The PA tree captures the underlying growth process of a network where vertices\/edges are added sequentially, while the ER component can be regarded as noise. Given only one snapshot of the final network G, we study the problem of constructing confidence sets for the root node of the unobserved growth process; the root node can be patient zero in an infection network or the source of fake news in a social network. We propose inference algorithms based on Gibbs sampling that scales to networks with millions of nodes and provide theoretical analysis showing that the size of the confidence set is small if the noise level of the ER edges is not too large. We also propose variations of the model in which multiple growth processes occur simultaneously, reflecting the growth of multiple communities; we use these models to provide a new approach to community detection.<\/jats:p>","DOI":"10.1093\/jrsssb\/qkad102","type":"journal-article","created":{"date-parts":[[2023,9,27]],"date-time":"2023-09-27T21:36:30Z","timestamp":1695850590000},"page":"825-865","source":"Crossref","is-referenced-by-count":5,"title":["Root and community inference on the latent growth process of a network"],"prefix":"10.1093","volume":"86","author":[{"given":"Harry","family":"Crane","sequence":"first","affiliation":[{"name":"Department of Statistics, Rutgers University , New Brunswick, NJ , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Min","family":"Xu","sequence":"additional","affiliation":[{"name":"Department of Statistics, Rutgers University , New Brunswick, NJ , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2023,9,26]]},"reference":[{"issue":"1","key":"2024091323314056900_qkad102-B1","doi-asserted-by":"publisher","first-page":"6446","DOI":"10.1561\/9781680834772","article-title":"Community detection and stochastic block models: Recent developments","volume":"18","author":"Abbe","year":"2017","journal-title":"The Journal of Machine Learning Research"},{"key":"2024091323314056900_qkad102-B2","doi-asserted-by":"publisher","author":"Adamic","year":"2005","DOI":"10.1145\/1134271.1134277"},{"issue":"4","key":"2024091323314056900_qkad102-B3","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1002\/rsa.v52.4","article-title":"High degrees in random recursive trees","volume":"52","author":"Addario-Berry","year":"2018","journal-title":"Random Structures & Algorithms"},{"key":"2024091323314056900_qkad102-B4","doi-asserted-by":"publisher","author":"Aiello","year":"2000","DOI":"10.1515\/9781400841356.259"},{"issue":"6749","key":"2024091323314056900_qkad102-B5","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1038\/43601","article-title":"Diameter of the world-wide web","volume":"401","author":"Albert","year":"1999","journal-title":"Nature"},{"issue":"4","key":"2024091323314056900_qkad102-B6","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/0403039","article-title":"The random walk construction of uniform spanning trees and uniform labelled trees","volume":"3","author":"Aldous","year":"1990","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"4","key":"2024091323314056900_qkad102-B7","doi-asserted-by":"publisher","first-page":"2097","DOI":"10.1214\/13-AOS1138","article-title":"Pseudo-likelihood methods for community detection in large sparse networks","volume":"41","author":"Amini","year":"2013","journal-title":"Annals of Statistics"},{"issue":"1","key":"2024091323314056900_qkad102-B8","first-page":"8393","article-title":"Statistical inference on random dot product graphs: A survey","volume":"18","author":"Athreya","year":"2017","journal-title":"The Journal of Machine Learning Research"},{"key":"2024091323314056900_qkad102-B9","author":"Banerjee","year":"2020"},{"key":"2024091323314056900_qkad102-B10","author":"Banerjee","year":"2021"},{"key":"2024091323314056900_qkad102-B11","volume-title":"Network science","author":"Barab\u00e1si","year":"2016"},{"issue":"5439","key":"2024091323314056900_qkad102-B12","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Barab\u00e1si","year":"1999","journal-title":"Science"},{"key":"2024091323314056900_qkad102-B13","author":"Bhamidi","year":"2007"},{"key":"2024091323314056900_qkad102-B14","author":"Bloem-Reddy","year":"2018"},{"issue":"5","key":"2024091323314056900_qkad102-B15","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1111\/rssb.12289","article-title":"Random-walk models of network formation and sequential monte carlo methods for graphs","volume":"80","author":"Bloem-Reddy","year":"2018","journal-title":"Journal of the Royal Statistical Society: Series B (Statistical Methodology)"},{"issue":"3","key":"2024091323314056900_qkad102-B16","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1002\/rsa.1009","article-title":"The degree sequence of a scale-free random graph process","volume":"18","author":"Bollob\u00e1s","year":"2001","journal-title":"Random Structures & Algorithms"},{"key":"2024091323314056900_qkad102-B17","author":"Briend","year":"2022"},{"key":"2024091323314056900_qkad102-B18","doi-asserted-by":"publisher","author":"Broder","year":"1989","DOI":"10.1109\/SFCS.1989.63516"},{"issue":"2","key":"2024091323314056900_qkad102-B19","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1002\/rsa.v50.2","article-title":"Finding Adam in random growing trees","volume":"50","author":"Bubeck","year":"2017","journal-title":"Random Structures & Algorithms"},{"issue":"4A","key":"2024091323314056900_qkad102-B20","doi-asserted-by":"publisher","first-page":"2887","DOI":"10.3150\/16-BEJ831","article-title":"From trees to seeds: On the inference of the seed from large tree in the uniform attachment model","volume":"23","author":"Bubeck","year":"2017","journal-title":"Bernoulli"},{"issue":"1","key":"2024091323314056900_qkad102-B21","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1109\/TNSE.2015.2397592","article-title":"On the influence of the seed graph in the preferential attachment model","volume":"2","author":"Bubeck","year":"2015","journal-title":"IEEE Transactions on Network Science and Engineering"},{"issue":"25","key":"2024091323314056900_qkad102-B22","doi-asserted-by":"publisher","first-page":"5468","DOI":"10.1103\/PhysRevLett.85.5468","article-title":"Network robustness and fragility: Percolation on random graphs","volume":"85","author":"Callaway","year":"2000","journal-title":"Physical Review Letters"},{"key":"2024091323314056900_qkad102-B23","author":"Cantwell","year":"2019"},{"issue":"3","key":"2024091323314056900_qkad102-B24","doi-asserted-by":"publisher","first-page":"038301","DOI":"10.1103\/PhysRevLett.126.038301","article-title":"Inference, model selection, and the combinatorics of growing trees","volume":"126","author":"Cantwell","year":"2021","journal-title":"Physical Review Letters"},{"issue":"1","key":"2024091323314056900_qkad102-B25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/15-STS529","article-title":"The ubiquitous Ewens sampling formula","volume":"31","author":"Crane","year":"2016","journal-title":"Statistical Science"},{"issue":"4","key":"2024091323314056900_qkad102-B26","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1111\/rssb.12428","article-title":"Inference on the history of a randomly growing tree","volume":"83","author":"Crane","year":"2021","journal-title":"Journal of Royal Statistical Society, Series B"},{"key":"2024091323314056900_qkad102-B27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.5802\/jep.15","article-title":"Scaling limits and influence of the seed graph in preferential attachment trees","volume":"2","author":"Curien","year":"2015","journal-title":"Journal de l\u2019\u00c9cole polytechnique\u2014Math\u00e9matiques"},{"key":"2024091323314056900_qkad102-B28","doi-asserted-by":"publisher","first-page":"1222","DOI":"10.1214\/EJP.v14-647","article-title":"Random networks with sublinear preferential attachment: Degree evolutions","volume":"14","author":"Dereich","year":"2009","journal-title":"Electronic Journal of Probability"},{"key":"2024091323314056900_qkad102-B29","author":"Devroye","year":"2018"},{"key":"2024091323314056900_qkad102-B30","author":"Diaconis","year":"2007"},{"key":"2024091323314056900_qkad102-B31","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-211-75357-6","volume-title":"Random trees: An interplay between combinatorics and probability","author":"Drmota","year":"2009"},{"key":"2024091323314056900_qkad102-B32","doi-asserted-by":"publisher","first-page":"6775","DOI":"10.12988\/ams.2014.49693","article-title":"Predicting the sources of an outbreak with a spectral technique","volume":"8","author":"Fioriti","year":"2014","journal-title":"Applied Mathematical Sciences"},{"key":"2024091323314056900_qkad102-B33","author":"Galashin","year":"2013"},{"issue":"6","key":"2024091323314056900_qkad102-B34","doi-asserted-by":"publisher","first-page":"2624","DOI":"10.1214\/15-AOS1354","article-title":"Rate-optimal graphon estimation","volume":"43","author":"Gao","year":"2015","journal-title":"Annals of Statistics"},{"issue":"22","key":"2024091323314056900_qkad102-B35","doi-asserted-by":"publisher","first-page":"7794","DOI":"10.1073\/pnas.0407994102","article-title":"The worldwide air transportation network: Anomalous centrality, community structure, and cities\u2019 global roles","volume":"102","author":"Guimera","year":"2005","journal-title":"Proceedings of the National Academy of Sciences"},{"issue":"3","key":"2024091323314056900_qkad102-B36","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1093\/aje\/kws006","article-title":"Robust reconstruction and analysis of outbreak data: influenza A(H1N1)v transmission in a school-based population","volume":"176","author":"Hens","year":"2012","journal-title":"American Journal of Epidemiology"},{"issue":"460","key":"2024091323314056900_qkad102-B37","doi-asserted-by":"publisher","first-page":"1090","DOI":"10.1198\/016214502388618906","article-title":"Latent space approaches to social network analysis","volume":"97","author":"Hoff","year":"2002","journal-title":"Journal of the American Statistical Association"},{"issue":"4","key":"2024091323314056900_qkad102-B39","doi-asserted-by":"publisher","first-page":"1779","DOI":"10.1214\/15-AOAS896","article-title":"Coauthorship and citation networks for statisticians","volume":"10","author":"Ji","year":"2016","journal-title":"The Annals of Applied Statistics"},{"issue":"1","key":"2024091323314056900_qkad102-B40","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1109\/COMST.2016.2615098","article-title":"Identifying propagation sources in networks: State-of-the-art and comparative studies","volume":"19","author":"Jiang","year":"2016","journal-title":"IEEE Communications Surveys & Tutorials"},{"issue":"1","key":"2024091323314056900_qkad102-B41","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1214\/14-AOS1265","article-title":"Fast community detection by SCORE","volume":"43","author":"Jin","year":"2015","journal-title":"Annals of Statistics"},{"issue":"1","key":"2024091323314056900_qkad102-B42","doi-asserted-by":"publisher","first-page":"016107","DOI":"10.1103\/PhysRevE.83.016107","article-title":"Stochastic blockmodels and community structure in networks","volume":"83","author":"Karrer","year":"2011","journal-title":"Physical Review E"},{"issue":"1","key":"2024091323314056900_qkad102-B43","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1109\/TNSE.6488902","article-title":"Confidence sets for the source of a diffusion in regular trees","volume":"4","author":"Khim","year":"2017","journal-title":"IEEE Transactions on Network Science and Engineering"},{"key":"2024091323314056900_qkad102-B44","volume-title":"The art of computer programming: Volume 1: Fundamental algorithms","author":"Knuth","year":"1997"},{"key":"2024091323314056900_qkad102-B45","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-88146-1","volume-title":"Statistical analysis of network data: Methods and models","author":"Kolaczyk","year":"2009"},{"key":"2024091323314056900_qkad102-B47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/19-EJP268","article-title":"Finding the seed of uniform attachment trees","volume":"24","author":"Lugosi","year":"2019","journal-title":"Electronic Journal of Probability"},{"key":"2024091323314056900_qkad102-B49","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/0025-5564(70)90071-4","article-title":"Distribution of nodes of a tree by degree","volume":"6","author":"Na","year":"1970","journal-title":"Mathematical Biosciences"},{"key":"2024091323314056900_qkad102-B50","author":"Pek\u00f6z","year":"2014"},{"key":"2024091323314056900_qkad102-B52","author":"Rossi","year":"2015"},{"key":"2024091323314056900_qkad102-B53","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-4250-5","volume-title":"Theory of statistics","author":"Schervish","year":"1995"},{"issue":"8","key":"2024091323314056900_qkad102-B54","doi-asserted-by":"publisher","first-page":"5163","DOI":"10.1109\/TIT.2011.2158885","article-title":"Rumors in a network: Who\u2019s the culprit?","volume":"57","author":"Shah","year":"2011","journal-title":"IEEE Transactions on Information Theory"},{"key":"2024091323314056900_qkad102-B55","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.osnem.2018.12.001","article-title":"Source detection of rumor in social network\u2014A review","volume":"9","author":"Shelke","year":"2019","journal-title":"Online Social Networks and Media"},{"issue":"4","key":"2024091323314056900_qkad102-B56","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/s10463-008-0181-5","article-title":"A preferential attachment model with poisson growth for scale-free networks","volume":"60","author":"Sheridan","year":"2008","journal-title":"Annals of the Institute of Statistical Mathematics"},{"issue":"20","key":"2024091323314056900_qkad102-B57","doi-asserted-by":"publisher","first-page":"5031","DOI":"10.1016\/j.physa.2012.05.041","article-title":"Measuring preferential attachment in growing networks with missing-timelines using Markov chain Monte Carlo","volume":"391","author":"Sheridan","year":"2012","journal-title":"Physica A: Statistical Mechanics and its Applications"},{"issue":"1","key":"2024091323314056900_qkad102-B58","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41598-019-38912-0","article-title":"Inferring temporal information from a snapshot of a dynamic network","volume":"9","author":"Sreedharan","year":"2019","journal-title":"Scientific Reports"},{"key":"2024091323314056900_qkad102-B59","doi-asserted-by":"crossref","DOI":"10.1017\/9781316779422","volume-title":"Random graphs and complex networks","author":"Van Der Hofstad","year":"2016"},{"issue":"2","key":"2024091323314056900_qkad102-B60","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1214\/17-BA1073","article-title":"Bayesian cluster analysis: Point estimation and credible balls (with discussion)","volume":"13","author":"Wade","year":"2018","journal-title":"Bayesian Analysis"},{"key":"2024091323314056900_qkad102-B62","doi-asserted-by":"publisher","author":"Wilson","year":"1996","DOI":"10.1145\/237814.237880"},{"key":"2024091323314056900_qkad102-B63","author":"Xie","year":"2019"},{"issue":"1","key":"2024091323314056900_qkad102-B64","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1214\/18-AOS1797","article-title":"Optimal rates for community estimation in the weighted stochastic block model","volume":"48","author":"Xu","year":"2018","journal-title":"Annals of Statistics"},{"issue":"4","key":"2024091323314056900_qkad102-B65","doi-asserted-by":"publisher","first-page":"041056","DOI":"10.1103\/PhysRevX.9.041056","article-title":"Phase transition in the recoverability of network history","volume":"9","author":"Young","year":"2019","journal-title":"Physical Review X"},{"issue":"4","key":"2024091323314056900_qkad102-B66","doi-asserted-by":"publisher","first-page":"452","DOI":"10.1086\/jar.33.4.3629752","article-title":"An information flow model for conflict and fission in small groups","volume":"33","author":"Zachary","year":"1977","journal-title":"Journal of Anthropological Research"}],"container-title":["Journal of the Royal Statistical Society Series B: Statistical Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/jrsssb\/advance-article-pdf\/doi\/10.1093\/jrsssb\/qkad102\/51772226\/qkad102.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/86\/4\/825\/59112678\/qkad102.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/86\/4\/825\/59112678\/qkad102.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T08:17:43Z","timestamp":1726301863000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jrsssb\/article\/86\/4\/825\/7283069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,26]]},"references-count":61,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,9,26]]},"published-print":{"date-parts":[[2024,9,13]]}},"URL":"https:\/\/doi.org\/10.1093\/jrsssb\/qkad102","relation":{},"ISSN":["1369-7412","1467-9868"],"issn-type":[{"value":"1369-7412","type":"print"},{"value":"1467-9868","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2024,9]]},"published":{"date-parts":[[2023,9,26]]}}}