Graphon-valued processes with
vertex-level fluctuations

Graphons arise as a powerful tool for characterising the limit of a sequence of dense graphs, i.e., graphs in which the number of edges scales as the square of the number of vertices. The theory describing these graphons (see e.g. [21], [22], [4], [5], [20]) focuses on the limiting properties of large dense graphs in terms of their subgraph densities. The literature covers both typical and atypical behaviour, a notable result being the large deviation principle (LDP) for homogeneous Erdős-Rényi random graphs and associated graphons [9], and their inhomogeneous counterparts [12].

While most of the existing theory focuses on static random graphons, the attention has gradually shifted to dynamic random graphons (see e.g. [26], [7], [1]). Two notable contributions in this area are [1], which presents a stochastic process limit in the space of graphons for a class of processes where the edges evolve in a dependent manner, and [6], which extends the LDP of [9] to a sample-path LDP for a dynamic random graph in which the edges switch on and off independently in a random fashion. In [6] the authors leave open the question whether a sample-path large deviation principle can be established for processes where the edges switch on and off in a dependent manner, such as in [1].

The goal of the present paper is two-fold: (1) to answer the open question raised in [6] by establishing a sample-path large deviation principle for a class of processes in which edges evolve in a dependent manner; (2) to strengthen the results in [1] while working in a more general framework.

In the class of processes we consider, each vertex is assigned a type that changes randomly over time, and fluctuations in the types of the vertices determine how the edges interact with each other while switching on and off. Specifically, the paths of the types of all the vertices up to time $t$ determine the probability that the edges in the random graph are active at time $t$. Collectively, these paths are called the driving process.

Our results generalise those of [1] in a number of directions:

• (i)

  We establish sample-path large deviations (Theorem 3.5), whereas [1] restricts attention to diffusion limits.

• (ii)

  We consider a general driving process and a general edge-switching dynamics, whereas [1] restricts attention to a specific driving process (the multi-type Moran model) and to a specific edge-switching dynamics (modulated by a fitness function).

• (iii)

  We establish stochastic process convergence in the space of $({\mathscr{W}},d_{\square})$-valued càdlàg paths (Theorem 3.10), whereas [1] works in the space of $(\tilde{\mathscr{W}},\delta_{\square})$-valued Skorokhod paths. (For the definition of these two spaces, see Section 2.1 below.)

• (iv)

  We allow for processes in which the probabilities that edges are active depend not only on the fluctuations in the types but also on the state of the graph itself, i.e., on which edges are active or not (Section 4.1).

On the way to proving our results for graphon-valued processes, we also prove a new large deviation principle for static random graphs (Theorem 2.6). This result can be viewed as a generalisation of the large deviation principle for inhomogeneous Erdős-Rényi random graphs in which each vertex is assigned a random type. Our proofs rely on concentrations estimates, coupling arguments, and continuous mapping. Along the way, several examples are presented.

The models analysed in this paper have a one-way dependence: the states of the edges depend on the types of the vertices, but the types of the vertices do not depend on the states of the edges. There are many natural models that fall into this framework, coming from statistical physics, population genetics and the social sciences, where the strengths of the interactions between particles, alleles or individuals generally depend on the type they carry. It is much harder to analyse models that exhibit a two-way dependence. Such models capture the evolution of spins, infections or opinions on dynamic random networks with mutual feedback, an area that so far remains largely unexplored.

In Section 2 we recall basic LDPs for graphons, and present three LDPs for what we call inhomogeneous random graphs with type dependence (IRGTs), which are static random objects. In Section 3 we look at their dynamic counterparts, which are graph-valued processes, the main result being a sample-path LDP in graphon space. We illustrate our results via a running example, and derive convergence of the graph-valued process to a graphon process. In Section 4 we describe various applications, and discuss possible extensions. Section 5 contains the proofs of our main theorems. Appendix A identifies the rate function in the LDP of the underlying driving process.

Let $\mathscr{W}$ be the space of functions $h\colon\,[0,1]^{2}\to[0,1]$ such that $h(x,y)=h(y,x)$ for all $(x,y)\in[0,1]^{2}$, formed after taking the quotient with respect to the equivalence relation of almost everywhere equality. A finite simple graph $G$ on $n$ vertices can be represented as a graphon $h^{G}\in\mathscr{W}$ by setting

