Persistence of centrality in random growing trees

DOI10.1002/RSA.20726zbMATH Open1386.05176arXiv1511.01975OpenAlexW2963429368MaRDI QIDQ4601443FDOQ4601443

Authors: Varun Jog, Po-Ling Loh 

Publication date: 16 January 2018

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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 $Kge1$ 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.

Full work available at URL: https://arxiv.org/abs/1511.01975

Recommendations

• Root finding algorithms and persistence of Jordan centrality in growing random trees
• Finding Adam in random growing trees
• Degree centrality and root finding in growing random networks
• Persistence of hubs in growing random networks
• On the centroid of increasing trees

zbMATH Keywords

centralitydiffusion processpersistencepreferential attachmentuniform attachment

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Cited In (13)

• Existence of a persistent hub in the convex preferential attachment model
• Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
• Jordan centre in random trees: persistence and distance to root
• Degree centrality and root finding in growing random networks
• Correlated randomly growing graphs
• Eve, Adam and the preferential attachment tree
• Persistence of hubs in growing random networks
• Archaeology of random recursive dags and Cooper-Frieze random networks
• Kinetic maintenance of mobile \(k\)-centres on trees
• Root finding algorithms and persistence of Jordan centrality in growing random trees
• On the distribution of betweenness centrality in random trees
• Finding the seed of uniform attachment trees
• Centers for random walks on trees

This page was built for publication: Persistence of centrality in random growing trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601443)