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
- 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
- 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?)
- 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
(52)- On large deviation regimes for random media models
- Large deviations in randomly coloured random graphs
- Some large deviation results for sparse random graphs
- Large deviations in generalized random graphs with node weights
- Ensemble equivalence for dense graphs
- A large deviation approach to super-critical bootstrap percolation on the random graph \(G_{n, p}\)
- Recovering nonuniform planted partitions via iterated projection
- Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
- The large deviation principle for interacting dynamical systems on random graphs
- Rare event asymptotics for exploration processes for random graphs
- Large deviation for uniform graphs with given degrees
- Logarithmic Sobolev inequalities for finite spin systems and applications
- Nonconventional moderate deviations theorems and exponential concentration inequalities
- Localization in random geometric graphs with too many edges
- Nonlinear large deviations: beyond the hypercube
- 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
- Efficient, local and symmetric Markov chains that generate one-factorizations
- Bivariate fluctuations for the number of arithmetic progressions in random sets
- Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs
- Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
- Upper tails and independence polynomials in random graphs
- Stochastic processes in random graphs
- Nonlinear large deviations
- On replica symmetry of large deviations in random graphs
- Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
- A strong law of large numbers for random biased connected graphs
- Large deviation principle for the greedy exploration algorithm over Erdős-Rényi graphs
- Asymptotic Structure for the Clique Density Theorem
- Large-scale structures in random graphs
- scientific article; zbMATH DE number 5252621 (Why is no real title available?)
- A large-deviations principle for all the components in a sparse inhomogeneous random graph
- A large‐deviations principle for all the cluster sizes of a sparse Erdős–Rényi graph
- Deviation probabilities for arithmetic progressions and other regular discrete structures
- Moderate deviations in cycle count
- The number of triangles in random intersection graphs
- Parameter estimation in a 3‐parameter p‐star random graph model
- Large-deviation properties of largest component for random graphs
- The large deviation principle for inhomogeneous Erdős-Rényi random graphs
- Large deviations for the greedy exploration process on configuration models
- Large deviations for mean field model in Erdős-Rényi graph
- The large deviation principle for the Erdős-Rényi random graph
- Sub-critical exponential random graphs: concentration of measure and some applications
- 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
- Moderate deviations of triangle counts in the Erdős-Rényi random graph G (n, m): the lower tail
- Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs G(n, m) and G(n, p)
- The large deviation principle for W-random spectral measures
- Moderate deviations of triangle counts -- the lower tail (extended abstract)
- Large deviation principles for graphon sampling
- Large deviations of empirical neighborhood distribution in sparse random graphs
- On large deviation properties of Erdős-Rényi random graphs
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)
