Degree Distribution and Number of Edges between Nodes of Given Degrees in the Buckley - Osthus Model of a Random Web Graph

摘要

In this paper, we study some important statistics of the random graph (H_(a.k))~(t) in the Buckley-Osthus model, where t is the number of nodes, kt is the number of edges (so that k ∈N), and a > 0 is the so-called initial attractiveness of a node. This model is a modification of the well-known Bollobas-Riordan model. First, we find a new asymptotic formula for the expectation of the number R(d, t) of nodes of a given degree d in a graph in this model. Such a formula is known for a ∈ N and d ≤ t~(1/100(a+1)). Both restrictions are unsatisfactory from theoretical and practical points of view. We completely remove them. Then we calculate the covariances between any two quantities R(d_1, t) and R(d_2, t), and using the second-moment method we show that R(d, t) is tightly concentrated around its mean for all possible values of d and t. Furthermore, we study a more complicated statistic of the web graph: X(d_1, d_2, t) is the total number of edges between nodes whose degrees are equal to d_1 and d_2 respectively. We also find an asymptotic formula for the expectation of X(d_1, d_2, t) and prove a tight concentration result. Again, we do not impose any substantial restrictions on the values of d_1, d_2, and t.