Scale-free graphs with many edges (Q6177606)

This paper is a study of large deviations in the number of edges of an inhomogeneous random graph. In the particular model that is considered, the vertices \(1,\ldots, n\) are equipped with weights that are i.i.d. random variables \(X_1,\ldots, X_n\), respectively, sampled from a distribution that has expected value \(\mu\) and whose tail scales as \(x^{-\alpha}\), for some \(\alpha >1\). Each distinct pair of vertices \(ij\) is included as an edge independently of any other pair with probability proportional to the product \(X_iX_j\) scaled by \(\mu n\). The main result of the paper is an asymptotic estimate of the probability that the number of edges exceeds \((\mu/2 + a )n\). They prove that this is asymptotic to \((n \mathbb{P}(X_1>n))^{\lceil a \rceil}\). This result is based on the observation that the main contribution to the result that the number of edges \(E_n\) exceeds \((\mu/2 + a)n\) comes from the existence of \(\lceil a\rceil\) vertices of very high weights which are proportional to \(n\). Furthermore, the authors establish a large deviation principle for the random variable \(E_n/n - \mu/2\), showing that its rate function is \((\alpha -1)\lceil x \rceil\) and its speed is \(\log n\).