An introduction to large deviations for random graphs
From MaRDI portal
Abstract: This article gives an overview of the emerging literature on large deviations for random graphs. Written for the general mathematical audience, the article begins with a short introduction to the theory of large deviations. This is followed by a description of some large deviation questions about random graphs, and an outline of the recent progress on this topic. A more elaborate discussion follows, with a brief account of graph limit theory and its application in constructing a large deviation theory for dense random graphs. The role of Szemer'edi's regularity lemma is explained, together with a sketch of the proof of the main large deviation result and some examples. Applications to exponential random graph models are briefly touched upon. The remainder of the paper is devoted to large deviations for sparse graphs. Since the regularity lemma is not applicable in the sparse regime, new tools are needed. Fortunately, there have been several new breakthroughs that managed to achieve the goal by an indirect method. These are discussed, together with an exposition of the underlying theory. The last section contains a list of open problems.
Recommendations
- Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
- Rare event asymptotics for exploration processes for random graphs
- The large deviation principle for the Erdős-Rényi random graph
- Nonlinear large deviations
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
Cites work
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 3780300 (Why is no real title available?)
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- Additive combinatorics
- An L^p theory of sparse graph convergence. I: Limits, sparse random graph models, and power law distributions
- An \(L^{p}\) theory of sparse graph convergence. II: LD convergence, quotients and right convergence
- Applications of Stein's method for concentration inequalities
- Asymptotic structure and singularities in constrained directed graphs
- Concentration of measure and isoperimetric inequalities in product spaces
- Concentration of multivariate polynomials and its applications
- Concentration of non‐Lipschitz functions and applications
- Consistency under sampling of exponential random graph models
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
- Counting graph homomorphisms
- Critical phenomena in exponential random graphs
- Divide and conquer martingales and the number of triangles in a random graph
- Emergent structures in large networks
- Estimating and understanding exponential random graph models
- Estimation of moments of sums of independent real random variables
- Graph limits and exchangeable random graphs
- Large deviations techniques and applications.
- Large networks and graph limits
- Limits of dense graph sequences
- Metrics for sparse graphs
- Mixing time of exponential random graphs
- Multipodal structure and phase transitions in large constrained graphs
- Nonconventional averages along arithmetic progressions and lattice spin systems
- Nonconventional large deviations theorems
- Nonconventional limit theorems
- Nonconventional limit theorems in discrete and continuous time via martingales
- On replica symmetry of large deviations in random graphs
- On the asymptotics of constrained exponential random graphs
- On the lower tail variational problem for random graphs
- Phase transitions in a complex network
- Phase transitions in exponential random graphs
- Probabilistic Symmetries and Invariance Principles
- Quick approximation to matrices and applications
- Representations for partially exchangeable arrays of random variables
- Singularities in the entropy of asymptotically large simple graphs
- Stein's method for concentration inequalities
- The asymptotics of large constrained graphs
- The large deviation principle for the Erdős-Rényi random graph
- The missing log in large deviations for triangle counts
- Tight upper tail bounds for cliques
- Upper tails and independence polynomials in random graphs
- Upper tails for subgraph counts in random graphs
- Upper tails for triangles
Cited in
(50)- Nonconventional moderate deviations theorems and exponential concentration inequalities
- A strong law of large numbers for random biased connected graphs
- Moderate deviations of triangle counts in the Erdős-Rényi random graph G (n, m): the lower tail
- The number of triangles in random intersection graphs
- Large-scale structures in random graphs
- Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
- Localization in random geometric graphs with too many edges
- Efficient, local and symmetric Markov chains that generate one-factorizations
- Recovering nonuniform planted partitions via iterated projection
- On replica symmetry of large deviations in random graphs
- Sub-critical exponential random graphs: concentration of measure and some applications
- A large deviation approach to super-critical bootstrap percolation on the random graph \(G_{n, p}\)
- The large deviation principle for inhomogeneous Erdős-Rényi random graphs
- On large deviation regimes for random media models
- Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs G(n, m) and G(n, p)
- On large deviation properties of Erdős-Rényi random graphs
- The large deviation principle for W-random spectral measures
- Large deviation principles for graphon sampling
- Moderate deviations of triangle counts -- the lower tail (extended abstract)
- Large deviations of subgraph counts for sparse Erdős-Rényi graphs
- Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs
- A large-deviations principle for all the components in a sparse inhomogeneous random graph
- Large-deviation properties of largest component for random graphs
- Ensemble equivalence for dense graphs
- Large deviations of empirical neighborhood distribution in sparse random graphs
- Large deviations in generalized random graphs with node weights
- Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
- Large deviations for the greedy exploration process on configuration models
- Nonlinear large deviations: beyond the hypercube
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- Upper tails and independence polynomials in random graphs
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- Marked random graphs with given degree sequence: large deviations on the local topology and applications
- Large deviations for mean field model in Erdős-Rényi graph
- The large deviation principle for interacting dynamical systems on random graphs
- Asymptotic Structure for the Clique Density Theorem
- Large deviations in randomly coloured random graphs
- Moderate deviations in cycle count
- Parameter estimation in a 3‐parameter p‐star random graph model
- The large deviation principle for the Erdős-Rényi random graph
- Rare event asymptotics for exploration processes for random graphs
- Bivariate fluctuations for the number of arithmetic progressions in random sets
- Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
- Stochastic processes in random graphs
- Logarithmic Sobolev inequalities for finite spin systems and applications
- A large‐deviations principle for all the cluster sizes of a sparse Erdős–Rényi graph
- Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs
- Nonlinear large deviations
- Large deviation principle for the greedy exploration algorithm over Erdős-Rényi graphs
- scientific article; zbMATH DE number 5252621 (Why is no real title available?)
This page was built for publication: An introduction to large deviations for random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2822847)
