Estimating the history of a random recursive tree
Simon Briend Christophe Giraud Gábor Lugosi Déborah Sulem
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.