05829432

j

05829432 Doku-Amponsah, Kwabena M\"orters, Peter Large deviation principles for empirical measures of colored random graphs. Ann. Appl. Probab. 20, No. 6, 1989-2021 (2010). 2010 Institute of Mathematical Statistics, Hayward, CA EN Random graph vertex color color distribution degree distribution large deviation principle convergence rate relative entropy

doi:10.1214/09-AAP647

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. Ove Frank (Stockholm)