An Application of Talagrand’s Inequality to Prove a Concentration of Second Degrees in Buckley-Osthus Random Graph Model

We consider the random graph model $H_{a,m}^n$. An explicit construction of this model was suggested by Buckley and Osthus. For any fixed positive integer $m$ and positive real $a$ we define a random graph $H_{a,m}^n$ in the following way. The graph $H_{a,1}^1$ consists of one vertex and one loop. Given a graph $H_{a,1}^{t-1}$ we transform it into $H_{a,1}^{t}$ by adding one new vertex and one new random edge $(t,i)$, where $i in {1, dots, t }$ and $Prob(i=t) = frac{a}{(a+1)t-1}$, $Prob(i=s) = frac{d_{H_{a,1}^{t-1}}(s) – 1 + a}{(a+1)t-1}$ if $1 le s le t-1$. To construct $H_{a,m}^n$ with $m>1$ we start from $H_{a,1}^{mn}$. Then we identify the vertices $1, dots, m$ to form the first vertex; we identify the vertices $m+1, dots, 2m$ to form the second vertex, etc.

The Buckley and Osthus random graph is a model of real-world networks. The parameter $a$ is called an “initial attractiveness” of a vertex. It was shown (by Buckley and Osthus for integer $a$ and by Grechnikov for real $a$) that the degree sequence in this model follows a power law distribution with exponent $-2-a$. We study second degrees of vertices in $H_{a,m}^n$. By the second degree of $t$ we mean the number of edges adjacent to the neighbors of $t$ except for the edges adjacent to the vertex $t$. Second degree of a vertex is an approximation of the PageRank. We show that the distribution of second degrees in $H_{a,1}^n$ follows a power law with exponent $-1-a$.

Proof of this result consists of two parts. The first step is to calculate the expectation of the number of vertices with second degree $k$ and the second step is to obtain a concentration. I will talk about the second step. It is a non-trivial application of Talagrand’s inequality. Instead of Talagrand’s inequality it is possible to apply Azuma’s inequality, but the result will be weaker.