Random friend trees
Preprint
Abstract
We study a random recursive tree model featuring complete redirection called the random friend tree and introduced by Saramäki and Kaski. Vertices are attached in a sequential manner one by one by selecting an existing target vertex and connecting to one of its neighbours (or friends), chosen uniformly at random. This model has interesting emergent properties, such as a highly skewed degree sequence. In contrast to the preferential attachment model, these emergent phenomena stem from a local rather than a global attachment mechanism. The structure of the resulting tree is also strikingly different from both the preferential attachment tree and the uniform random recursive tree: every edge is incident to a macro-hub of asymptotically linear degree, and with high probability all but at most $n^{9/10}$ vertices in a tree of size $n$ are leaves. We prove various results on the neighbourhood of fixed vertices and edges, and we study macroscopic properties such as the diameter and the degree distribution, providing insights into the overall structure of the tree. We also present a number of open questions on this model and related models.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Structural results for the tree builder random walkThe Annals of Applied Probability, 2025
- Analysis of social network metrics based on the model of random recursive treeJournal of Interdisciplinary Mathematics, 2020
- Emergent network modularityJournal of Statistical Mechanics: Theory and Experiment, 2017
- Asymptotic degree distribution in random recursive treesRandom Structures & Algorithms, 2004
- Scale-free networks generated by random walkersPhysica A: Statistical Mechanics and its Applications, 2004
- Emergence of Scaling in Random NetworksScience, 1999
- The strong convergence of maximal degrees in uniform random recursive trees and dagsRandom Structures & Algorithms, 1995
- Note on the heights of random recursive trees and random m‐ary search treesRandom Structures & Algorithms, 1994
- Applications of the theory of records in the study of random treesActa Informatica, 1988