Large deviations of empirical neighborhood distribution in sparse random graphs

Abstract

Consider the Erdős-Renyi random graph on n vertices where each edge is present independently with probability c/n, with c>0 fixed. For large n, a typical random graph locally behaves like a Galton-Watson tree with Poisson offspring distribution with mean c. 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.

58 pages, 5 figures

Cited by in corpus (19)

• The condensation phase transition in random graph coloring
• Harnessing the Bethe free energy
• Limits of discrete distributions and Gibbs measures on random graphs
• A large-deviations principle for all the cluster sizes of a sparse Erdős-Rényi graph
• A large-deviations principle for all the components in a sparse inhomogeneous random graph
• A Notion of Entropy for Stochastic Processes on Marked Rooted Graphs
• Central limit theorem for statistics of subcritical configuration models
• Large Deviations of Non-Stochastic Interacting Particles on Sparse Random Graphs
• Universal Graph Compression: Stochastic Block Models
• Lossy Asymptotic Equipartition property for Networked Data Structures
• Local Large deviation: A McMillian Theorem for Coloured Random Graph Processes
• The core in random hypergraphs and local weak convergence
• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• Large deviation principles for empirical measures of the multitype random networks
• Entropies of tailored random graph ensembles: bipartite graphs, generalised degrees, and node neighbourhoods
• Large deviations for marked sparse random graphs with applications to interacting diffusions
• Large Deviation Principle for the Exploration Process of the Configuration Model
• Local Large deviations for empirical locality measure of typed Random Graph Models
• Marked random graphs with given degree sequence: large deviations on the local topology