Finding the seed of uniform attachment trees
From MaRDI portal
Publication:2631843
DOI10.1214/19-EJP268zbMATH Open1466.60013arXiv1801.01816OpenAlexW2964269465MaRDI QIDQ2631843FDOQ2631843
Authors: Gábor Lugosi, A. S. Pereira 
Publication date: 16 May 2019
Published in: Electronic Journal of Probability (Search for Journal in Brave)
Abstract: A uniform attachment tree is a random tree that is generated dynamically. Starting from a fixed "seed" tree, vertices are added sequentially by attaching each vertex to an existing vertex chosen uniformly at random. Upon observing a large (unlabeled) tree, one wishes to find the initial seed. We investigate to what extent seed trees can be recovered, at least partially. We consider three types of seeds: a path, a star, and a random uniform attachment tree. We propose and analyze seed-finding algorithms for all three types of seed trees.
Full work available at URL: https://arxiv.org/abs/1801.01816
Recommendations
- On finding most uniform spanning trees
- From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
- Uniform generation of a Schröder tree
- Uniform Generation of Rooted Ordered Trees with Prescribed Degrees
- Growing random uniform \(d\)-ary trees
- scientific article; zbMATH DE number 1101606
- Influence of the seed in affine preferential attachment trees
- Uniform and most uniform partitions of trees
- scientific article; zbMATH DE number 953290
- scientific article; zbMATH DE number 1263307
Estimation in multivariate analysis (62H12) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)
Cites Work
- Concentration inequalities. A nonasymptotic theory of independence
- Title not available (Why is that?)
- The central limit theorem for dependent random variables
- Random Trees
- Limit laws for local counters in random binary search trees
- Large deviations for sums of partly dependent random variables
- Rumors in a Network: Who's the Culprit?
- Scaling limits and influence of the seed graph in preferential attachment trees
- Looking for vertex number one
- On normal approximation rates for certain sums of dependent random variables
- Persistence of centrality in random growing trees
- Finding rumor sources on random trees
- Finding Adam in random growing trees
- From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
- Discrete minimax estimation with trees
Cited In (12)
- Degree centrality and root finding in growing random networks
- Correlated randomly growing graphs
- Root estimation in Galton–Watson trees
- Epicenter of random epidemic spanning trees on finite graphs
- Persistence of hubs in growing random networks
- Archaeology of random recursive dags and Cooper-Frieze random networks
- Inference in balanced community modulated recursive trees
- Finding Adam in random growing 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
- Broadcasting on random recursive trees
This page was built for publication: Finding the seed of uniform attachment trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2631843)
