The degree distribution and the number of edges between nodes of given degrees in directed scale-free graphs

Abstract

In this paper, we study some important statistics of the random graph in the directed preferential attachment model introduced by B. Bollobás, C. Borgs, J. Chayes and O. Riordan. First, we find a new asymptotic formula for the expectation of the number $n_{in}(d,t)$ of nodes of a given in-degree $d$ in a graph in this model with $t$ edges, which covers all possible degrees. The out-degree distribution in the model is symmetrical to the in-degree distribution. Then we prove tight concentration for $n_{in}(d,t)$ while $d$ grows up to the moment when $n_{in}(d,t)$ decreases to ${\ln }^{2}t$; if $d$ grows even faster, $n_{in}(d,t)$ is zero \textbf{whp}. Furthermore, we study a more complicated statistic of the graph: $X(d_1,d_2,t)$ is the total number of edges from a vertex of out-degree $d_1$ to a vertex of in-degree $d_2$. We also find an asymptotic formula for the expectation of $X(d_1,d_2,t)$ and prove a tight concentration result.

25 pages

References in corpus (2)

• Emergence of scaling in random networks
• Structure of Growing Networks: Exact Solution of the Barabasi--Albert's Model