Consider the Erdős–Renyi random graph on (n ) vertices where each edge is present independently with probability ( n ), with ( >0 ) fixed. For large (n ), a typical random graph locally behaves like a Galton–Watson tree with Poisson offspring distribution with mean ( ). Here, we study large deviations from this typical behavior within the framework of the local weak convergence of finite graph sequences. The associated rate function is expressed in terms of an entropy functional on unimodular measures and takes finite values only at measures supported on trees. We also establish large deviations for other commonly studied random graph ensembles such as the uniform random graph with given number of edges growing linearly with the number of vertices, or the uniform random graph with given degree sequence. To prove our results, we introduce a new configuration model which allows one to sample uniform random graphs with a given neighborhood distribution, provided the latter is supported on trees. We also introduce a new class of unimodular random trees, which generalizes the usual Galton Watson tree with given degree distribution to the case of neighborhoods of arbitrary finite depth. These generalized Galton Watson trees turn out to be useful in the analysis of unimodular random trees and may be considered to be of interest in their own right.
As far as we know, this is the first time that large deviations of the neighborhood distribution are addressed in a systematic way. While our approach does not cover results on connectivity and the size of connected components such as @cite_7 , it does yield a simplification of some of the existing arguments concerning the large deviations for degree sequences. We point out that our Corollary gives a corrected version of [Corollary 2.2] MR2759726 . Under a stronger sparsity assumption, large deviations of neighborhood distributions for random networks have been used in @cite_24 to study the large deviations of the spectral measure of certain random matrices.
@cite_24 @cite_7
2053990689 2063553966
We consider @math Hermitian matrices with i.i.d. entries @math whose tail probabilities @math behave like @math for some @math and @math . We establish a large deviation principle for the empirical spectral measure of @math with speed @math with a good rate function @math that is finite only if @math is of the form @math for some probability measure @math on @math , where @math denotes the free convolution and @math is Wigner's semicircle law. We obtain explicit expressions for @math in terms of the @math th moment of @math . The proof is based on the analysis of large deviations for the empirical distribution of very sparse random rooted networks. We obtain a large deviation principle (LDP) for the relative size of the largest connected component in a random graph with small edge probability. The rate function, which is not convex in general, is determined explicitly using a new technique. The proof yields an asymptotic formula for the probability that the random graph is connected.