The large deviation principle for inhomogeneous Erdős-Rényi random graphs

DOI10.1007/S10959-022-01181-1MaRDI QIDQ6161583zbMATH OpenOpenAlexWikidataFDO

Authors Maarten Markering

Publication date 5 June 2023

Published in Journal of Theoretical Probability (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2010.03504

zbMATH Keywords

graphoninhomogeneous Erdős-Rényi random graphlarge deviationslargest eigenvaluerate function

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Large deviations (60F10)

Abstract: Consider the inhomogeneous ErdH{o}s-R'enyi random graph (ERRG) on $n$ vertices for which each pair $i,jin1,ldots,n$, $ieqj$ is connected independently by an edge with probability $r_n(fraci-1n,fracj-1n)$, where $(r_n{)}_{ninmathbbN}$ is a sequence of graphons converging to a reference graphon $r$. As a generalization of the celebrated LDP for ERRGs by Chatterjee and Varadhan (2010), Dhara and Sen (2019) proved a large deviation principle (LDP) for a sequence of such graphs under the assumption that $r$ is bounded away from 0 and 1, and with a rate function in the form of a lower semi-continuous envelope. We further extend the results by Dhara and Sen. We relax the conditions on the reference graphon to $logr,log(1-r)in{L}^1([0,1{]}^2)$. We also show that, under this condition, their rate function equals a different, more tractable rate function. We then apply these results to the large deviation principle for the largest eigenvalue of inhomogeneous ERRGs and weaken the conditions for part of the analysis of the rate function by Chakrabarty, Hazra, Den Hollander and Sfragara (2020).

Recommendations

• The large deviation principle for the Erdős-Rényi random graph
• A large deviation principle for the Erdős-Rényi uniform random graph
• Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs
• On large deviation properties of Erdős-Rényi random graphs
• A sample-path large deviation principle for dynamic Erdős-Rényi random graphs
• A large-deviations principle for all the components in a sparse inhomogeneous random graph
• Large deviations for empirical measures of generalized random graphs
• An introduction to large deviations for random graphs
• A law of large numbers and large deviations for interacting diffusions on Erdős-Rényi graphs
• Large deviation principles for empirical measures of colored random graphs

Cites work

• An introduction to large deviations for random graphs
• Estimating and understanding exponential random graph models
• scientific article; zbMATH DE number 2171466 (Why is no real title available?)
• Large deviation for uniform graphs with given degrees
• Large deviations for random graphs. École d'Été de Probabilités de Saint-Flour XLV -- 2015
• Large networks and graph limits
• The large deviation principle for the Erdős-Rényi random graph

Cited in

(14)

• A large deviation principle for the Erdős-Rényi uniform random graph
• Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs
• The large deviation principle for interacting dynamical systems on random graphs
• Exponential Chebyshev inequalities for random graphons and their applications
• Ergodic theory on stationary random graphs
• Large deviation principle for the greedy exploration algorithm over Erdős-Rényi graphs
• A large-deviations principle for all the components in a sparse inhomogeneous random graph
• A sample-path large deviation principle for dynamic Erdős-Rényi random graphs
• Marked random graphs with given degree sequence: large deviations on the local topology and applications
• A large deviation principle for block models
• Large deviation principle for the norm of the Laplacian matrix of inhomogeneous Erdős-Rényi random graphs
• Large deviation principles for graphon sampling
• Large deviations for subgraphs in inhomogeneous random graphs
• On large deviation properties of Erdős-Rényi random graphs

This page was built for publication: The large deviation principle for inhomogeneous Erdős-Rényi random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6161583)