Finding the seed of uniform attachment trees
From MaRDI portal
Publication:2631843
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.
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
Cites work
- Concentration inequalities. A nonasymptotic theory of independence
- Discrete minimax estimation with trees
- Finding Adam in random growing trees
- Finding rumor sources on 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 4170917 (Why is no real title available?)
- Large deviations for sums of partly dependent random variables
- Limit laws for local counters in random binary search trees
- Looking for vertex number one
- On normal approximation rates for certain sums of dependent random variables
- Persistence of centrality in random growing trees
- Random Trees
- Rumors in a Network: Who's the Culprit?
- Scaling limits and influence of the seed graph in preferential attachment trees
- The central limit theorem for dependent random variables
Cited in
(14)- Persistence of hubs in growing random networks
- Broadcasting on random recursive trees
- Correlated randomly growing graphs
- Root finding algorithms and persistence of Jordan centrality in growing random trees
- Influence of the seed in affine preferential attachment trees
- From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
- Finding Adam in random growing trees
- Epicenter of random epidemic spanning trees on finite graphs
- Root estimation in Galton–Watson trees
- Degree centrality and root finding in growing random networks
- Inference in balanced community modulated recursive trees
- Archaeology of random recursive dags and Cooper-Frieze random networks
- Estimating the history of a random recursive tree
- Uniform attachment with freezing
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)
