A sample-path large deviation principle for dynamic Erdős–Rényi random graphs

The Annals of Applied Probability, vol. 33

Abstract

We consider a dynamic Erdős–Rényi random graph on n vertices in which each edge switches on at rate λ and switches off at rate μ, independently of other edges. The focus is on the analysis of the evolution of the associated empirical graphon in the limit as n→∞. Our main result is a large deviation principle (LDP) for the sample path of the empirical graphon observed until a fixed time horizon. The rate is ( n 2), the rate function is a specific action integral on the space of graphon trajectories. We apply the LDP to identify (i) the most likely path that starting from a constant graphon creates a graphon with an atypically large density of d-regular subgraphs, and (ii) the mostly likely path between two given graphons. It turns out that bifurcations may occur in the solutions of associated variational problems.

Authors 3

1. Peter Braunsteins

   University of Amsterdam

   Affiliation as printed

   Korteweg-de-Vries Instituut, Universiteit van Amsterdam

2. Frank den Hollander Aachen Mathematisch Instituut

   Leiden University

   Affiliation as printed

   Mathematisch Instituut, Universiteit Leiden

3. Michel Mandjes

   University of Amsterdam

   Affiliation as printed

   Korteweg-de-Vries Instituut, Universiteit van Amsterdam