Estimating the history of a random recursive tree
This work addresses a fundamental ordering problem in network analysis, with potential applications in understanding growth processes, but it is incremental as it builds on existing centrality measures and models.
The paper tackles the problem of estimating vertex arrival order in random recursive trees, such as uniform attachment and linear preferential attachment models, by proposing a Jordan centrality-based estimator that is proven nearly optimal and numerically outperforms degree-based and spectral methods.
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.