Estimating the history of a random recursive tree

2024/03/14 by Briend, Simon, Giraud, Christophe, Lugosi, Gábor +1
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Social and Information Networks (cs.SI)

paper · doi:10.48550/arxiv.2403.09755

Abstract

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.

Related

• MSO 0-1 law for recursive random trees
• A Random Walk Approach to Broadcasting on Random Recursive Trees
• Ordered increasing k-trees: Introduction and analysis of a preferential attachment network model
• Random Friend Trees
• Random friend trees