Many large networks are formed by dynamic growth that can be modelled by
simple random mechanisms. A natural problem is to discover the "past"
of such networks by merely observing their present state. This talk
addresses one of the simplest such problems one may formulate: find the
the first vertex in large random trees generated by either the uniform
attachment or preferential attachment model. We study algorithms that,
upon observing the tree, output a set of K vertices. We require that, with
probability at least
1 - epsilon, the first vertex is in this set. We show that for any
epsilon,
there
exist such algorithms with K independent of the size of the tree.
The talk is based on joint work with Seb Bubeck and Luc Devroye.