Grechnikov, Evgeniy A. Degree distribution and number of edges between nodes of given degrees in the Buckley-Osthus model of a random web graph. (English) Zbl 1258.05112 Internet Math. 8, No. 3, 257-287 (2012). Summary: 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 \(k \in \mathbb{N}\)), 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 \(a \in \mathbb{N}\) and \(d \leq 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\). Cited in 4 Documents MSC: 05C80 Random graphs (graph-theoretic aspects) Keywords:initial attractiveness of a node; random graph; Buckley-Osthus model; random web graph; Bollobas-Riordan model; second moment method; tight concentation × Cite Format Result Cite Review PDF Full Text: DOI arXiv Euclid