This object is referred to as an empirical graphon and has a block structure. The space of graphons $\mathscr{W}$ is endowed with the cut distance

It is noted that the space $(\mathscr{W},d_{\square})$ is not compact [19, Example F.6].

On $\mathscr{W}$ there is a natural equivalence relation, referred to as ‘$\sim$’. Letting $\mathscr{M}$ denote the set of measure-preserving bijections $\sigma\colon\,[0,1]\to[0,1]$, we write $h_{1}\sim h_{2}$ when there exists a $\sigma\in\mathscr{M}$ such that $h_{1}(x,y)=h_{2}(\sigma(x),\sigma(y))$ for all $(x,y)\in[0,1]^{2}$. This equivalence relation induces the quotient space $(\tilde{\mathscr{W}},\delta_{\square})$, where $\delta_{\square}$ is the cut metric defined by

Notably, the space $(\tilde{\mathscr{W}},\delta_{\square})$ is compact [21, Lemma 8].

Let $r\in\mathscr{W}$ be a reference graphon. Fix $n\in\mathbb{N}$ and consider a random graph $\widehat{G}_{n}$ with vertex set $[n]:=\{1,\dots,n\}$, where the pair of vertices $i,j\in[n]$, $i\neq j$, is connected by an edge with probability $r(\frac{i}{n},\frac{j}{n})$, independently of other pairs of vertices. Write $\mathbb{P}_{n}$ to denote the law of $\widehat{G}_{n}$. Use the same symbol to denote the law on $\mathscr{W}$ induced by the map that associates with the graph $\widehat{G}_{n}$ its graphon $h^{\widehat{G}_{n}}$. Write $\tilde{\mathbb{P}}_{n}$ to denote the law of $\tilde{h}^{\widehat{G}_{n}}$, the equivalence class associated with $h^{\widehat{G}_{n}}$.

The following theorem is an extension of the LDP for homogeneous Erdős-Rényi random graphs established in [9]. It was first stated in [12] under additional assumptions. These assumptions were subsequently relaxed in [24], [3], [13]. The following version of the LDP corresponds to [13, Theorem 4.1].

Consider the following generalisation of the inhomogeneous Erdős-Rényi random graph defined in Section 2.2. Suppose that each vertex $i\in[n]$ is assigned a (possibly random) type $X_{i}^{(n)}\in[0,1]$. Denote the empirical type measure by

and the empirical type distribution

where $\mathbbm{1}\{A\}$ is the indicator function of the event $A$ and ${\boldsymbol{X}}^{(n)}\equiv(X_{1}^{(n)},\ldots,X_{n}^{(n)})$. Let $\mathcal{M}([0,1])$ denote the space of measures on $[0,1]$ endowed with the topology of weak convergence.

The way the graph is constructed is as follows. Whether or not an edge $(i,j)$ is active depends on local properties, namely, the types $X_{i}^{(n)}$ and $X_{j}^{(n)}$, as well as global properties, namely, the empirical type distribution $F_{n}({\boldsymbol{X}}^{(n)},\cdot\,)$. Concretely, we let edge $ij$ be active with probability

where $H\colon\,[0,1]^{2}\times\mathcal{M}([0,1])\to[0,1]$ is symmetric in its first two inputs. Given ${\boldsymbol{X}}^{(n)}$, the edge placement is independent for all vertex pairs. We label the resulting sequence of random graphs as $\{G_{n}\}_{n\in\mathbb{N}}$, and refer to them as inhomogeneous random graphs with type dependence (IRGT).

Two relations with inhomogeneous Erdős-Rényi random graphs are worth mentioning:

• $\circ$

  Observe that if

  $$X_{i}^{(n)}=\frac{i}{n}\quad\forall\,n\in\mathbb{N},\,i\in[n],\qquad H(x,y,F)=r(x,y)\quad\forall\,x,y\in[0,1],$$

  (2.11)

  then the IRGT is equivalent to the inhomogeneous Erdős-Rényi random graph defined in Section 2.2.

