2011/08/19 by Evgeniy Grechnikov, Grechnikov, Evgeniy A.
Computer Science · Mathematics · Physics and Astronomy · #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1108.4054
openalex publication_date 2011/08/19 · openalex created_date 2022/10/07 · openalex updated_date 2026/07/28
In this paper, we study some important statistics of the random graph in the\nBuckley-Osthus model. This model is a modification of the well-known\nBollob 'as-Riordan model. We denote the number of nodes by t, the so-called\ninitial attractiveness of a node by a. First, we find a new asymptotic formula\nfor the expectation of the number R(d,t) of nodes of a given degree d in a\ngraph in this model. Such a formula is known for positive integer values of a\nand d \≤ t1/100(a+1). Both restrictions are unsatisfactory from theoretical\nand practical points of view. We completely remove them. Then we calculate the\ncovariances between any two quantities R(d1,t), R(d2,t), and using the second\nmoment method we show that R(d,t) is tightly concentrated around its mean for\nevery possible values of d and t. Furthermore, we study a more complicated\nstatistic of the web graph: X(d1,d2,t) is the total number of edges between\nnodes whose degrees are equal to d1 and d2 respectively. We also find an\nasymptotic formula for the expectation of X(d1,d2,t) and prove a tight\nconcentration result. Again, we do not impose any substantial restrictions on\nthe values of d1, d2, and t.\n