Large deviation principles for empirical measures of colored random graphs

DOI10.1214/09-AAP647zbMATH Open1213.60054arXivmath/0607545OpenAlexW3104521118MaRDI QIDQ614113FDOQ614113

Authors: Kwabena Doku-Amponsah, Peter Mörters 

Publication date: 27 December 2010

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

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.

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

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

zbMATH Keywords

convergence ratelarge deviation principlerelative entropydegree distributioncolor distributionRandom graphvertex color

Mathematics Subject Classification ID

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

Cites Work

• The phase transition in inhomogeneous random graphs
• Large deviations for mixtures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Critical behavior in inhomogeneous random graphs
• Large deviations
• Bins and balls: Large deviations of the empirical occupancy process
• Some large deviation results for sparse random graphs
• Large deviations of \(U\)-empirical measures in strong topologies and applications
• Title not available (Why is that?)
• Large deviations in randomly coloured random graphs
• Large deviations of Markov chains indexed by random trees
• Asymptotic equipartition properties for simple hierarchical and networked structures

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
• Title not available (Why is that?)
• Large Deviations Principle for Occupancy Problems with Colored Balls
• Large deviations for empirical measures of generalized random graphs
• Sandpile groups of random bipartite 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)