• $\circ$

  Let $\bar{F}$ denote the right-continuous generalised inverse of a distribution function $F$ with support $[0,1]$, which is defined in the usual way as

  $$\bar{F}(u):=\inf\{x\in[0,1]\colon\,F(x)>u\},\qquad u\in[0,1).$$

  (2.12)

  For $F\in\mathcal{M}([0,1])$, define the induced reference graphon $g^{[F]}\in\mathscr{W}$ by setting

  $$g^{[F]}(x,y)=H\big{(}\bar{F}(x),\bar{F}(y),F\big{)}.$$

  (2.13)

  Given the type distribution $F_{n}$, $\tilde{h}^{G_{n}}$ has the same distribution as the inhomogeneous Erdős-Rényi random graph with reference graphon $g^{[F_{n}]}$. In other words, we have

  $$\tilde{h}^{G_{n}}\,|\,F_{n}\stackrel{{\scriptstyle\rm d}}{{=}}\tilde{h}^{\widehat{G}_{n}},\,r=g^{[F_{n}]}.$$

  (2.14)

  This observation is central to the LDP for IRGTs stated in Theorem 2.6 below.

Before stating Theorem 2.6, we make a number of assumptions.

When $X^{(n)}_{i}$, $i\in\mathbb{N}$, are fixed and $\mu_{n}\to\mu$ in $\mathcal{M}([0,1])$ as $n\to\infty$, as in (2.11), then Assumption 2.2 is satisfied with $\ell(n)=\infty$. Assumption 2.2 holds, for instance, when $\{X^{(n)}_{i}\}_{n\in\mathbb{N},i\in[n]}$ are i.i.d. random variables with distribution $f$, in which case $\ell(n)=n$ and $K(f^{\circ})={\mathscr{H}}(f^{\circ}\,|\,f)$ is the relative entropy (or Kullback-Leibler divergence) of $f^{\circ}$ with respect to $f$. Assumption 2.2 may also hold with $\ell(n)$ not scaling linearly in $n$.

To provide an example, we extend the setup in [13, Example 2.5]. Let $p>0$, $f$ be a probability distribution on $\mathbb{R}$ with bounded support, and $\{Y_{i}^{(n)}\}_{i\in[\lfloor n^{p}\rfloor]}$ be i.i.d. random variables with distribution $f$. Let $s_{n}$ be such that

and identify $s_{n}$ with its periodic extension to $\mathbb{R}$. Let $\rho$ be a smooth convolution kernel with compact support, and define

In this case $\ell(n)=n^{p}$ and

We refer the reader to [13, Example 2.5] for the arguments underlying this result.

Assumption 2.3 holds, for example, when $H(x,y,F)\equiv H^{*}(x,y)$ (i.e., there is no dependence on the type distribution) and $H^{*}\colon\,[0,1]^{2}\to[0,1]$ is a continuous function. Assumption 2.3 also holds when, in addition, $f\colon\,\mathcal{M}([0,1])\to[0,1]$ and $h\colon\,[0,1]^{2}\to[0,1]$ are continuous functions, and

In certain settings we require two further assumptions that are of a more technical nature.

Let

and recall that $(r,\tilde{h})\mapsto I_{r}(\tilde{h})$ is a function from $\mathscr{W}\times\tilde{\mathscr{W}}$ to $\mathbb{R}_{+}$. We are now ready to state our LDP for IRGTs.

To understand where Theorem 2.6 comes from, it is instructive to realize that two random mechanisms play a role, and that the dominant mechanism determines the rare event behavior. Concretely, think of simulating outcomes of $\tilde{h}^{\widehat{G}_{n}}$ in two steps:

• $\circ$

  Simulate the types of the vertices, i.e., simulate the type distribution $F_{n}$.

• $\circ$

  Simulate the edges given $F_{n}$, i.e., simulate $\tilde{h}^{\widehat{G}_{n}}$ given the induced reference graphon $g^{[F_{n}]}$.

Due to Assumption 2.2, large fluctuations in Step 1 are governed by the LDP with rate $\ell(n)$ and with rate function $K(\cdot)$, whereas due to (2.14) large fluctuations in Step 2 are governed by the LDP with rate ${n\choose 2}$ and with rate function $I_{g^{[F_{n}]}}$. In particular, this implies that when $\ell(n)=o\left({n\choose 2}\right)$ large fluctuations in $\tilde{h}^{\widehat{G}_{n}}$ are most likely to be caused by a rare event in Step 1, whereas when ${n\choose 2}=o(\ell(n))$ large fluctuations in $\tilde{h}^{\widehat{G}_{n}}$ are most likely to be caused by a rare event in Step 2. The regime $\ell(n)\asymp{n\choose 2}$ can be viewed as ‘balanced’, in the sense that large fluctuations in $\tilde{h}^{\widehat{G}_{n}}$ are most likely to be caused by a combination of rare events in both Steps 1 and 2. When $\ell(n)=o\left({n\choose 2}\right)$ we say that the IRGT exhibits vertex-level fluctuations, whereas when ${n\choose 2}=o(\ell(n))$ we say that it exhibits edge-level fluctuations.

