Stratification in the Preferential Attachment Network
E. Ben-Naim and P.L. Krapivsky
We study structural properties of trees grown by preferential
attachment. In this mechanism, nodes are added sequentially and
attached to existing nodes at a rate that is strictly proportional to
the degree. We classify nodes by their depth $n$, defined as the
distance from the root of the tree, and find that the network is
strongly stratified. Most notably, the distribution $f_k^{(n)}$ of
nodes with degree $k$ at depth $n$ has a power-law tail,
$f_k^{(n)}\sim k^{-\gamma(n)}$. The exponent grows linearly with
depth, $\gamma(n)=2+\frac{n-1}{\langle n-1\rangle}$, where the
brackets denote an average over all nodes. Therefore, nodes that are
closer to the root are better connected, and moreover, the degree
distribution strongly varies with depth. Similarly, the in-component
size distribution has a power-law tail and the characteristic exponent
grows linearly with depth. Qualitatively, these behaviors extend to a
class of networks that grow by a redirection mechanism.
source,
ps,
pdf