Random Ancestor Trees

E. Ben-Naim and P.L. Krapivsky

We investigate a network growth model in which the genealogy controls the evolution. In this model, a new node selects a random target node and links either to this target node, or to its parent, or to its grandparent, etc; all nodes from the target node to its most ancient ancestor are equiprobable destinations. The emerging random ancestor tree is very shallow: the fraction $g_n$ of nodes at distance $n$ from the root decreases super-exponentially with $n$, $g_n=e^{-1}/(n-1)!$. We find that a macroscopic hub at the root coexists with highly connected nodes at higher generations. The maximal degree of a node at the $n$th generation grows algebraically as $N^{1/\beta_n}$ where $N$ is the system size. We obtain the series of nontrivial exponents which are roots of transcendental equations: $\beta_1\cong 1.351746$, $\beta_2\cong 1.682201$, etc. As a consequence, the fraction $p_k$ of nodes with degree $k$ has algebraic tail, $p_k\sim k^{-\gamma}$, with $\gamma=\beta_1+1=2.351746$.


source, ps, pdf