The IRGT is of interest in its own right. However, our primary motivation for introducing the IRGT is that it can be generalized in a natural way to a stochastic process. The rough idea behind its dynamic counterpart is that at each point in time the distribution of the process corresponds to an IRGT. We will focus primarily on processes that exhibit vertex-level fluctuations.

For a given time horizon $T$, let $(G_{n}(t))_{t\in[0,T]}$ denote our graph-valued process. This process is constructed as follows. Suppose that each vertex $i\in[n]$ has a type $X^{(n)}_{i}(t)$ that may fluctuate randomly over time. Let $(\mu_{n}(t))_{t\in[0,T]}$ denote the process of empirical type measures defined by

i.e., the dynamic version of (2.8). This process evolves autonomously, i.e., independently of the graph-valued process $(G_{n}(t))_{t\in[0,T]}$.

In addition, let $(F_{n}(t;\cdot))_{t\in[0,T]}$ denote the process of empirical type distribution defined by

i.e., the dynamic counterpart of (2.9). The process $(\mu_{n}(t))_{t\in[0,T]}$ lives on $D(\mathcal{M}([0,1]),[0,T])$, the space of $\mathcal{M}([0,1])$-valued càdlàg paths. We suppose that, at any given time $t$, edge $ij$ is active with probability

independently of all other edges at time $t$, of $X^{(n)}_{i}(t)$, $X^{(n)}_{j}(t)$, and of $(F_{n}(t;\cdot))_{t\in[0,T]}$, where

This function $H$ gives rise to the induced reference graphon process $g^{[F]}$, which, for $F\in D(\mathcal{M}([0,1]),[0,T])$, is characterised by

Observe that, for any $t\in[0,T]$, given the outcome of the empirical type distribution $F_{n}(t,\cdot\,)$, the distribution of $\tilde{h}^{G_{n}(t)}$ corresponds to that of an inhomogeneous Erdős-Rényi random graph with reference graphon $g^{[F_{n}]}(t;\cdot,\cdot)$. In other words, for any $t\in[0,T]$,

where $\widehat{G}_{n}$ is the inhomogeneous Erdős-Rényi random graph defined in Section 2.2. We make the following assumption on the function $F\mapsto g^{[F]}$, which due to (3.5) is an assumption on $H$.

Suppose that $(G_{n}(t))_{t\in[0,T]}$ is characterised by the following dynamics:

• •

  $G_{n}(0)$ is the empty graph.

• •

  Each vertex is assigned an independent Poisson clock with rate $\gamma$, i.e., the time intervals between two consecutive ring times are exponentially distributed with parameter $\gamma$. Each time the clock attached to vertex $v$ rings, all the edges are adjacent to $v$ become inactive.

• •

  If the edge $ij$ is inactive, then it becomes active at rate $\lambda$, independently of anything else.

We first describe the associated driving process. Let $\{\tau_{k}(v)\}_{k\in\mathbb{N}}$ denote the sequence of times at which the Poisson clock attached to vertex $v$ rings, and let

denote the time since the clock last rung. The value of $Y_{v}(t)$ can be thought of as the age of vertex $v$ at time $t$: each time the clock associated with $v$ rings, it dies and all its adjacent edges are lost. Recalling that we assumed that types take values in $[0,1]$, we write

to denote the type of vertex $v$ at time $t$, where $F^{{\rm exp}}(\cdot)$ can be interpreted as the distribution function of an exponential random variable with rate $\gamma$.

The function $H(t;u,v,F)$ can now also be identified. The probability that there is an active edge between vertices of ages $\bar{u}$ and $\bar{v}$ is $1-\exp\{-\lambda(\bar{u}\wedge\bar{v})\}$. Putting $u=F^{{\rm exp}}(\bar{u})$ and $v=F^{{\rm exp}}(\bar{v})$, we obtain, using that $\bar{u}=-\log(1-u)/\gamma$ and $\bar{v}=-\log(1-v)/\gamma$,

