Large deviation principles for empirical measures of coloured random graphs

Kwabena Doku-Amponsah, Peter Morters

Research output: Contribution to journalArticle

6 Citations (Scopus)

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 Erdos-Renyi graphs near criticality.
Original languageEnglish
Pages (from-to)1989-2021
Number of pages33
JournalAnnals of Applied Probability
Volume20
Issue number6
DOIs
Publication statusPublished - Dec 2010

Fingerprint

Colored Graph
Empirical Measures
Large Deviation Principle
Random Graphs
Count
Weak Topology
Rate Function
Relative Entropy
Degree Distribution
Finite Graph
Criticality
Erdös
Graph in graph theory
Color
Large deviations
Random graphs
Graph
Model

Keywords

  • random graph
  • degree distribution
  • typed graph
  • entropy
  • partition function
  • random randomly colored graph
  • relative entropy
  • spins
  • Ising model on a random graph
  • Erdos-Renyi graph
  • joint large deviation principle
  • empirical pair measure
  • empirical measure

Cite this

Large deviation principles for empirical measures of coloured random graphs. / Doku-Amponsah, Kwabena; Morters, Peter.

In: Annals of Applied Probability, Vol. 20, No. 6, 12.2010, p. 1989-2021.

Research output: Contribution to journalArticle

Doku-Amponsah, Kwabena ; Morters, Peter. / Large deviation principles for empirical measures of coloured random graphs. In: Annals of Applied Probability. 2010 ; Vol. 20, No. 6. pp. 1989-2021.
@article{de44552d4ee444b08c5c5e9fb73cbcb8,
title = "Large deviation principles for empirical measures of coloured random graphs",
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 Erdos-Renyi graphs near criticality.",
keywords = "random graph, degree distribution, typed graph, entropy, partition function, random randomly colored graph, relative entropy, spins, Ising model on a random graph, Erdos-Renyi graph, joint large deviation principle, empirical pair measure, empirical measure",
author = "Kwabena Doku-Amponsah and Peter Morters",
year = "2010",
month = "12",
doi = "10.1214/09-AAP647",
language = "English",
volume = "20",
pages = "1989--2021",
journal = "Annals of Applied Probability",
issn = "1050-5164",
publisher = "Institute of Mathematical Statistics",
number = "6",

}

TY - JOUR

T1 - Large deviation principles for empirical measures of coloured random graphs

AU - Doku-Amponsah, Kwabena

AU - Morters, Peter

PY - 2010/12

Y1 - 2010/12

N2 - 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 Erdos-Renyi graphs near criticality.

AB - 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 Erdos-Renyi graphs near criticality.

KW - random graph

KW - degree distribution

KW - typed graph

KW - entropy

KW - partition function

KW - random randomly colored graph

KW - relative entropy

KW - spins

KW - Ising model on a random graph

KW - Erdos-Renyi graph

KW - joint large deviation principle

KW - empirical pair measure

KW - empirical measure

UR - http://www.scopus.com/inward/record.url?scp=78650502851&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1214/09-AAP647

U2 - 10.1214/09-AAP647

DO - 10.1214/09-AAP647

M3 - Article

VL - 20

SP - 1989

EP - 2021

JO - Annals of Applied Probability

JF - Annals of Applied Probability

SN - 1050-5164

IS - 6

ER -