# Estimating the history of a random recursive tree

arXiv: https://arxiv.org/abs/2403.09755 · HTML: https://mlsanity.com/paper/2403.09755/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 32 references that are in the map.
- First posted on arXiv 14 Mar 2024.

## Builds on (most cited first, 12 of 12)

- [Localization in 1D non-parametric latent space models from pairwise affinities](https://mlsanity.com/paper/2108.03098/) (2021)
- [Finding Adam in random growing trees](https://mlsanity.com/paper/1411.3317/) (2014)
- [Reconstruction of Line-Embeddings of Graphons](https://mlsanity.com/paper/2007.06444/) (2020)
- [Reconstructing Latent Orderings by Spectral Clustering](https://mlsanity.com/paper/1807.07122/) (2018)
- [Root and community inference on the latent growth process of a network](https://mlsanity.com/paper/2107.00153/) (2021)
- [Archaeology of random recursive dags and Cooper-Frieze random networks](https://mlsanity.com/paper/2207.14601/) (2022)
- [From trees to seeds: on the inference of the seed from large trees in the uniform attachment model](https://mlsanity.com/paper/1409.7685/) (2014)
- [Persistence of centrality in random growing trees](https://mlsanity.com/paper/1511.01975/) (2015)
- [Analysis of centrality in sublinear preferential attachment trees via the CMJ branching process](https://mlsanity.com/paper/1601.06448/) (2016)
- [On the discovery of the seed in uniform attachment trees](https://mlsanity.com/paper/1810.00969/) (2018)
- [Depth of vertices with high degree in random recursive trees](https://mlsanity.com/paper/1611.07466/) (2016)
- [Inference for growing trees](https://mlsanity.com/paper/1910.04788/) (2019)

## Built on by (most cited first, 1 of 1)

- [History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities](https://mlsanity.com/paper/2606.24465/) (2026)

## 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.