Root finding algorithms and persistence of Jordan centrality in growing random trees

DOI10.1214/21-AAP1731zbMATH Open1503.05107arXiv2006.15609OpenAlexW3037680033WikidataQ113240928 ScholiaQ113240928MaRDI QIDQ2170374FDOQ2170374

Shankar Bhamidi, Sayan Banerjee

Publication date: 5 September 2022

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: We consider models of growing random trees $mathcal{T}_f(n):ngeq1$ with model dynamics driven by an attachment function $f:mathbb{Z}_{+}omathbb{R}_{+}$. At each stage a new vertex enters the system and connects to a vertex $v$ in the current tree with probability proportional to $f(extdegree(v))$. The main goal of this study is to understand the performance of root finding algorithms. A large body of work (e.g. the work of Bubeck, Devroye and Lugosi or Jog and Loh) has emerged in the last few years in using techniques based on the Jordan centrality measure and its variants to develop root finding algorithms. Given an unlabelled unrooted tree, one computes the Jordan centrality for each vertex in the tree and for a fixed budget $K$ outputs the optimal $K$ vertices (as measured by Jordan centrality). Under general conditions on the attachment function $f$, we derive necessary and sufficient bounds on the budget $K(epsilon)$ in order to recover the root with probability at least $1-epsilon$. For canonical examples such as linear preferential attachment and uniform attachment, these general results give matching upper and lower bounds for the budget. We also prove persistence of the optimal $K$ Jordan centers for any $K$, i.e. the existence of an almost surely finite random time $n^{*}$ such that for $ngeq{n}^{*}$ the identity of the $K$-optimal Jordan centers in $mathcal{T}_f(n):ngeq{n}^{*}$ does not change, thus describing robustness properties of this measure. Key technical ingredients in the proofs of independent interest include sufficient conditions for the existence of exponential moments for limits of (appropriately normalized) continuous time branching processes within which the models $mathcal{T}_f(n):ngeq{n}^{*}$ can be embedded, as well as rates of convergence results to these limits.

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

Recommendations

• Random trees and general branching processes
• The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees
• Vertices of high degree in the preferential attachment tree
• Degree distributions in recursive trees with fitnesses
• Trees grown under young-age preferential attachment
• A class of random recursive tree algorithms with deletion
• Persistence of centrality in random growing trees
• Geometry of weighted recursive and affine preferential attachment trees
• Uniform recursive trees: branching structure and simple random downward walk
• On the asymptotic behaviour of random recursive trees in random environments

zbMATH Keywords

centrality measuresrandom treestemporal networksrecursive distributional equationsCrump-Mode-Jagers processescontinuous time branching processesJordan centralityMalthusian rate of growthstable age distribution theory

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Applications of branching processes (60J85) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cites Work

• Statistical mechanics of complex networks
• Random graphs and complex networks. Volume 1
• Emergence of Scaling in Random Networks
• The Structure and Function of Complex Networks
• Networks. An introduction.
• Random Trees
• Random graphs.
• Random graph dynamics
• Title not available (Why is that?)
• Markov Chains
• Title not available (Why is that?)
• Seneta-Heyde norming in the branching random walk
• Component behavior near the critical point of the random graph process
• Embedding of Urn Schemes into Continuous Time Markov Branching Processes and Related Limit Theorems
• On generalized multiplicative cascades
• Fixed points of the smoothing transformation
• Rumors in a Network: Who's the Culprit?
• Asymptotic properties and absolute continuity of laws stable by random weighted mean.
• A fixed point theorem for distributions
• Elementary fixed points of the BRW smoothing transforms with infinite number of summands
• Random networks with sublinear preferential attachment: degree evolutions
• Random trees and general branching processes
• The growth and composition of branching populations
• Title not available (Why is that?)
• Scaling limits and influence of the seed graph in preferential attachment trees
• On the convergence of supercritical general (C-M-J) branching processes
• Continuity of limit random variables in the branching random walk
• Persistence of centrality in random growing trees
• A guide to temporal networks
• Finding Adam in random growing trees
• Existence of a persistent hub in the convex preferential attachment model
• Persistence of hubs in growing random networks
• Finding the seed of uniform attachment trees
• Discrete minimax estimation with trees
• Correlated randomly growing graphs
• Thin tails of fixed points of the nonhomogeneous smoothing transform
• A probabilistic approach to the leader problem in random graphs

Cited In (6)

• Degree centrality and root finding in growing random networks
• Fluctuation bounds for continuous time branching processes and evolution of growing trees with a change point
• Eve, Adam and the preferential attachment tree
• Archaeology of random recursive dags and Cooper-Frieze random networks
• Inference in balanced community modulated recursive trees
• The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees

This page was built for publication: Root finding algorithms and persistence of Jordan centrality in growing random trees

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