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

color distributionconvergence ratedegree distributionlarge deviation principleRandom graphrelative entropyvertex color

Mathematics Subject Classification ID

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

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.

Review text

A random graph on n vertices has vertex colors chosen independently according to a common color distribution on a finite color set. Conditional on the vertex colors, edges are independently attached to the unordered vertex pairs with connection probability depending on n and the connected vertex colors. Empirical counting measures are considered for the number of vertices of each color, the number of edges between each pair of colors, and the number of vertices of each color with specified numbers of neighbors of each color. Large deviation principles are given for these measures, and their rate functions are expressed in terms of relative entropies. As a special case, a large deviation principle is stated for the degree distribution of a Bernoulli graph with expected degree converging to a constant.

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

• 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
• 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?)
• Large deviations
• Large deviations for mixtures
• Large deviations in randomly coloured random graphs
• Large deviations of U-empirical measures in strong topologies and applications
• Large deviations of Markov chains indexed by random trees
• Some large deviation results for sparse random graphs
• The phase transition in inhomogeneous random graphs

Cited in

(16)

• Large deviations in randomly coloured random graphs
• Bins and balls: Large deviations of the empirical occupancy process
• The large deviation principle for interacting dynamical systems on random graphs
• Large deviation for uniform graphs with given degrees
• 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
• Sandpile groups of random bipartite graphs
• Moderate deviation in colored random graphs
• scientific article; zbMATH DE number 1191595 (Why is no real title available?)
• Joint large deviation principle for some empirical measures of the d-regular random graphs
• Large deviations for empirical measures of generalized random graphs
• Large Deviations Principle for Occupancy Problems with Colored Balls
• The large deviation principle for inhomogeneous Erdős-Rényi random graphs
• Scale-free graphs with many edges
• On the upper tail of star counts in random graphs
• Large deviations of empirical neighborhood distribution in sparse 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)