Estimating the history of a random recursive tree
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910746437222400 |
|---|---|
| author | Briend, Simon Giraud, Christophe Lugosi, Gábor Sulem, Déborah |
| author_facet | Briend, Simon Giraud, Christophe Lugosi, Gábor Sulem, Déborah |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_09755 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Estimating the history of a random recursive tree Briend, Simon Giraud, Christophe Lugosi, Gábor Sulem, Déborah Machine Learning Social and Information Networks 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. |
| title | Estimating the history of a random recursive tree |
| topic | Machine Learning Social and Information Networks |
| url | https://arxiv.org/abs/2403.09755 |