Eve, Adam and the preferential attachment tree (Q6617186)

This paper investigates a problem of network archaeology in the context of the Barabási-Albert (BA) model. The objective is to identify the initial vertex (``Adam'') in a large, growing random tree structure by outputting a subset of vertices (called the ``packet'') that contains Adam with high probability. The key insight presented is that Adam is either a high-degree vertex or closely connected to one (called ``Eve''). The study offers a new statistical approach for identifying this initial vertex by constructing confidence sets with reduced sizes, compared to previous methods, for achieving the desired level of certainty. \N\NThe key contributions of this paper can be summarized as follows:\N\begin{itemize}\N\item[1.] Sharper bound for the size of the confidence set: The paper fills a gap in the literature by proving that the lower bound on the size of the confidence set is sharp. It constructs a confidence set, \(P_\varepsilon(n)\), which contains Adam with probability at least \(1-\varepsilon\). The authors demonstrate that this set's size scales as \(\varepsilon^{-1-\eta}\) for small \(\eta>0\), improving upon previously known bounds that suggested the set's size could be as large as \(\varepsilon^{-2+o(1)}.\)\N\item[2.] Utilizing Eve to find Adam: The novel aspect of this work is the introduction of Eve, a vertex adjacent to Adam with a potentially large degree. The authors show that even if Adam has a relatively small degree, Eve is likely to have a high degree, allowing Adam's identification through their connection. This insight refines the search for Adam and reduces the size of the packet.\N\item[3.] Estimation of the degrees of vertices: The paper introduces precise asymptotic results for the degrees of vertices in the BA model. It provides upper and lower bounds on the probability that Adam and Eve's degrees meet specific conditions, enabling the effective construction of \(P_\varepsilon(n)\) based on their joint degree distribution.\N\item[4.] Application of stochastic techniques: The paper uses advanced stochastic tools, such as martingale theory and Beta and Gamma distributions, to derive the limiting degree distributions for vertices in the BA tree. These techniques are used to estimate the probability that Adam and Eve are included in the packet, providing rigorous justification for the proposed approach.\N\end{itemize}\NThis paper offers a significant contribution to the study of random trees and network archaeology by providing a new method for identifying the initial vertex in a preferential attachment tree. The introduction of Eve as a tool to locate Adam and the sharper bounds on the size of the confidence set advance the theoretical understanding of random graph models.