Inference on the history of a randomly growing tree

Research output: Contribution to journalArticlepeer-review


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.

Original languageAmerican English
Pages (from-to)639-668
Number of pages30
JournalJournal of the Royal Statistical Society. Series B: Statistical Methodology
Issue number4
StatePublished - Sep 2021

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


  • network data analysis
  • random graph
  • root inference

Cite this