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