Finding Adam in random growing trees

DOI10.1002/RSA.20649MaRDI QIDQ2977563zbMATH OpenOpenAlexFDO

Authors Sébastien Bubeck, Luc Devroye, Gábor Lugosi

Publication date 18 April 2017

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

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

zbMATH Keywords

random treesroot-finding algorithmsPólya urns

Mathematics Subject Classification ID

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

Abstract: We investigate algorithms to find the first vertex in large trees generated by either the uniform attachment or preferential attachment model. We require the algorithm to output a set of $K$ vertices, such that, with probability at least $1-epsilon$, the first vertex is in this set. We show that for any $epsilon$, there exist such algorithms with $K$ independent of the size of the input tree. Moreover, we provide almost tight bounds for the best value of $K$ as a function of $epsilon$. In the uniform attachment case we show that the optimal $K$ is subpolynomial in $1/epsilon$, and that it has to be at least superpolylogarithmic. On the other hand, the preferential attachment case is exponentially harder, as we prove that the best $K$ is polynomial in $1/epsilon$. We conclude the paper with several open problems.

Recommendations

• Finding the seed of uniform attachment trees
• Looking for vertex number one
• Root finding algorithms and persistence of Jordan centrality in growing random trees
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• scientific article; zbMATH DE number 3858430

Cites work

• Branching processes in the analysis of the heights of trees
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• Limit theorems for triangular urn schemes
• On an elementary proof of some asymptotic formulas in the theory of partitions
• Rumors in a Network: Who's the Culprit?
• Scaling limits and influence of the seed graph in preferential attachment trees

Cited in

(27)

• Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
• The power of adaptivity in source identification with time queries on the path
• Permutation Tests for Infection Graphs
• Finding the root in random nearest neighbor trees
• Persistence of centrality in random growing trees
• 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
• Correlated randomly growing graphs
• Detecting a late changepoint in the preferential attachment model
• Root estimation in Galton–Watson trees
• Epicenter of random epidemic spanning trees on finite graphs
• Metric dimension of critical Galton-Watson trees and linear preferential attachment trees
• Eve, Adam and the preferential attachment tree
• Persistence of hubs in growing random networks
• Community modulated recursive trees and population dependent branching processes
• Archaeology of random recursive dags and Cooper-Frieze random networks
• Inference in balanced community modulated recursive trees
• Root finding algorithms and persistence of Jordan centrality in growing random trees
• From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
• Influence of the seed in affine preferential attachment trees
• Finding the seed of uniform attachment trees
• Uniform attachment with freezing
• Broadcasting on random recursive trees
• Estimating the history of a random recursive tree
• On a tail bound for analyzing random trees
• Network evolution with mesoscopic delays
• Change point detection in network models: preferential attachment and long range dependence

This page was built for publication: Finding Adam in random growing trees

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