Mathematics – Probability
Scientific paper
2011-08-19
Mathematics
Probability
20 pages
Scientific paper
In this paper, we study some important statistics of the random graph in the Buckley-Osthus model. This model is a modification of the well-known Bollob\'as-Riordan model. We denote the number of nodes by t, the so-called initial attractiveness of a node by a. 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 positive integer values of a and d \le 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), R(d_2,t), and using the second moment method we show that R(d,t) is tightly concentrated around its mean for every 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.
No associations
LandOfFree
The degree distribution and the number of edges between nodes of given degrees in the Buckley-Osthus model of a random web graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The degree distribution and the number of edges between nodes of given degrees in the Buckley-Osthus model of a random web graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The degree distribution and the number of edges between nodes of given degrees in the Buckley-Osthus model of a random web graph will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-244160