This post will outline the paper Finding Adam in random growing trees by Bubeck, Devroye, and Lugosi. The main question examined in this paper is simply stated and relatively unstudied: given a tree, which has been generated under some attachment model, find the first vertex. “First” here meaning oldest. Think about the spread of a rumor, or disease. In these situations, the resulting distribution is known, but the starting point is not.
In a tree generated under a uniform attachment model (UA model), each new node added in the tree connects uniformly at random to exactly one existing node. Below is an example of a random graph generated under a uniform attachment model.
In a tree generated under a preferential attachment model (PA model), each new node added in the tree connects to exactly one existing node with probability proportional to its degree. Think of it like the rich get richer. Below is an example of a random graph generated under a preferential attachment model.
What does this paper prove?
Given a tree on vertices and an error bound , a root-finding algorithm outputs a set of size vertices such that as , with probability at least , the first vertex is in .
Now the insight as to why root-finding algorithms are interesting: the size of the vertex set output by a root-finding algorithm does not depend on the size of the tree. The size of the set output only depends on the probability that the first vertex is in that set, but the tree can be huge and it doesn’t matter.
Finding Adam highlights proofs of the following:
- The existence of root-finding algorithms for trees generated from a uniform or preferential attachment model.
- A root-finding algorithm for trees generated from the UA model, where the size of the set found by the algorithm is sub-polynomial in . Bounds for the best value of are almost tight for trees grown under the UA model.
- An impossibility result showing that for a tree grown under the PA model, root-finding algorithms output a set of size at least polynomial in .
Existence of root-finding algorithms
First, note that it’s not obvious that root-finding algorithms even exist. The authors point out that one heuristic which would not work in this situation is to output the set of vertices from the tree which have large degree. This seems like a reasonable heuristic, as the older the vertex is, the more likely it is to have more edges (especially under the uniform attachment model). However, in order for such a set to contain the first vertex with constant probability, it must be of size at least logarithmic in the number of vertices in the tree. For a tree generated under the UA model, a simple expectation calculation on the degree of the first vertex after vertices are in the tree and knowledge of concentration inequalities should convince you of this.
The authors construct a simple root-finding algorithm, which given a tree , generated under the UA or PA model, and target accuracy , produces a set of vertices of size .
Theorem 1a For a tree with vertices generated under the uniform attachment model, the simple root-finding algorithm produces such that for ,
Theorem 1b For a tree with vertices generated under the preferential attachment model, the simple root-finding algorithm produces such that for for some constant ,
A simple root-finding algorithm
Let denote the tree with first vertex , and let denote the subtree starting at . Define the function such that
In other words, inputs a vertex , views as the first vertex of the tree, then returns the size of the largest subtree starting at some child of . An example is given for a tree below.
Then let be the mapping which returns the set with the smallest values. This procedure satisfies Theorems 1a and 1b, but the proofs are omitted in this post (check the paper if you want to see them).
Doing better under the UA model
The simple root-finding algorithm outputs a set of size for a tree grown under the UA model. Next, the paper explains an algorithm which outputs a set of size subpolynomial in .
Theorem 2 For a tree with vertices generated under the UA model, there exist universal constants such that if , then
The authors note that the function defined in the simple root-finding algorithm can be viewed as a relaxation of a likelihood function. So they define a tighter relaxation of a likelihood function to improve the result under the UA model. Let denote the tree with first vertex , and let denote the subtree starting at . Define the function such that
Let be a mapping which returns the vertices in with the smallest values.
The values returned by make sense intuitively. A leaf will have value , and a vertex near the center of the tree will have large value. Using the same example tree given earlier for the simple root finding algorithm:
This procedure satisfies Theorem 2, but the proofs are omitted in this post (Again, check the paper to read it).
Can’t do much better under the PA model
In the section above, the set output has size subpolynomial in . For a tree generated under the PA model, the set output has size at least polynomial in .
Theorem 3. For a tree with vertices generated under the PA model, there exists such that for , any procedure that satisfies
in the preferential attachment model must have .
Basically, a tree grown under the preferential attachment model is more likely to have its first vertex be isomorphic to a bunch of leaves. So the first vertex is indistinguishable in some set of leaves
Outline proof of Theorem 3
Earlier in the paper, it’s shown that the probability of error for the optimal procedure is nondecreasing in , which means that finding the first vertex doesn’t get easier as the tree grows. Thus, it suffices to show that the optimal procedure has probability of error for some finite . We’ll show for which with probability , the first vertex is isomorphic to at least vertices in the tree. In this setting, any algorithm which outputs less than vertices has probability of error at least .
The probability that the first vertex is a leaf is . Let , and the probability that the first vertex is a leaf is . Given that the first vertex is a leaf, the probability that vertex 2 is connected to leaves is . All of these leaves would be isomorphic to the first vertex.
Previous work on similar problems
The authors state that they have not found any evidence of previous work that has been done on root-finding algorithms. However, variants of this problem have been studied by others. In Looking for vertex one Frieze and Pegden give an algorithm which finds the first vertex of a tree generated under the PA model and runs, with high probability, in sub-polynomial time. Their approach uses only information about the neighborhoods of single vertices.
Another interesting pre-cursor was in a series of papers by Bubeck et al., Curien et al., and another from Bubeck et al.. These papers proved that trees are heavily by their structure after some finite number of steps. This gives evidence towards the existence of root-finding algorithms, as trees which look different late in their growth, looked different earlier in their lives.