Because $H(t;u,v,F)$ is a continuous function of $u$ and $v$, and is independent of $t$ and $F$, it is straightforward to verify that Assumption 3.1 holds. A more involved example is given in Section 4.1.

Similarly as in Section 2.5, we assume that the driving process satisfies the LDP (which for the above illustrative example is established in Lemma A.1).

To establish the sample-path LDP for the graphon-valued process $\{(\tilde{h}^{\widehat{G}_{n}(t)})_{t\geq 0}\}_{n\in\mathbb{N}}$, we need to:

• (I)

  establish the LDP in the pointwise topology;

• (II)

  strengthen this topology by establishing exponential tightness.

Step (I) is settled by the following result. For $\tilde{h}\in D((\tilde{\mathscr{W}},\delta_{\square}),[0,T])$, let

Note that Proposition 3.3 does not refer to any edge-switching dynamics. Specifically, if two process $\{G_{n}\}_{n\in\mathbb{N}}$ and $\{G^{*}_{n}\}_{n\in\mathbb{N}}$ have a common sequence of types $((X_{i}(t))_{t\geq 0})_{i\in[n]}$ and a common edge-connection function $H$, then the marginal distributions are equivalent, i.e.,

However, this does not necessarily mean that the joint distributions are equivalent, i.e., we may have

because these depend on the specific edge-switching dynamics. Nonetheless, Proposition 3.3 implies that both $\{G_{n}\}_{n\in\mathbb{N}}$ and $\{G^{*}_{n}\}_{n\in\mathbb{N}}$ satisfy equivalent LDPs in the pointwise topology, i.e., the rate function depends only on the marginal distributions of the process and not on the specific edge-switching dynamics. In Sections 4.1 and 4.2 we provide examples of processes with equivalent marginals and different edge-switching dynamics.

The specific edge-switching dynamics do need to be taken into consideration when we want to perform step (II), i.e., strengthen the topology of the LDP in Proposition 3.3 by establishing exponential tightness. We next provide a condition that can be used to verify that $\{\tilde{h}^{G_{n}}\}_{n\in\mathbb{N}}$ are exponentially tight. Let

and define

In other words, $C_{n}(t,\delta)$ is the number of edges that change (i.e., go from active to inactive or vice versa) at some time between $t$ and $t+\delta$.

Combining the above two propositions, we obtain the following.

In view of Lemma A.1, the conditions of Theorem 3.5 can be readily verified for the illustrative example. In Theorem 3.10 we establish a sample-path LDP for a class of processes that includes the illustrative example.

In the sequel, $\Rightarrow$ denotes convergence in distribution, and $\stackrel{{\scriptstyle\rm fdd}}{{\Rightarrow}}$ convergence of the associated finite-dimensional distributions. We assume that the empirical type distribution has a stochastic process limit.

We establish the stochastic process limit of $(h^{G_{n}(t)})_{t\in[0,T]}$ as $n\to\infty$ on $D((\mathscr{W},d_{\square}),[0,T])$, i.e., we no longer take the quotient with respect to the equivalence relation $\sim$. To establish a stochastic process limit in this finer topology, as explained below, we need to ensure that the labels of the vertices update dynamically.

The importance of Assumption 3.7 is illustrated in Figure 3.4, where we consider the illustrative example from Section 3.2 with $t=1$, $\lambda=6$ and $\gamma=3$. The left panel shows an outcome of $h^{G_{100}(1)}$ with a static labelling, where vertices are labelled arbitrarily at time $t=0$ and their labels do not change over time. We observe that $h^{G_{100}(1)}$ has no discernible structure, and so with probability 1 the sequence $(h^{G_{n}(1)})_{n\in\mathbb{N}}$ does not converge to a limit in $(\mathscr{W},d_{\square})$. The center panel of Figure 3.4 illustrates an outcome of $h^{G_{100}(1)}$ under the dynamic labelling given in Assumption 3.7. Under this assumption $h^{G_{100}(1)}$ has a discernible structure and $h^{G_{n}(1)}\to g$ in $(\mathscr{W},d_{\square})$ as $n\to\infty$, where $g$ is the smooth graphon illustrated in the right panel of Figure 3.4.