{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T08:40:41Z","timestamp":1790844041942,"version":"4.1.0"},"reference-count":33,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T00:00:00Z","timestamp":1677196800000},"content-version":"vor","delay-in-days":580,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1454817"],"award-info":[{"award-number":["DMS-1454817"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NSF DMS-2113671"],"award-info":[{"award-number":["NSF DMS-2113671"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The spread of infectious disease in a human community or the proliferation of fake news on social media can be modelled as a randomly growing tree-shaped graph. The history of the random growth process is often unobserved but contains important information such as the source of the infection. We consider the problem of statistical inference on aspects of the latent history using only a single snapshot of the final tree. Our approach is to apply random labels to the observed unlabelled tree and analyse the resulting distribution of the growth process, conditional on the final outcome. We show that this conditional distribution is tractable under a shape exchangeability condition, which we introduce here, and that this condition is satisfied for many popular models for randomly growing trees such as uniform attachment, linear preferential attachment and uniform attachment on a D-regular tree. For inference of the root under shape exchangeability, we propose O(n log n) time algorithms for constructing confidence sets with valid frequentist coverage as well as bounds on the expected size of the confidence sets. We also provide efficient sampling algorithms which extend our methods to a wide class of inference problems.<\/jats:p>","DOI":"10.1111\/rssb.12428","type":"journal-article","created":{"date-parts":[[2021,7,24]],"date-time":"2021-07-24T11:06:01Z","timestamp":1627124761000},"page":"639-668","source":"Crossref","is-referenced-by-count":11,"title":["Inference on the History of a Randomly Growing Tree"],"prefix":"10.1093","volume":"83","author":[{"given":"Harry","family":"Crane","sequence":"first","affiliation":[{"name":"Department of Statistics, Rutgers University , New Brunswick , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Min","family":"Xu","sequence":"additional","affiliation":[{"name":"Department of Statistics, Rutgers University , New Brunswick , USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2021,7,24]]},"reference":[{"key":"2023022501100315800_","volume-title":"Root finding algorithms and persistence of Jordan centrality in growing random trees","author":"Banerjee","year":"2020"},{"issue":"5439","key":"2023022501100315800_","doi-asserted-by":"crossref","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":"2023022501100315800_","volume-title":"Universal techniques to analyze preferential attachment trees: global and local analysis","author":"Bhamidi","year":"2007"},{"issue":"3","key":"2023022501100315800_","doi-asserted-by":"crossref","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"},{"issue":"1","key":"2023022501100315800_","doi-asserted-by":"crossref","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":"4A","key":"2023022501100315800_","doi-asserted-by":"crossref","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":"2","key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1002\/rsa.20649","article-title":"Finding Adam in random growing trees","volume":"50","author":"Bubeck","year":"2017","journal-title":"Random Structures & Algorithms"},{"issue":"25","key":"2023022501100315800_","doi-asserted-by":"crossref","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":"2023022501100315800_","volume-title":"Recovering the past states of growing trees","author":"Cantwell","year":"2019"},{"issue":"1","key":"2023022501100315800_","first-page":"1","article-title":"The ubiquitous Ewens sampling formula","volume":"31","author":"Crane","year":"2016","journal-title":"Statistical Science"},{"issue":"2","key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1017\/jsl.2017.61","article-title":"Relatively exchangeable structures","volume":"83","author":"Crane","year":"2018","journal-title":"Journal of Symbolic Logic"},{"key":"2023022501100315800_","volume-title":"On the discovery of the seed in uniform attachment trees","author":"Devroye","year":"2018"},{"key":"2023022501100315800_","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":"2023022501100315800_","doi-asserted-by":"crossref","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":"2023022501100315800_","volume-title":"Statistical tables for biological, agricultural and medical research","author":"Fisher","year":"1943"},{"issue":"2","key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"3979","DOI":"10.1214\/17-EJS1356","article-title":"Consistent estimation in general sublinear preferential attachment trees","volume":"11","author":"Gao","year":"2017","journal-title":"Electronic Journal of Statistics"},{"issue":"3","key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1093\/aje\/kws006","article-title":"Robust reconstruction and analysis of outbreak data: influenza a(h1n1)v transmission in a schoolbased population","volume":"176","author":"Hens","year":"2012","journal-title":"American Journal of Epidemiology"},{"issue":"3","key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s00440-005-0442-7","article-title":"Limit theorems for triangular urn schemes","volume":"134","author":"Janson","year":"2006","journal-title":"Probability Theory and Related Fields"},{"issue":"1","key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TNSE.2016.2622923","article-title":"Analysis of centrality in sublinear preferential attachment trees via the crump-mode-jagers branching process","volume":"4","author":"Jog","year":"2016","journal-title":"IEEE Transactions on Network Science and Engineering"},{"issue":"1","key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1002\/rsa.20726","article-title":"Persistence of centrality in random growing trees","volume":"52","author":"Jog","year":"2018","journal-title":"Random Structures & Algorithms"},{"issue":"4","key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1098\/rsif.2005.0051","article-title":"Networks and epidemic models","volume":"2","author":"Keeling","year":"2005","journal-title":"Journal of the Royal Society Interface"},{"issue":"1","key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1109\/TNSE.2016.2627502","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":"2023022501100315800_","volume-title":"The art of computer programming: Volume 1: Fundamental algorithms","author":"Knuth","year":"1997"},{"key":"2023022501100315800_","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-88146-1","volume-title":"Statistical analysis of network data: Methods and model","author":"Kolaczyk","year":"2009"},{"key":"2023022501100315800_","doi-asserted-by":"crossref","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":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1145\/3178876.3186105","article-title":"Times: temporal information maximally extracted from structures","author":"Magner","year":"2018","journal-title":"Proceedings of the 2018 World Wide Web Conference"},{"key":"2023022501100315800_","first-page":"361","article-title":"Dynamic generation of discrete random variates","author":"Matias","year":"1993","journal-title":"Proceedings of the ACM Symposium on Discrete Algorithms"},{"issue":"8","key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"5163","DOI":"10.1109\/TIT.2011.2158885","article-title":"Rumors in a network: who's the Culprit?","volume":"57","author":"Shah","year":"2011","journal-title":"IEEE Transactions on information theory"},{"issue":"3","key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1287\/opre.2015.1455","article-title":"Finding rumor sources on random tree","volume":"64","author":"Shah","year":"2016","journal-title":"Operations research"},{"key":"2023022501100315800_","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1016\/j.osnem.2018.12.001","article-title":"Source detection of rumor in social network\u2013a review","volume":"9","author":"Shelke","year":"2019","journal-title":"Online Social Networks and Media"},{"issue":"1","key":"2023022501100315800_","doi-asserted-by":"crossref","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":"2023022501100315800_","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevE.102.032304","volume-title":"Choosing among alternative histories of a tree","author":"Tim\u00e1r","year":"2020"},{"issue":"4","key":"2023022501100315800_","doi-asserted-by":"crossref","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"}],"container-title":["Journal of the Royal Statistical Society Series B: Statistical Methodology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/rssb.12428","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1111\/rssb.12428","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/83\/4\/639\/49320709\/jrsssb_83_4_639.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jrsssb\/article-pdf\/83\/4\/639\/49320709\/jrsssb_83_4_639.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,6]],"date-time":"2023-11-06T12:18:24Z","timestamp":1699273104000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jrsssb\/article\/83\/4\/639\/7056025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,24]]},"references-count":33,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,7,24]]},"published-print":{"date-parts":[[2021,9,1]]}},"URL":"https:\/\/doi.org\/10.1111\/rssb.12428","relation":{},"ISSN":["1369-7412","1467-9868"],"issn-type":[{"value":"1369-7412","type":"print"},{"value":"1467-9868","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,9]]},"published":{"date-parts":[[2021,7,24]]}}}