Eve, Adam and the Preferential Attachment Tree
share
We consider the problem of finding the initial vertex (Adam) in a Barabási–Albert tree process (𝒯(n) : n ≥ 1) at large times. More precisely, given ε>0, one wants to output a subset 𝒫_ε(n) of vertices of 𝒯(n) so that the initial vertex belongs to 𝒫_ ε(n) with probability at least 1- ε when n is large. It has been shown by Bubeck, Devroye Lugosi, refined later by Banerjee Huang, that one needs to output at least ε^-1 + o(1) and at most ε^-2 + o(1) vertices to succeed. We prove that the exponent in the lower bound is sharp and the key idea is that Adam is either a “large degree" vertex or is a neighbor of a “large degree" vertex (Eve).
READ FULL TEXT