Persistence of centrality in random growing trees
Preprint
Abstract
We investigate properties of node centrality in random growing tree models. We focus on a measure of centrality that computes the maximum subtree size of the tree rooted at each node, with the most central node being the tree centroid. For random trees grown according to a preferential attachment model, a uniform attachment model, or a diffusion processes over a regular tree, we prove that a single node persists as the tree centroid after a finite number of steps, with probability 1. Furthermore, this persistence property generalizes to the top $K \ge 1$ nodes with respect to the same centrality measure. We also establish necessary and sufficient conditions for the size of an initial seed graph required to ensure persistence of a particular node with probability $1-\epsilon$, as a function of $\epsilon$: In the case of preferential and uniform attachment models, we derive bounds for the size of an initial hub constructed around the special node. In the case of a diffusion process over a regular tree, we derive bounds for the radius of an initial ball centered around the special node. Our necessary and sufficient conditions match up to constant factors for preferential attachment and diffusion tree models.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Confidence Sets for the Source of a Diffusion in Regular TreesIEEE Transactions on Network Science and Engineering, 2016
- Preferential attachment with choiceRandom Structures & Algorithms, 2015
- A survey of random processes with reinforcementProbability Surveys, 2007
- Centrality and network flowSocial Networks, 2005
- A Strategic Model of Social and Economic Networks2003
- Emergence of Scaling in Random NetworksScience, 1999
- Accretion centers: A generalization of branch weight centroidsDiscrete Applied Mathematics, 1981
- Another characterization of the centroid of a treeDiscrete Mathematics, 1978
- Some properties of a centroid of a free treeInformation Processing Letters, 1975
- Sur les assemblages de lignes.Journal für die reine und angewandte Mathematik (Crelles Journal), 1869