In this paper, we study some important statistics of the random graph _H_^(t)_a,k in the Buckley–Osthus model, where _t_ is the number of nodes, _kt_ is the number of edges (so that ), and _a_>0 is the so-called initial attractiveness of a node. This model is a modification of the well-known Bollobás–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 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_₁, _t_) and _R_(_d_₂, _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_₁, _d_₂, _t_) is the total number of edges between nodes whose degrees are equal to _d_₁ and _d_₂ respectively. We also find an asymptotic formula for the expectation of _X_(_d_₁, _d_₂, _t_) and prove a tight concentration result. Again, we do not impose any substantial restrictions on the values of _d_₁, _d_₂, and _t_.

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

This website uses cookies