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

DOI10.1214/22-AAP1892MaRDI QIDQ6165256zbMATH OpenOpenAlexFDO

Authors Peter Braunsteins, F. den Hollander, M. R. H. Mandjes

Publication date 31 July 2023

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

Full work available at URL https://arxiv.org/abs/2009.12848, https://projecteuclid.org/journals/annals-of-applied-probability/volume-33/issue-4/A-sample-path-large-deviation-principle-for-dynamic-Erd%c5%91sR%c3%a9nyi-random/10.1214/22-AAP1892.full

zbMATH Keywords

dynamic random graphs graphon dynamics large deviation principle optimal path sample-path large deviations

Mathematics Subject Classification ID

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

Abstract: We consider a dynamic ErdH{o}s-R'enyi random graph (ERRG) on

n

vertices in which each edge switches on at rate

l a m b d a

and switches off at rate

m u

, independently of other edges. The focus is on the analysis of the evolution of the associated empirical graphon in the limit as

n o i n f t y

. 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

, 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.

Review text

In this paper, a large deviation principle (LDP) is derived for a model of dynamic inhomogeneous random graphs. This random graph process starts with a random graph on \(n\) vertices which comes from a given graphon. A random process is associated with each one of its edges where it becomes inactive with a certain rate \(\lambda>0\) and it is activated again at rate \(\mu>0\), where \(\lambda\) and \(\mu\) are real numbers. These random processes are independent. The dynamic gives rise to a graph-valued process \(G_{n,t}\) and the authors consider this for a finite interval \([0,T]\). Equivalently, this may be viewed as a graphon-valued process, since each graph gives rise to a (step) graphon. Using the cut metric on the space of graphons, one can define the Skorohod topology on the set of paths of this process. The authors derive a number of LDPs for this process, under the assumption that the initial graphon converges as \(n\to \infty\) to a given graphon. The first LDP is for the measure over graphons at time \(T\). Then an LDP is derived for the joint measure on graphons that occur at times \(t_1 < \cdots < t_k\leq T\). Finally, an LDP is derived for the measure of this process on the associated graphon-valued space of paths. Thereafter, two applications are discussed. The first is about the typical path that the process follows conditional that it ends up with an atypically large density of copies of a \(d\)-regular graph \(H\) (with respect to the initial graphon, which is assumed to be constant). In the second application, the uniqueness of the typical path is discussed conditional on the initial and the final graphons being close to two given graphons.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: A sample-path large deviation principle for dynamic Erdős-Rényi random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6165256)