Estimating the history of a random recursive tree
Not on the map. Why?
Abstract (arXiv)
This paper studies the problem of estimating the order of arrival of the vertices in a random recursive tree. Specifically, we study two fundamental models: the uniform attachment model and the linear preferential attachment model. We propose an order estimator based on the Jordan centrality measure and define a family of risk measures to quantify the quality of the ordering procedure. Moreover, we establish a minimax lower bound for this problem, and prove that the proposed estimator is nearly optimal. Finally, we numerically demonstrate that the proposed estimator outperforms degree-based and spectral ordering procedures.
Key facts. Cited by 1 paper in the map (data through 13 Oct 2026). Builds on 12 of its 32 references that are in the map. First posted on arXiv 14 Mar 2024.
Builds on
12 of 32 references.
References · 12
- 2021Localization in 1D non-parametric latent space models from pairwise affinitiescited by 7
- 2014Finding Adam in random growing treescited by 5
- 2020Reconstruction of Line-Embeddings of Graphonscited by 5
- 2018Reconstructing Latent Orderings by Spectral Clusteringcited by 4
- 2021Root and community inference on the latent growth process of a networkcited by 4
- 2022Archaeology of random recursive dags and Cooper-Frieze random networkscited by 4
- 2014From trees to seeds: on the inference of the seed from large trees in the uniform attachment modelcited by 3
- 2015Persistence of centrality in random growing treescited by 3
- 2016Analysis of centrality in sublinear preferential attachment trees via the CMJ branching processcited by 3
- 2018On the discovery of the seed in uniform attachment treescited by 3
- 2016Depth of vertices with high degree in random recursive treescited by 1
- 2019Inference for growing treescited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.