Estimating the history of a random recursive tree
This paper studies the problem of estimating the order of the arrival of the vertices in randomly growing trees, based only on the structure of the graph. Since the risk function (to be minimized by the estimate) gives more weight to the older vertices, the methods focus more on the early phase of the process. Hence, this problem is closely related to the question of finding the first vertex in a randomly growing graph, which has been studied by various methods in the literature in network archaeology. In the current paper, the authors elaborate a procedure based on the Jordan centrality measure, which is a significantly new approach. The random tree models examined are the uniform random recursive tree and the preferential attachment tree. The algorithm providing the estimate of the birth order of the vertices also includes randomness. A key notion is the Jordan centrality, which is based on a minimax argument. Given a tree \(T\) and a vertex \(u\in V(T)\), this is defined by \(\Psi_T(u)=\max_{v\in T, v\sim u} |(T,u)_v|\). A centroid of \(T\) is \(c=\arg \min_{u\in T} \Psi_T(u)\). Ordering the vertices with respect to the increasing values of \(\Psi_T(u)\) (and in a uniform random order if several vertices have the same centrality) is called the Jordan ordering procedure, which is analysed in the paper.\N\NAfter giving a lower bound of order \(n^{\gamma}\) (with \(n\) denoting the number of vertices and \(\gamma<2\) being an appropriate exponent, depending on the risk function) for the expected risk in case of the uniform random recursive tree, the authors prove an upper bound for the same quantity corresponding to the Jordan ordering procedure. Although there is a gap between the bounds, the exponents of \(n\) are the same. The main tool for finding the upper bound is a construction of another order and a coupling of this with the Jordan algorithm.\N\NAs for the preferential attachment tree, the lower bound matches the one for the uniform recursive tree, and the upper bound also has the same order as the one in the other model, only the constants differ. The proofs are based on the analysis of the degree distribution and various tools from probability theory and analysis. Putting together the main results of the paper, one can conclude that the structure of the underlying random tree model does not change the magnitude of the errors of the best estimates for reconstructing the birth order of the vertices.
- Archaeology of random recursive dags and Cooper-Frieze random networks
- Estimating the history of a random recursive tree
- Eve, Adam and the preferential attachment tree
- Finding Adam in random growing trees
- Finding rumor sources on random trees
- Finding the seed of uniform attachment trees
- From trees to seeds: on the inference of the seed from large trees in the uniform attachment model
- scientific article; zbMATH DE number 1744100 (Why is no real title available?)
- scientific article; zbMATH DE number 3073477 (Why is no real title available?)
- Inference on the History of a Randomly Growing Tree
- Localization in 1D non-parametric latent space models from pairwise affinities
- On the centroid of increasing trees
- On the discovery of the seed in uniform attachment trees
- Persistence of centrality in random growing trees
- Persistence of hubs in growing random networks
- Polya Urn Models
- Random Plane Networks
- Reconstruction of line-embeddings of graphons
- Root estimation in Galton–Watson trees
- Root finding algorithms and persistence of Jordan centrality in growing random trees
- Rumors in a Network: Who's the Culprit?
- The recovery of the root of a tree
This page was built for publication: Estimating the history of a random recursive tree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6896794)
