Large deviation principles for empirical measures of colored random graphs

DOI10.1214/09-AAP647MaRDI QIDQ614113zbMATH OpenOpenAlexFDO

Authors Kwabena Doku-Amponsah, Peter Mörters

Publication date 27 December 2010

Published in The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

convergence ratelarge deviation principlerelative entropydegree distributioncolor distributionRandom graphvertex color

Mathematics Subject Classification ID

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

Abstract: For any finite colored graph we define the empirical neighborhood measure, which counts the number of vertices of a given color connected to a given number of vertices of each color, and the empirical pair measure, which counts the number of edges connecting each pair of colors. For a class of models of sparse colored random graphs, we prove large deviation principles for these empirical measures in the weak topology. The rate functions governing our large deviation principles can be expressed explicitly in terms of relative entropies. We derive a large deviation principle for the degree distribution of ErdH{o}s--R'{e}nyi graphs near criticality.

Recommendations

• Large deviations in randomly coloured random graphs
• Joint large deviation principle for some empirical measures of the \(d\)-regular random graphs
• Large deviations of empirical neighborhood distribution in sparse random graphs
• The large deviation principle for the Erdős-Rényi random graph
• Some large deviation results for sparse random graphs

Cites work

• scientific article; zbMATH DE number 1158743 (Why is no real title available?)
• scientific article; zbMATH DE number 1959499 (Why is no real title available?)
• scientific article; zbMATH DE number 3255204 (Why is no real title available?)
• Asymptotic equipartition properties for simple hierarchical and networked structures
• Bins and balls: Large deviations of the empirical occupancy process
• Critical behavior in inhomogeneous random graphs
• Large deviations
• Large deviations for mixtures
• Large deviations in randomly coloured random graphs
• Large deviations of Markov chains indexed by random trees
• Large deviations of U-empirical measures in strong topologies and applications
• Some large deviation results for sparse random graphs
• The phase transition in inhomogeneous random graphs

Cited in

(14)

• Joint large deviation principle for some empirical measures of the \(d\)-regular random graphs
• The large deviation principle for inhomogeneous Erdős-Rényi random graphs
• Degeneracy in sparse ERGMs with functions of degrees as sufficient statistics
• Limit laws for the number of triangles in the generalized random graphs with random node weights
• Moderate deviation in colored random graphs
• Large deviations of empirical neighborhood distribution in sparse random graphs
• Scale-free graphs with many edges
• Bins and balls: Large deviations of the empirical occupancy process
• The large deviation principle for interacting dynamical systems on random graphs
• Large deviations in randomly coloured random graphs
• scientific article; zbMATH DE number 1191595 (Why is no real title available?)
• Large Deviations Principle for Occupancy Problems with Colored Balls
• Sandpile groups of random bipartite graphs
• Large deviations for empirical measures of generalized random graphs

This page was built for publication: Large deviation principles for empirical measures of colored random graphs

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