A study of centrality measures in random recursive trees
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911530911531008 |
|---|---|
| author | Josifov, Richard Coll Devroye, Luc Lugosi, Gabor |
| author_facet | Josifov, Richard Coll Devroye, Luc Lugosi, Gabor |
| contents | We investigate the behaviour of five classical centrality measures--Jordan, rumor, betweenness, degree, and closeness centralities--in the setting of uniform random recursive trees. Motivated by applications in network archaeology, we focus on two fundamental questions: (i) the birth index (time of arrival) of the most central vertex, and (ii) the relative centrality of the root. We quantify the probability that the root is the most central vertex, analyze its expected rank under each centrality measure, and determine the expected birth index of a central vertex. In addition, we characterize the typical size of the set of top-ranked vertices that contains the root with high probability. Finally, for each centrality notion, we study the persistence properties of the center and the asymptotic behaviour of the root's rank. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_19493 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A study of centrality measures in random recursive trees Josifov, Richard Coll Devroye, Luc Lugosi, Gabor Probability We investigate the behaviour of five classical centrality measures--Jordan, rumor, betweenness, degree, and closeness centralities--in the setting of uniform random recursive trees. Motivated by applications in network archaeology, we focus on two fundamental questions: (i) the birth index (time of arrival) of the most central vertex, and (ii) the relative centrality of the root. We quantify the probability that the root is the most central vertex, analyze its expected rank under each centrality measure, and determine the expected birth index of a central vertex. In addition, we characterize the typical size of the set of top-ranked vertices that contains the root with high probability. Finally, for each centrality notion, we study the persistence properties of the center and the asymptotic behaviour of the root's rank. |
| title | A study of centrality measures in random recursive trees |
| topic | Probability |
| url | https://arxiv.org/abs/2603.19493 |