# Finding Adam in random growing trees

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Nov 2014.

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

- [Diffusion Source Identification on Networks with Statistical Confidence](https://mlsanity.com/paper/2106.04800/) (2021)
- [Archaeology of random recursive dags and Cooper-Frieze random networks](https://mlsanity.com/paper/2207.14601/) (2022)
- [Estimating the history of a random recursive tree](https://mlsanity.com/paper/2403.09755/) (2024)
- [Leaf Stripping on Uniform Attachment Trees](https://mlsanity.com/paper/2410.06481/) (2024)
- [History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities](https://mlsanity.com/paper/2606.24465/) (2026)

## Abstract (arXiv)

We investigate algorithms to find the first vertex in large trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of K vertices, such that, with probability at least 1-ε, the first vertex is in this set. We show that for any ε, there exist such algorithms with K independent of the size of the input tree. Moreover, we provide almost tight bounds for the best value of K as a function of ε. In the uniform attachment case we show that the optimal K is subpolynomial in 1/ε, and that it has to be at least superpolylogarithmic. On the other hand, the preferential attachment case is exponentially harder, as we prove that the best K is polynomial in 1/ε. We conclude the paper with several open problems.