Estimating the history of a random recursive tree
- Briend, Simon ORCID UniDistance Suisse
- Giraud, Christophe
- Lugosi, Gábor
- Sulem, Déborah
-
2024
English
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.
- Identifiers
-
- DOI 10.48550/ARXIV.2403.09755
- URI https://pub.orcid.org/v3.0/0009-0009-8655-0532/work/183074223
- ARK ark:/51647/srd1336043
- Persistent URL
- https://n2t.net/ark:/51647/srd1336043
Statistics
Document views: 5
File downloads:
- Estimating-the-history-of-a-random-recursive-tree.pdf: 8