A sample-path large deviation principle for dynamic Erdős-Rényi random graphs (Q6165256)
From MaRDI portal
scientific article; zbMATH DE number 7720505
Language | Label | Description | Also known as |
---|---|---|---|
English | A sample-path large deviation principle for dynamic Erdős-Rényi random graphs |
scientific article; zbMATH DE number 7720505 |
Statements
A sample-path large deviation principle for dynamic Erdős-Rényi random graphs (English)
0 references
31 July 2023
0 references
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.
0 references
dynamic random graphs
0 references
graphon dynamics
0 references
optimal path
0 references
sample-path large deviations
0 references
large deviation principle
0 references
0 references
0 references
0 references