Correlated uniform attachment trees
2026-06-01 • Social and Information Networks
Social and Information Networks
AI summaryⓘ
The authors study a new kind of growing tree model where two trees grow side-by-side with some connection between how new branches attach in each. They focus on estimating how much the growth choices are correlated, using only the final unlabeled trees. Their main method uses a concept called Jordan centrality to find important early nodes common to both trees, and then uses the sizes of small subtrees to guess which nodes appeared when. They prove their estimator works better as the trees get larger and also provide new insights about how early nodes remain central over time.
Uniform Attachment TreeCorrelationJordan CentralityNetwork ArchaeologyFringe SubtreeEstimationUnlabeled TreeTime LabelsConsistent Estimator
Authors
Johannes Bäumler, Miklós Z. Rácz, Nathan Ross, Anirudh Sridhar
Abstract
We introduce and study a new model of correlated uniform attachment (UA) trees, where correlation is sprinkled throughout the time evolution of the process. In this model, two UA trees are grown in parallel, and at each time step a new node is added to each tree, with an edge between it and a uniformly chosen existing vertex in the respective tree. The two choices of attachment are correlated: with probability $α$, the edges attach to nodes with the same time label in both trees, and with probability $1-α$, the choices are made independently. We study fundamental detection and estimation questions for this model, given two \emph{unlabeled} trees. In our main result, we construct a consistent estimator of the correlation parameter $α$, as the size of the trees goes to infinity. The construction of our statistic relies on two key ideas. First, we use Jordan centrality to identify subsets of vertices of each tree whose intersection has a sufficient number of common early vertices. The second idea is that, across multiple time scales, it is possible to approximately determine the labels of vertices that have attached to these early vertices, using the sizes of fringe subtrees. Our analysis includes novel quantitative bounds on the fraction of early vertices that remain central, which are of independent interest in the network archaeology literature.