2.1. Notational conventions

We use the symbols $\mathbb{N}$ and $\mathbb{R}$ to denote the set of natural numbers and the set of real numbers, respectively. Also, we use $\mathbb{N}_0 \,:\!=\, \mathbb{N} \cup \{0\}$ and $\mathbb{R}_{+} \,:\!=\, \mathbb{R} \setminus ({-}\infty,0]$ . Given $R \subseteq \mathbb{R}$ , we denote the $\sigma$ -field of Borel subsets of R by $\mathcal{B} ({R})$ . Recall $\mathcal{T}_{0} \,:\!=\, [0, T]$ for some $t>0$ . We denote by $D=D(\mathcal{T}_{0})$ the space of real functions on $\mathcal{T}_{0}$ that are right continuous and have left-hand limits. Functions in D are called càdlàg. Unless otherwise mentioned, the space D is assumed to be endowed with the Skorokhod topology [Reference Billingsley14, Chapter 3], which turns D into a Polish space. We call D the Skorokhod space. Let the triplet $(\Omega, \mathcal{F}, \mathbb{P})$ denote our probability space. For an event A, we use $\mathsf{1}\!\left({A}\right)$ to denote the indicator (or characteristic) function of A. We shall use the shorthand notation $ ( a)_{b} = a(a-1)(a-2)\cdots(a-b+1)$ for $a>b$ and $a,b \in \mathbb{N}$ . The symbols $\mathop{}\!O{\left({.}\right)}$ and $\mathop{}\!o{\left({.}\right)}$ are the big-O and small-o notation, respectively, and they carry their usual meanings. For a differentiable function f defined on some set $E \subseteq \mathbb{R}^d$ , we denote its partial derivative with respect to the ith variable by $\partial_i\, f$ , for $i= 1,2, \ldots, d$ . With some abuse of notation, we use $\partial f(x)$ to denote the derivative of a differentiable function of a single variable at x. For a stochastic process Z(t) with paths in D, we denote the associated jump process $Z(t)-Z(t{-})$ by $\delta Z(t)$ . We also define $\mathcal{T} \,:\!=\, (0,T] \subset \mathcal{T}_{0}$ .

2.2. Model

We begin with the class of all CM random graphs [Reference Van der Hofstad47, Chapter 7] with n vertices, for $n \in \mathbb{N}$ . The main advantage of the CM is that it allows one to fix the degrees before constructing the graph itself. There are numerous real-life situations where random graphs with a prescribed degree sequence (or a probability distribution for the degree sequence) are reasonable and intuitive. See [Reference Van der Hofstad47, Chapter 7] for some examples.

Given degrees $d_1,d_2, \ldots, d_n$ for n vertices, we first assign $d_i$ half-edges to vertex i. The CM random graph is then obtained by matching (or pairing) all available half-edges uniformly at random. Two paired half-edges form an edge. We assume the degrees $d_1, d_2, \ldots, d_n$ are drawn from a probability distribution, which we call the degree distribution. If the sum of the drawn degrees is not even, we add a parity half-edge to the last vertex. That is, we first draw $d_1, d_2, \ldots, d_{n-1}$ and $d_{n}^{\prime}$ as an independent and identically distributed random sample from the degree distribution and then set $d_n \,:\!=\, d_{n}^{\prime} + \mathsf{1}\!\left({d_{n}^{\prime} + \sum_{j=1}^{n-1} d_j\ \text{is odd}}\right)$ . However, for large n the contribution of the added indicator function is negligible with probability one (see, e.g., [Reference Van der Hofstad47, Section 7.6, p. 239]), and we will thus ignore it in our asymptotic calculations.

Additionally, we assume the first three moments of the degree distribution are finite. Note that, by matching half-edges uniformly at random, we obtain a multigraph, because the resulting graph may have self-loops and multiple edges. Interestingly, when the degrees $d_1, d_2, \ldots, d_n$ are drawn independently, [Reference Durrett23, Theorem 3.1.2] states that as the number of vertices grows to infinity, the numbers of self-loops and parallel edges have independent Poisson limits whose means depend only on the first two moments of the degree distribution. Since the focus of this paper is on the functional limit of the fluctuations of the scaled stochastic process $n^{-1}X$ , the contributions of self-loops and parallel edges are negligible in the limit. Therefore, we will ignore self-loops and parallels edges in our calculations of the asymptotic terms.

Let us denote the probability generating function of the underlying degree distribution by $\psi$ , i.e.,

(2.1) \begin{equation}\psi(x) \,:\!=\, \sum_{k} x^k p_k ,\end{equation}

where $p_k$ is the probability that a randomly chosen vertex has degree k, for $k \in \mathbb{N}_0$ . We denote the class of all CM random graphs with n vertices by $\mathcal{G}(\psi,n)$ .

A half-edge is referred to as SI-type (resp., IS-type) if it originates at a susceptible (resp., infected) vertex and is a part of an SI-type edge. Similarly, an SS-type half-edge is a part of an SS-type edge and an II-type half-edge is a part of an II-type edge (connecting two infected individuals).

We consider the Markovian SI model on CM random graphs. Each infected individual (represented by a vertex of the graph) infects one of its neighbours at rate $\beta >0$ , independently of the other neighbours. We split the population into two compartments consisting respectively of the susceptible and the infected individuals. In order to prove the FCLT result outlined in the introduction, we need to approximate the probability distributions of the counts $X_{{S}}$ , $X_{{SI}}$ , and $X_{{SS}}$ , which requires us to calculate the probability that a susceptible vertex of degree k has l infected neighbours, for $l\le k$ . As we explain below, obtaining this probability is particularly easy if we allow the graph to be constructed dynamically as the infection spreads. Consequently, we adopt the following dynamic construction of the graph first proposed in [Reference Decreusefond, Dhersin, Moyal and Tran21].

Dynamic construction of the graph. Suppose we are given n vertices with degrees (or numbers of half-edges) $d_1, d_2, \ldots, d_n$ . A subset of size $X_{{S}}(0)$ of n vertices is chosen uniformly at random. Those vertices are designated as susceptible, and the remaining vertices as infected. Note that since we can write

\begin{equation*}X_{{SI}}(t) = \sum_{i\in I(t)} X_{{IS},i}(t) , \end{equation*}

where $X_{{IS},i}(t)$ denotes the number of IS-type half-edges originating at an infected vertex i at time t, it suffices to follow the infected vertices in the dynamic construction.

We start at time $t=0$ by infecting a random subset of vertices and revealing their connections by matching their half-edges uniformly at random with the available half-edges (see below). We then associate with each IS-type half-edge an independent exponential clock with parameter $\beta$ . The first of all these clocks that rings determines the next event. Therefore, at time t we know that the next infection will take place in a time exponentially distributed with parameter $\beta X_{{SI}}(t)$ . Let $t^\ast>t$ denote the time of the next infection, with its left limit denoted by $t^\ast\!\!-$ . At $t^\ast$ , we update the state of the epidemic as follows.

1. Step 1. We randomly match the IS-type half-edge that has rung to a half-edge originating from a susceptible vertex. This susceptible vertex is newly infected with degree, say, k.

2. Step 2. We choose uniformly $k - 1$ half-edges among all the available half-edges (they are either of type IS or of type SS). Let $n_{{IS}}$ (resp., $n_{{SS}}$ ) be the number of IS-type (resp., of SS-type) half-edges drawn among these $k - 1$ half-edges. Note that the probability of drawing a specific pair $(n_{{IS}},n_{{SS}})$ is given by the hypergeometric distribution

   \begin{equation*}\frac{\binom{X_{{SI}}(t^\ast\!\!-)}{n_{{IS}}}\binom{X_{{SS}}(t^\ast\!\!-)}{n_{{SS}}}}{\binom{X_{{S}\bullet}(t^\ast\!\!-)}{k-1}}.\end{equation*}
   The chosen $n_{{IS}}$ half-edges of type IS determine the infected neighbours of the newly infected individual. The remaining $n_{{SS}}$ edges of type SS remain open in the sense that the susceptible neighbour is not fixed.

3. Step 3. We change the status of the $n_{{IS}}$ (resp., $n_{{SS}}$ ) IS-type (resp., SS-type) edges created to II-type (resp., SI-type).

4. Step 4. We change the status of the newly infected from S to I and wait for the next clock to ring at a new time $t^{\ast\ast}>t^\ast$ to repeat Steps 1–4. The process stops when there are no more IS-type half-edges.

The above algorithm (see Figure 1 for a pictorial representation) gives rise to the natural filtration $\mathcal{F}_{t}$ as the $\sigma$ -field generated by the process history up to and including time $t>0$ [Reference Durrett22, Chapter 1, p. 14]. The filtration $\mathcal{F}_{t}$ includes information about the status of all vertices (susceptible or infected), and all paired and unpaired half-edges. To be precise, we define

\begin{align} \mathcal{F}_{t} \,:\!=\, \sigma\!\left(\{S(s), I(s), \{X_{{IS},i}, X_{{II},i}\}_{i \in I(s)} \mid s \le t \}\right) . \nonumber\end{align}

We let $\mathcal{F}_{0}$ contain all $\mathbb{P}$ -null sets in $\mathcal{F}$ . We include all $\mathbb{P}$ -null sets in $\mathcal{F}_{0}$ so that the filtration family $\{\mathcal{F}_{t} \}$ is complete. It is also right continuous (i.e., $\mathcal{F}_{t+}=\mathcal{F}_{t}$ for every $t\geq 0$ , where $\mathcal{F}_{t+} \,:\!=\, \cap_{s >0} \mathcal{F}_{t+s}$ is the $\sigma$ -field of events immediately after t), because it is generated by a right continuous jump process [Reference Andersen, Borgan, Gill and Keiding1, Chapter II, p. 61]. Therefore, the usual Dellacherie conditions on $\{\mathcal{F}_{t} \}$ are satisfied [Reference Rebolledo44, Reference Karatzas and Shreve33, Reference Fleming and Harrington25]. We denote the $\sigma$ -field of events strictly prior to $t \in \mathbb{R}_{+}$ by $\mathcal{F}_{t-}$ and write $\mathcal{F}_{0-} \,:\!=\, \mathcal{F}_{0}$ , by convention.

Figure 1.

Dynamics of the stochastic SI model over a finite time interval $\mathcal{T}_{0}$ . Susceptible vertices are shown in yellowish green and infected vertices in dark red. Different types of edges are shown in different colours. (a) State of the system at a given time. We know the degree of each vertex. For each infected vertex, we know the number of infected neighbours it has (the number of ${II}$ -type edges, which are shown in solid red) and the number of ${IS}$ -type half-edges emanating from it, which are shown in dashed blue. The green dotted half-edges emanating from the susceptible vertices are of undetermined types. (b) An ${IS}$ -type half-edge rings and is randomly matched with a half-edge originating from a susceptible vertex. A full edge is thus formed. (c) We change the status of the chosen susceptible vertex to infected (and change its colour to dark red). (d) We determine the types of the remaining half-edges of the newly infected vertex.

Denote the collection of vertices of degree k that remain susceptible at time t by $S_k(t)$ . Recall that $X(t) \,:\!=\, \big( X_{{S}}(t), X_{{SI}}(t), X_{{SS}}(t) \big)$ denotes the aggregated state vector of the system at time $t \ge 0$ . Note that, since we may calculate $X_{{SS}}(t)$ if we know $X_{{SI}}(t)$ and $X_{{II}}(t)$ , the process X is adapted to $\mathcal{F}_{t}$ . However, the process X itself is not necessarily Markovian. Let $\tilde{X} \,:\!=\, (X_{{SI},i}, X_{{SS},i})_{i \in S} $ . By the Doob–Meyer decomposition theorem [Reference Meyer36], we decompose X as

(2.2) \begin{align}X(t) = X(0)+ \int_{0}^{t} \mathbb{F}_{{X}} \!\left({\tilde{X}(s)} \right) \, {d} {s} + M^{\prime}(t) ,\end{align}

where $M^{\prime}(t) \,:\!=\, ( M^{\prime}_{{S}}(t), M^{\prime}_{{SI}}(t), M^{\prime}_{{SS}}(t)) $ is a zero-mean martingale adapted to the filtration $\mathcal{F}_{t}$ , and $\mathbb{F}_{{X}} \big({\tilde{X}} \big) \,:\!=\, \big(\mathbb{F}_{{{S}}} \big({\tilde{X}} \big) , \mathbb{F}_{{{SI}}} \big({\tilde{X}} \big), \mathbb{F}_{{{SS}}} \big({\tilde{X}} \big) \big)$ is an integrable function given by

(2.3) \begin{align}\begin{aligned}\mathbb{F}_{{{S}}} \!\left({\tilde{x}} \right) & \,:\!=\, -\beta x_{{SI}} , \\\mathbb{F}_{{{SI}}} \!\left({\tilde{x}} \right) & \,:\!=\, \sum_{i \in S} \beta x_{{SI},i} \big(x_{{SS},i}- x_{{SI},i}\big) , \\\mathbb{F}_{{{SS}}} \!\left({\tilde{x}} \right) & \,:\!=\, -2 \sum_{i \in S} \beta x_{{SI},i} x_{{SS},i} ,\end{aligned}\end{align}

for $\tilde{x}\,:\!=\, (x_{{SI},i}, x_{{SS},i})_{i \in S}$ and $x_{{SI}} \,:\!=\, \sum_{i \in S} x_{{SI},i}, x_{{SS}} \,:\!=\, \sum_{i \in S} x_{{SS},i}$ . The first equation follows from the fact that the number of susceptible vertices decreases by 1 at rate $\beta X_{{SI}}$ because of the Markovian assumption on the SI process and the independence of the infection transmissions along the edges. Similarly, when a susceptible vertex i gets infected, which happens at rate $\beta X_{{SI},i}$ (again because of the independence of infection transmissions along each of its $X_{{SI},i}$ infectious edges), the SI edges connected to that susceptible vertex turn into II-type edges, whereas its SS-type edges turn into SI-type edges. Therefore, the net change in the total count of SI-edges is $\big(X_{{SS},i} - X_{{SI},i}\big)$ whenever a susceptible vertex i gets infected. Because of the independence assumption, we sum over all susceptible vertices to arrive at the second equation. See Figure 2 for a visualization. The third equation can be explained similarly by computing the rates and the corresponding net changes in the total count of SS-edges when a susceptible vertex gets infected.

Figure 2.

Change to the edge counts. When a susceptible vertex i gets infected (turns red from green; see Step 2 of the dynamic construction), the SI edges attached to that vertex turns into II edges, whereas SS edges become new SI edges. This visualization is helpful in understanding the Doob–Meyer decomposition in Equation (2.2).

We note that as a consequence of the uniformly-at-random matching of half edges in the dynamic construction, similarly to Step 2, we obtain also the following hypergeometric distribution (see also [Reference Jacobsen, Burch, Tien and Rempała30]) for the number of infected and susceptible neighbours of a susceptible vertex of degree k at time t.

Lemma 1. For $k \in \mathbb{N}_0$ and $i \in S_k(t)$ , conditionally on the process history until time t, the vector $(X_{{SI},i}(t), X_{{SS},i}(t))$ follows the hypergeometric distribution

(2.4) \begin{align}\mathbb{P}\!\left({X_{{SI},i}(t)= n_{{SI}}, X_{{SS},i}(t)= n_{{SS}} \mid \mathcal{F}_{t}}\right) ={}& \frac{\binom{X_{{SI}}(t)}{n_{{SI}}} \binom{X_{{SS}}(t)}{n_{{SS}}}}{\binom{X_{{S} \bullet}(t)}{k}} , \end{align}

supported on $n_{{SI}}+ n_{{SS}}= k$ , where $n_{{SI}},n_{{SS}} \in \mathbb{N}_0$ .

Proof. Consider $X_{SI}(t)$ , the number of half-edges of type IS emanating from the set of infected vertices. By construction, they all connect to the susceptible vertices uniformly at random. Thus the probability that $n_{{SI}}$ of them connect to a given vertex $i\in S_k$ when a total of $X_{{S} \bullet}(t)$ half-edges are available to choose from is

\begin{equation*} \frac{\binom{k} {n_{SI}} \binom{X_{{S} \bullet}(t)-k}{{X_{SI}(t)}-n_{SI}}}{\binom{X_{{S} \bullet}(t)}{X_{SI}(t)}},\end{equation*}

which works out to be the same as the hypergeometric probability (2.4).

Since we partition the collection of susceptible vertices S(t) by their degree $k \in \mathbb{N}_0$ , we have $S(t) = \cup_k S_k(t)$ . Therefore, $X_{{S}}(t) = \sum_k X_{S_k}(t)$ , where $X_{S_k}(t)$ is the size of $S_k(t)$ . Note that $X_{{S}\bullet}(t) = \sum_{k} k X_{S_k}(t)$ . To study the large graph limit of the system, we also define the quantity

(2.5) \begin{align}\theta(t) \,:\!=\, {}& \exp \biggl({-\beta \int_{0}^{t} \frac{X_{{SI}}(s)}{X_{{S}\bullet}(s)} \, {d} {s}} \biggr),\end{align}

which can be intuitively described as the probability that a degree-1 vertex that was susceptible at time zero remains susceptible till time $t >0$ ([Reference Volz48, Reference Miller37, Reference Miller, Slim and Volz38]). It may be described equivalently as

\begin{align}\theta(t) = \theta(0) + \int_{0}^{t} \mathbb{F}_{{0}} \!\left({X_{{SI}}(s),X_{{S}\bullet}(s), \theta(s)} \right) \, {d} {s} , \nonumber\end{align}

where $\theta(0) =1$ and $\mathbb{F}_{{0}} \!\left({X_{{SI}},X_{{S}\bullet}, \theta} \right) \,:\!=\, - \beta \theta \dfrac{X_{{SI}}}{X_{{S}\bullet}}$ .

4.1. Deterministic limit of $ \left\langle {\textbf{M}} \right\rangle \textbf{(t)}$

Recall that $(x, \vartheta) \,:\!=\, ( (x_{{S}}, x_{{SI}}, x_{{SS}}), \vartheta )$ . Let us begin by defining the following operators acting on the function $(x, \vartheta) $ :

(4.4) \begin{align} v_{{S}} & \,:\!=\, \beta x_{{SI}} , \nonumber\\ v_{{SI}} & \,:\!=\, \beta \!\left( \frac{x_{{SI}} (x_{{SS}}-x_{{SI}} )^2}{x_{{S}}^2} \mathbb{D}^{3} {\psi(\vartheta )} - \frac{x_{{SI}} (x_{{SS}}-3x_{{SI}} )}{x_{{S}}} \mathbb{D}^{2} {\psi(\vartheta)} + x_{{SI}} \right) , \nonumber \\ v_{{SS}} & \,:\!=\, 4 \beta \frac{x_{{SI}} x_{{SS}}}{x_{{S}}} \!\left( \frac{x_{{SS}}}{x_{{S}}} \mathbb{D}^{3} {\psi(\vartheta )} + \mathbb{D}^{2} {\psi(\vartheta)} \right) , \nonumber\\ v_{{S} , {SI}} & \,:\!=\, - \beta \!\left(\frac{x_{{SI}} ( x_{{SS}} - x_{{SI}})}{x_{{S}}} \mathbb{D}^{2} {\psi(\vartheta )}- x_{{SI}} \right) , \\ v_{{S} , {SS}} & \,:\!=\, 2\beta \frac{x_{{SI}} x_{{SS}}}{x_{{S}}} \mathbb{D}^{2}{\psi(\vartheta )} , \nonumber\\ v_{{SI}, {SS}} & \,:\!=\, -2 \beta \frac{x_{{SI}}x_{{SS}} (x_{{SS}}- x_{{SI}})}{x_{{S}}^2} \mathbb{D}^{3} {\psi(\vartheta )} . \nonumber \end{align}

The intuition behind the operators in Equation (4.4) will be clear when we compute the predictable quadratic variation $ \left\langle {M} \right\rangle $ of the martingale process M and seek its limit as $n \rightarrow \infty$ . In particular, we shall see that each of the terms on the right-hand side of Equation (4.4) is a function of various multinomial moments, which we find as limits of the corresponding hypergeometric ones in order to approximate the expected jump sizes conditional on the process history.

Now, define a $\mathcal{T}$ -indexed family of matrices $\{V(t) \}$ as follows

(4.5) \begin{align} V(t) \,:\!=\, & \begin{pmatrix} V_{{S}}(t) & \quad V_{{S} , {SI}} (t) & \quad V_{{S} ,{SS}}(t) \\[4pt] V_{{SI} ,{S}}(t) & \quad V_{{SI}}(t) & \quad V_{{SI} , {SS}} (t) \\[4pt] V_{{SS}, {S}}(t) & \quad V_{{SS} , {SI}}(t) & \quad V_{{SS}}(t) \\ \end{pmatrix} , \end{align}

where, given $ v_{id_1,id_2}( x,\vartheta )\ \text{for}\ id_1,id_2 \in \{{S}, {SI}, {SS} \} $ in Equation (4.4),

(4.6) \begin{align} V_{id_1, id_2} (t) \,:\!=\, {}& \int_{0}^{t} v_{id_1,id_2}( x(s),\vartheta(s) ) \, {d} {s} , \end{align}

with the convention $ v_{id_1,id_2} \,:\!=\, v_{id_2,id_1}\ \text{for}\ id_1,id_2 \in \{{S}, {SI}, {SS} \} $ and $ v_{id_1,id_2} \,:\!=\, v_{id_1} $ whenever $ id_1= id_2 \in \{{S}, {SI}, {SS} \} $ . Note that this also sets the convention $ V_{id_1,id_2}(t ) \,:\!=\, V_{id_2,id_1}( t)\ \text{for}\ id_1,id_2 \in \{{S}, {SI}, {SS} \} $ and $ V_{id_1,id_2}( t ) \,:\!=\, V_{id_1}( t ) $ whenever $ id_1= id_2 \in \{{S}, {SI}, {SS} \} $ for each $t \in \mathcal{T}$ .

Let us now present our first result providing the deterministic limit of $ \left\langle {M} \right\rangle $ in the following lemma. Recall that proving a deterministic limit of $ \left\langle {M} \right\rangle $ will satisfy one of the conditions of the Rebolledo theorem. The key strategy in establishing the result will be to approximate various hypergeometric moments by the corresponding multinomial ones.

Lemma 2. Consider the stochastic SI model described in Section 2.2. Assume A1, A2, and A3 for a CM graph $\mathcal{G}(\psi, n)$ . Then

\begin{align} \left\langle {M} \right\rangle (t) {\xrightarrow[]{ {P}}}& V(t) , \nonumber \end{align}

for each $t \in \mathcal{T}$ , as $ n \rightarrow \infty$ , where V(t) is as defined in Equation (4.5), and $ (x, \vartheta) $ is the solution of Equation (3.8) with $x (0) = \alpha $ and $\vartheta (0)=1$ .

Proof of Lemma 2. To show convergence of the matrix random process $ \left\langle {M} \right\rangle (t) $ to V(t), we show componentwise convergence of the respective components. The general strategy for proving convergence for these components remains the same. To conserve space, we only demonstrate here the strategy for establishing $M_{{SI}}(t) \xrightarrow[]{ {P}} V_{{SI}}(t) $ . The remaining assertions follow similarly.

Computation of $ \left\langle {\textbf{M}_{\textbf{SI}}} \right\rangle $ . The process $M_{{SI}}$ jumps only if a susceptible vertex gets infected. Therefore, the predictable quadratic variation is computed as follows:

\begin{align*} \left\langle {M_{{SI}}} \right\rangle (t) = \left\langle {n^{-1/2} M^{\prime}_{{SI}}} \right\rangle (t) = & \int_{0}^{t} \sum_k \frac{1}{n} \sum_{i \in S_k} \beta X_{{SI},i} \big(X_{{SS},i}- X_{{SI},i} \big)^2 \, {d} {s} .\end{align*}

Now, for a randomly selected $i \in S_k$ , we seek the (conditional) moments $\mathbb{E}\!\left[{X_{{SI},i} \big(X_{{SS},i}- X_{{SI},i} \big)^2 \big| \mathcal{F}_{t-}}\right]$ . Define the function $C_{h}^k \,:\,\mathcal{T}_{0} \rightarrow \mathbb{R} $ as

\begin{align*} C_{h}^k(t) \,:\!=\, & \mathbb{E}\big[{X_{{SI},i}(t) (X_{{SS},i}(t) - X_{{SI},i}(t) )^2 \big| \mathcal{F}_{t-}}\big] . \end{align*}

Following the computations in Appendix A, we get

\begin{align*} C_{h}^k(t) = & \frac{ ( k)_{3} X_{{SI}}}{( {X_{{S} \bullet}})_{3}} \left[ ( {X_{{SS}}})_{2} - 2 (X_{{SI}}-1 )X_{{SS}} + ( {X_{{SI}}-1})_{2} \right] \\[5pt] & - \frac{ ( k)_{2} X_{{SI}}}{( {X_{{S} \bullet}})_{2}} [ X_{{SS}} - 3(X_{{SI}}-1) ] + k \frac{X_{{SI}}}{X_{{S} \bullet}} . \end{align*}

To be precise, the processes on the right-hand side of the above equation are evaluated at $t-$ . To approximate the hypergeometric moments by corresponding multinomial ones, define the multinomial compensator $C_{m}^k \,:\, \mathcal{T}_{0} \times [\xi, \partial \psi(1)] \rightarrow \mathbb{R} $ as

\begin{align*}C_{m}^k (t,z) & \,:\!=\, \frac{ ( k)_{3} n^{-3} X_{{SI}}}{z^{3}} \big( {X_{{SS}}}^{2} - 2 X_{{SI}}X_{{SS}} + X_{{SI}}^2 \big) \\& \quad - \frac{ ( k)_{2} n^{-2} X_{{SI}}}{z^{2}} ( X_{{SS}} - 3X_{{SI}} )+ \frac{k n^{-1} X_{{SI}}}{z} \\& = \frac{ ( k)_{3} n^{-3} X_{{SI}} ( X_{{SS}}- X_{{SI}} ) ^2}{z^{3}} - \frac{ ( k)_{2} n^{-2} X_{{SI}} ( X_{{SS}} - 3X_{{SI}} )}{z^{2}} + \frac{k n^{-1} X_{{SI}}}{z} .\end{align*}

Again, to be precise, the processes on the right-hand side of the above equation are evaluated at $t-$ . Observe that there exists an $L >0$ such that

(4.7) \begin{align}C_{m}^k (t,z(t) ) \leq L k^3 ,\end{align}

uniformly in n. This holds because $n^{-1}X_{{SI}}$ and $n^{-1}X_{{SS}}$ are uniformly bounded above by virtue of Remark 1 and z is bounded away from zero, by definition. The function $C_{m}^k (t,z(t) ) $ is also Lipschitz continuous in z. Now recall the definition of $v_{{SI}}$ from Equation (4.4) and define

\begin{align*} \Delta(t) & \,:\!=\, \sum_k \frac{1}{n} \sum_{i \in S_k} \beta X_{{SI},i}(t) \big(X_{{SS},i}(t) - X_{{SI},i} (t) \big)^2 - v_{{SI}}(x(t), \vartheta(t) ) \\ & = \sum_k \frac{1}{n} \sum_{i \in S_k} \beta X_{{SI},i}(t) \big(X_{{SS},i}(t)- X_{{SI},i}(t) \big)^2 -v_{{SI}}\big( n^{-1}X(t), \theta(t) \big) \\ & \quad +v_{{SI}}( n^{-1}X(t) , \theta (t) ) - v_{{SI}}(x(t), \vartheta(t) ) \\ & = \Delta_{1}(t) + \Delta_{2}(t) , \end{align*}

where

\begin{equation*} \Delta_{1}(t) \,:\!=\, \sum_k \frac{1}{n} \sum_{i \in S_k} \beta X_{{SI},i}(t) (X_{{SS},i}(t) - X_{{SI},i}(t) )^2 -v_{{SI}}\big( n^{-1}X(t), \theta(t) \big),\end{equation*}

and $ \Delta_{2}(t) \,:\!=\, v_{{SI}}( n^{-1}X(t) , \theta(t) ) - v_{{SI}}(x(t), \vartheta(t) ) $ . To show $ \left\langle {M_{{SI}}} \right\rangle \xrightarrow[]{ {P}} V_{{SI}} $ , it suffices to show $ \sup_{t \in \mathcal{T}} | \Delta(t) | \xrightarrow[]{ {P}} 0$ . We achieve this by separately showing $ \sup_{t \in \mathcal{T}} | \Delta_{1}(t) | \xrightarrow[]{ {P}} 0 $ and $\sup_{t \in \mathcal{T}} | \Delta_{2}(t) | \xrightarrow[]{ {P}} 0$ .

Convergence of $\Delta_{1}(t)$ . Observe that

\begin{align*} \Delta_{1}(t) = & \sum_k \frac{1}{n} \sum_{i \in S_k} \beta X_{{SI},i} \big(X_{{SS},i}- X_{{SI},i} \big)^2 - \beta \!\left[ \frac{n^{-3} X_{{SI}} (X_{{SS}}-X_{{SI}} )^2}{\alpha_{{S}}^2} \frac{\partial^3 \psi(\theta )}{( \partial \psi(\theta ))^3} \right. \\ & {} \left. - \frac{n^{-2} X_{{SI}} (X_{{SS}}-3X_{{SI}} )}{\alpha_{{S}}} \frac{\partial^2 \psi(\theta )}{( \partial \psi(\theta ))^2} + n^{-1} X_{{SI}} \right] \\ = & \sum_k \!\left[ \frac{1}{n} \sum_{i \in S_k} \beta X_{{SI},i} \big(X_{{SS},i}- X_{{SI},i} \big)^2 - \beta \!\left\{\frac{n^{-3} X_{{SI}} (X_{{SS}}-X_{{SI}} )^2}{\alpha_{{S}}^2} \frac{ ( k)_{3} \theta^k p_k}{(\theta \partial \psi(\theta) )^3} \right. \right. \\ & \left. \left. {} - \frac{n^{-2} X_{{SI}} (X_{{SS}}-3X_{{SI}} )}{\alpha_{{S}}} \frac{ ( k)_{2} \theta^k p_k}{(\theta \partial \psi(\theta) )^2} + n^{-1} X_{{SI}} \frac{k \theta p_k}{\theta \partial \psi(\theta)} \right\} \right] \\ = & \sum_k \!\left[ \frac{1}{n} \sum_{i \in S_k} \beta X_{{SI},i} \big(X_{{SS},i}- X_{{SI},i} \big)^2 - \beta \alpha_{{S}} p_k \theta^k C_{m}^k (t, \alpha_{{S}} \theta \partial \psi(\theta) ) \right] . \end{align*}

The second equality follows from expressing the derivatives of the probability generating functions as sums over all possible degrees k and then collecting terms involving degree k. Define

\begin{equation*} \Delta_{1}^{(k)}(t) \,:\!=\, \frac{1}{n} \sum_{i \in S_k} \beta X_{{SI},i} \big(X_{{SS},i}- X_{{SI},i} \big)^2 - \beta \alpha_{{S}} p_k \theta^k C_{m}^k (t, \alpha_{{S}} \theta \partial \psi(\theta) ).\end{equation*}

Our task boils down to showing that $ \sup_{t \in \mathcal{T}} \!\left| \sum_k \Delta_{1}^{(k)}(t) \right| \xrightarrow[]{ {P}} 0 $ as $n \rightarrow \infty$ . We achieve this in two steps. First we show that the tails of $\sum_k \Delta_{1}^{(k)}(t) $ are negligible. Second, we show that each term $ \Delta_{1}^{(k)}(t)$ converges to zero uniformly in probability for a fixed $k \in \mathbb{N}$ .

Step I: Tails are negligible. Let us begin by showing that as $N \rightarrow \infty$ ,

\begin{align*} \sup_{n \in \mathbb{N}} \sup_{t \in \mathcal{T}} \!\left| \sum_{k > N} \Delta_{1}^{(k)}(t) \right| \xrightarrow[]{ {P}} 0 . \end{align*}

Observe that, for sufficiently large n,

(4.8) \begin{align} \left| \frac{1}{n} \sum_{k > N} \sum_{i \in S_k} \beta X_{{SI},i} \big(X_{{SS},i}- X_{{SI},i} \big)^2 \right| \leq {} \frac{\beta}{n} \sum_{k > N} k^3 X_{S_k} \leq {} 2 \beta \sum_{k > N} k^3 p_k , \end{align}

because $ n^{-1} X_{S_k} \leq 2p_k $ for sufficiently large n in light of Remark 1. Following Remark 1 and the bound on $C_m^k$ from Equation (4.7), we get

(4.9) \begin{align} \left| \sum_{k > N} \beta \alpha_{{S}} p_k \theta^k C_{m}^k (t, \alpha_{{S}} \theta \partial \psi(\theta) ) \right| \leq {}& \beta L \sum_{k> N} k^3 p_k . \end{align}

Therefore, we get $ \sup_{n \in \mathbb{N}} \sup_{t \in \mathcal{T}} \Big| \sum_{k > N} \Delta_{1}^{(k)}(t) \Big| \xrightarrow[]{ {P}} 0 $ by combining the inequalities (4.8) and (4.9), in view of A3.

Step II: Uniform convergence in probability for a fixed k. In addition to Step I, it is sufficient to show $\sup_{t \in \mathcal{T}} | \Delta_{1}^{(k)}(t) | \xrightarrow[]{ {P}} 0 $ for an arbitrarily fixed $k \in \mathbb{N}$ to justify $ \sup_{t \in \mathcal{T}} | \Delta_{1}^{}(t) | \xrightarrow[]{ {P}} 0 $ . Observe that

(4.10) \begin{align} | \Delta_{1}^{(k)}(t) | = & \Bigg| \frac{1}{n} \sum_{i \in S_k} \beta X_{{SI},i} \big(X_{{SS},i}- X_{{SI},i} \big)^2 - \beta \alpha_{{S}} p_k \theta^k C_{m}^k (t, \alpha_{{S}} \theta \partial \psi(\theta) ) \Bigg| \nonumber \\ \leq\, & \beta n^{-1} \Bigg| \sum_{i \in S_k} X_{{SI},i} \big(X_{{SS},i}- X_{{SI},i} \big)^2 - X_{S_k} C_h^k(t) \Bigg| \end{align}

(4.11) \begin{align} & + \beta n^{-1} X_{S_k} \big| C_h^k(t) - C_{m}^k \big(t, n^{-1} X_{{S} \bullet} \big) \big| \end{align}

(4.12) \begin{align} & + \beta \big| n^{-1} X_{S_k} C_{m}^k \big(t, n^{-1} X_{{S} \bullet} \big) - \alpha_{{S}} p_k \theta^k C_{m}^k \big(t, n^{-1} X_{{S} \bullet} \big) \big| \end{align}

(4.13) \begin{align} & + \beta \alpha_{{S}} p_k \theta^k \big| C_{m}^k \big(t, n^{-1} X_{{S} \bullet} \big) - C_{m}^k (t, \alpha_{{S}} \theta \partial \psi(\theta) ) \big| .\end{align}

We show that each of the above summands converges uniformly in probability to zero.

Define the process $ \Delta_{1,1}^{(k)}(t) \,:\!=\, \sum_{i \in S_k} X_{{SI},i} \big(X_{{SS},i}- X_{{SI},i} \big)^2 - X_{S_k} C_h^k(t) $ . Observe that $ \Delta_{1,1}^{(k)}(t)$ is a zero-mean, piecewise constant, càdlàg martingale with paths in D. The jumps of $ \Delta_{1,1}^{(k)}(t) $ take place when a vertex of degree k gets infected. The quadratic variation of $ \Delta_{1,1}^{(k)}(t) $ is therefore the sum of its squared jumps,

\begin{align*} \Big[ {\Delta_{1,1}^{(k)}} \Big] (t) = & \sum_{s \leq t}\! \Big(\delta \Delta_{1,1}^{(k)}(s) \Big)^2 \leq k^6 n , \end{align*}

because the number of jumps cannot exceed n. Therefore, by Doob’s martingale inequality we get $\sup_{t \in \mathcal{T}} \big| n^{-1} \Delta_{1,1}^{(k)}(t) \big| \xrightarrow[]{ {P}} 0 $ , since

\begin{equation*}\mathbb{E}\!\left[{ \left[ {\Delta_{1,1}^{(k)}} \right] (t)}\right] = \mathbb{E}\!\left[{\Big(\Delta_{1,1}^{(k)}(t) \Big)^2}\right] = \mathop{}\!O{\left({n}\right)}.\end{equation*}

That is, the quantity in (4.10) converges uniformly in probability to zero.

For the term in (4.11), take into account $ n^{-1}X_{S_k} \leq 1 $ and observe that

\begin{align*} \sup_{t \in \mathcal{T}} \big| C_h^k(t) - C_{m}^k \big(t, n^{-1} X_{{S} \bullet} \big) \big| \leq {}& \frac{c_1 k^3}{X_{S \bullet}(T) -2} ,\end{align*}

for some $c_1>0$ , because $ X_{{S} \bullet} $ is non-increasing on $\mathcal{T}_{0} $ . Therefore, by A1, the quantity in (4.11) converges to zero uniformly in probability.

Now observe that

\begin{align*} \sup_{t \in \mathcal{T}} \big| n^{-1} X_{S_k} C_{m}^k \big(t, n^{-1} X_{{S} \bullet} \big) - \alpha_{{S}} p_k \theta^k C_{m}^k \big(t, n^{-1} X_{{S} \bullet} \big) \big| \\ \leq L k^3 \sup_{t \in \mathcal{T}} \big| n^{-1} X_{S_k} -\alpha_{{S}} p_k \theta^k \big| & \xrightarrow[]{ {P}} 0 , \end{align*}

by virtue of the bound on $C_m^k$ in Equation (4.7) and [Reference Jacobsen, Burch, Tien and Rempała30, Lemma 1(a)]. Therefore, the term in (4.12) also converges to zero uniformly in probability.

Finally, by virtue of the Lipschitz continuity of $C_m^k(t,z)$ in z, we get

\begin{align*} \sup_{t \in \mathcal{T}} \big| C_{m}^k \big(t, n^{-1} X_{{S} \bullet} \big) - C_{m}^k (t, \alpha_{{S}} \theta \partial \psi(\theta) ) \big| \leq\ & c_2 \sup_{t \in \mathcal{T}} \big| n^{-1} X_{{S} \bullet} - \alpha_{{S}} \theta \partial \psi(\theta) \big| , \end{align*}

for some $c_2 >0$ . Because $ \sup_{t \in \mathcal{T}} \big| n^{-1} X_{{S} \bullet} - \alpha_{{S}} \theta \partial \psi(\theta) \big| \xrightarrow[]{ {P}} 0 $ as shown in [Reference Jacobsen, Burch, Tien and Rempała30], we conclude that the term in (4.13) converges to zero uniformly in probability.

Having shown that the terms in (4.10), (4.11), (4.12), and (4.13) converge to zero uniformly in probability, we establish that $\sup_{t \in \mathcal{T}} \big| \Delta_{1}^{(k)}(t) \big| \xrightarrow[]{ {P}} 0 $ uniformly in probability for any fixed $k \in \mathbb{N}$ . Finally, by virtue of Step I and Step II, we obtain $ \sup_{t \in \mathcal{T}} | \Delta_{1}(t) | \xrightarrow[]{ {P}} 0 $ .

Convergence of $ \Delta_{2}(t)$ . Note that $ v_{{SI}}( n^{-1}X, \theta ) $ is Lipschitz continuous on its domain, which we can take as $ (0,1] \times [\xi, \partial \psi(1)]^2 \times [\xi,1] $ , by Remark 1. Therefore,

\begin{align*} \sup_{t \in \mathcal{T}} \big| v_{{SI}}( n^{-1}X , \theta ) - v_{{SI}}(x, \vartheta ) \big| \leq {} c_3 \sup_{t \in \mathcal{T}} \big\lVert{(n^{-1}X, \theta )- (x, \vartheta )}\big\rVert , \end{align*}

for some Lipschitz constant $c_3>0$ . Since $ (x, \vartheta) $ is the solution of Equation (3.8) with initial condition $x (0) = \alpha $ and $\vartheta (0)=1$ , by virtue of Theorem 1 we obtain $ \sup_{t \in \mathcal{T}} | \Delta_{2}(t) | \xrightarrow[]{ {P}} 0$ .

Final conclusion. Since $ \sup_{t \in \mathcal{T}} | \Delta_{1}(t) | \xrightarrow[]{ {P}} 0$ and $ \sup_{t \in \mathcal{T}} | \Delta_{2}(t) | \xrightarrow[]{ {P}} 0$ , we conclude $ \sup_{t \in \mathcal{T}} | \Delta(t) | \xrightarrow[]{ {P}} 0$ , which is a sufficient condition for

\begin{align*} \left\langle {M_{{SI}}} \right\rangle (t) \xrightarrow[]{ {P}} V_{{SI}}(t)= {}& \int_{0}^{t} v_{{SI}}(x(s), \vartheta(s) ) \, {d} {s} .\end{align*}

We remark that the various moment estimates used in the proof above (and elsewhere in the paper) ignore the contributions of self-loops and parallel edges. Their contributions are asymptotically negligible as discussed earlier in Section 2.2. Also, note that we may need to add a parity edge to the last vertex if the sum of the drawn degrees is not even. This is relevant for the calculations in Steps I and II. However, as discussed earlier in Section 2.2, the contribution due to this minor adjustment is negligible and hence is not shown explicitly.

4.2. Asymptotic rarefaction of jumps

Recall that $M^\epsilon \,:\!=\, \big( M_{{S}}^\epsilon, M_{{SI}}^\epsilon, M_{{SS}}^\epsilon\big)$ is the vector of square-integrable martingales containing all jumps of components of M larger than $\epsilon$ in absolute value, for $\epsilon>0$ ; i.e., $ M_{id}(t) - M_{id}^\epsilon(t) $ is a locally square-integrable martingale and $| \delta M_{id}(t) - \delta M_{id}^\epsilon(t) | \leq \epsilon $ for all ${id} \in \{{S}, {SI}, {SS} \}$ and $ t \in \mathcal{T} $ . We wish to show $ \left\langle {M_{id}^\epsilon} \right\rangle (t) \xrightarrow[]{ {P}} 0$ for all ${id} \in \{{S}, {SI}, {SS} \}$ and $t \in \mathcal{T} $ , as $n \rightarrow \infty$ . We would like to point out that this condition is essentially the strong asymptotic rarefaction of jumps condition of the second type (strong ARJ(2)) as described in [Reference Rebolledo44, Reference Andersen, Borgan, Gill and Keiding1]. Intuitively this ensures that the sample paths of the martingale M(t) are close to continuous in the limit. Before proceeding further, we offer the following remark.

Lemma 3. For the CM graph $\mathcal{G}(\psi, n)$ along with A3, the following holds true:

(4.14) \begin{align}n^{- \frac{1}{2}}\ d_{{max}} \xrightarrow[]{ {a.s.}} 0 ,\end{align}

where $d_{{max}}$ is the maximum degree observed in a realization of $\mathcal{G}(\psi, n)$ .

Let us now compute the predictable quadratic variation of $M^\epsilon$ and establish its asymptotic limit.

Lemma 4. Consider the stochastic SI model described in Section 2.2. Assume A1, A2, and A3 for a CM graph $\mathcal{G}(\psi, n)$ . Consider the vector $M^\epsilon$ of square-integrable martingales containing all jumps of components of M(t) larger than $ \epsilon $ in absolute value for $\epsilon>0$ , as defined in Equation (4.2). Then, as $ n \rightarrow \infty$ , for all ${id} \in \{{S}, {SI}, {SS} \}$ , for each $t \in \mathcal{T}$ ,

(4.15) \begin{align} \left\langle {M^\epsilon_{id}} \right\rangle (t) \xrightarrow[]{ {P}} {}& 0 . \end{align}

Proof of Lemma 4. We proceed in the following two steps.

Computation of $ \left\langle {M_{{S}}^\epsilon} \right\rangle $ . Note that the original process $M^{\prime}_{{S}}$ makes only unit jumps. Then, for arbitrary $\epsilon >0 $ ,

\begin{align*} \left\langle {M_{{S}}^\epsilon} \right\rangle (t) \leq {}& \int_{0}^{t} \mathbb{E}\!\left[{\big(\delta M_{{S}}^\epsilon(s) \big)^2 \mathsf{1}\big({| \delta M^{\prime}_{{S}}(s) | > n^{1/2} \epsilon}\big) \big| \mathcal{F}_{s-}}\right] \, {d} {s} ={} 0 \quad \forall \, n > \frac{1}{\epsilon^2} \\ \implies {} \left\langle {M_{{S}}^\epsilon} \right\rangle (t) \xrightarrow[]{ {P}} & 0 \quad \text{for all}\ 0 < t \leq T\ \text{and for all}\ \epsilon> 0\ \text{as}\ n \rightarrow \infty .\end{align*}

Computation of $ \left\langle {M_{{SI}}^\epsilon} \right\rangle$ and $ \left\langle {M_{{SS}}^\epsilon} \right\rangle $ . Note that both $M^{\prime}_{{SI}}$ and $M^{\prime}_{{SS}}$ jump only if infection of a vertex occurs. This in particular implies that the jump sizes of $M^{\prime}_{{SI}}$ and $M^{\prime}_{{SS}}$ are bounded above by the degree of the vertex getting infected. Therefore, they are also bounded above by the maximum degree $d_{{max}}$ . For an arbitrary $\epsilon >0$ , and for ${id} \in \{{SI}, {SS} \}$ ,

\begin{align*} \left\langle {M_{id}^\epsilon} \right\rangle (t) & \leq \int_{0}^{t} \mathbb{E}\!\left[{(\delta M_{id}^\epsilon(s) )^2 \mathsf{1}\!\left({| n^{-1/2} d_{{max}} | > \epsilon}\right) \mid \mathcal{F}_{s-}}\right] \, {d} {s} \\ & \leq t n^{-1} d^2_{{max}} \mathsf{1}\!\left({| n^{-1/2} d_{{max}} | > \epsilon}\right) .\end{align*}

By Lemma 3, along with the continuous mapping theorem and the fact that almost sure convergence implies convergence in probability, we can claim that the right-hand side of the above inequality $t n^{-1} d^2_{{max}} \mathsf{1}\!\left({| n^{-1/2} d_{{max}} | > \epsilon}\right) \xrightarrow[]{ {P}} 0 $ for each $0 < t \leq T$ and $\epsilon >0$ . Therefore, for all $h >0$ ,

\begin{equation*}\mathbb{P}\!\left({ \left\langle {M_{id}^\epsilon} \right\rangle (t) > h} \right)\leq \mathbb{P}\!\left({t n^{-1} d^2_{{max}} \mathsf{1}\!\left({| n^{-1/2} d_{{max}} | > \epsilon}\right) > h}\right) \rightarrow 0 \end{equation*}

as $n \rightarrow \infty$ , establishing $ \left\langle {M_{id}^\epsilon} \right\rangle (t) \xrightarrow[]{ {P}} 0$ as $n \rightarrow \infty$ for all $0 < t \leq T$ and $\epsilon >0$ . This completes the proof.

4.3. Statement and proof of the FCLT

Having shown the convergence of all relevant quadratic variation processes, we are now ready to present the FCLT. First we state that the function V found in Lemma 2 is a positive semidefinite matrix-valued function on $\mathcal{T}$ , with positive semidefinite increments. Set $V(0) \,:\!=\, \boldsymbol{0}$ , the $3 \times 3$ null matrix, so that we can treat V(t) as a positive semidefinite matrix-valued function on the entirety of $\mathcal{T}_{0}$ . Let us denote by $\mathcal{V}$ the collection of all such positive semidefinite $3 \times 3$ matrix-valued functions on $\mathcal{T}_{0}$ that have positive semidefinite increments and that are $\boldsymbol{0}$ at time zero. Given such a matrix-valued function $V \in \mathcal{V} $ , let G be a continuous Gaussian vector martingale such that $ \left\langle {G} \right\rangle = \left[ {G} \right] =V$ . Such a process always exists [Reference Andersen, Borgan, Gill and Keiding1, Chapter II, p. 83]. In particular, $G(t)- G(s) \sim N( \boldsymbol{0}, V(t)- V(s) ) $ , the multivariate normal distribution for $ 0 \leq s \leq t$ .

Theorem 2. (Functional central limit theorem.) Consider the stochastic SI model described in Section 2.2. Assume A1, A2, and A3 for a CM graph $\mathcal{G}(\psi, n)$ . Consider, for $t \in \mathcal{T}_{0}$ , the fluctuation process

(4.16) \begin{align} Y(t) \,:\!=\, \sqrt{n} \big( n^{- 1} X(t) - x(t) \big) . \end{align}

Assume $\lim_{n \rightarrow \infty} Y(0) = U(0) $ , for some non-random U $(0) $ . Then there exists a matrix-valued function $V \in \mathcal{V} $ on $\mathcal{T}_{0}$ such that

(4.17) \begin{align} Y \overset{\mathcal{D}}{\implies} U \ {in}\ D^{(3)} {as}\ n \rightarrow \infty , \end{align}

where U is a continuous Gaussian vector semimartingale satisfying

(4.18) \begin{align} U(t) = U(0) + G(t) + \int_{0}^{t} \nabla \mathbb{H}_{{x}} \!\left( {x(s), \vartheta(s)} \right) U(s) \, {d} {s} , \end{align}

where $\nabla \mathbb{H}_{{x}} \!\left( {x, \vartheta} \right) \,:\!=\, (( \partial_j \mathbb{H}_{{i}} ( {x, \vartheta} ) ))$ for $i,j \in \{{S}, {SI}, {SS} \}$ and G is a continuous Gaussian vector martingale such that $ \left\langle {G} \right\rangle = \left[ {G} \right] =V$ , provided V remains finite on the entirety of $\mathcal{T}_{0}$ and $\nabla \mathbb{H}_{{x}} \!\left( {x(s), \vartheta(s)} \right) $ is continuous.

Proof of Theorem 2. We first prove an FCLT for the martingale process M defined in Equation (4.1). We wish to apply Rebolledo’s FCLT for local martingales on M. A version of the Rebolledo theorem adequate for our purpose is provided in Appendix C. Note that, in light of the Doob–Meyer decomposition given in Equation (2.2), M is indeed a pure-jump, zero-mean, locally square-integrable, càdlàg martingale. After having established an FCLT for the martingale process M, we prove convergence of the fluctuation process Y. It suffices to carry out the following three steps.

Step I: Deterministic limit of $ \left\langle {M} \right\rangle $ . Let $ (x, \vartheta) $ be the solution of Equation (3.8) with initial condition $x (0) = \alpha $ and $\vartheta (0)=1$ , as given in Theorem 1. Then, by virtue of Lemma 2, we conclude, for each $t \in \mathcal{T}$ , $ \left\langle {M} \right\rangle (t) \xrightarrow[]{ {P}} V(t)$ , where the matrix-valued function V is defined in Equation (4.5), and we set $V(0) \,:\!=\, \boldsymbol{0}$ , the $3 \times 3$ null matrix.

Step II: Asymptotic rarefaction of jumps. Let $\epsilon>0$ be arbitrary. Consider the vector $M^\epsilon$ of square-integrable martingales containing all jumps of components of M(t) larger than $\epsilon$ in absolute value for $\epsilon>0$ , as defined in Equation (4.2). Then, by means of Lemma 4, we conclude $ \left\langle {M^\epsilon_{id}} \right\rangle (t) \xrightarrow[]{ {P}} 0 $ , for each $t \in \mathcal{T}$ and $id \in \{{S}, {SI}, {SS}\}$ .

Now let G be the continuous Gaussian vector martingale such that $ \left\langle {G} \right\rangle = \left[ {G} \right] =V$ . In light of Rebolledo’s theorem for locally square-integrable martingales (see Appendix C and also [Reference Andersen, Borgan, Gill and Keiding1, Chapter II, p. 83]), Step I and Step II are sufficient to establish

\begin{align} ( M(t_1),M(t_2),\ldots, M(t_l)) \overset{\mathcal{D}}{\implies} ( G(t_1),G(t_2),\ldots, G(t_l)) \quad \text{as} n \rightarrow \infty \nonumber \end{align}

for all $ t_1,t_2, \ldots, t_l \in \mathcal{T}$ . Furthermore, since $\mathcal{T}$ is dense in $\mathcal{T}_{0}$ , we conclude $M \overset{\mathcal{D}}{\implies} G $ in $D^{(3)}$ as $n \rightarrow \infty$ , and $ \left\langle {M} \right\rangle $ and $ \left[ {M} \right] $ converge uniformly on compact subsets of $\mathcal{T}_{0}$ , in probability, to V.

Step III: Convergence of the fluctuation process. In keeping with the Doob–Meyer decomposition given in Equation (2.2),

\begin{align} Y(t) = Y(0) + M(t) + \int_0^{t} \sqrt{n} \bigg( \frac{1}{n} \mathbb{F}_{{X}} \!\left({\tilde{X}(s)} \right) - \mathbb{H}_{{x}} \!\left( {x (s) , \vartheta (s)} \right) \bigg) \, {d} {s} , \nonumber\end{align}

we expect the following limit process:

(4.19) \begin{align} U(t) = U(0) + G(t) + \int_{0}^{t} \nabla \mathbb{H}_{{x}} \!\left( {x(s), \vartheta(s)} \right) U(s) \, {d} {s} . \end{align}

Indeed, define

\begin{align*} \Delta (t) \,:\!=\, & \int_{0}^{t} \sqrt{n} \left( \frac{1}{n} \mathbb{F}_{{X}} \!\left({\tilde{X}(s)} \right) - \mathbb{H}_{{x}} \!\left( {x (s) , \vartheta (s)} \right) - \frac{1}{\sqrt{n}} \nabla \mathbb{H}_{{x}} \!\left( {x(s), \vartheta(s)} \right) \, Y(s) \right) \, {d} {s} \\ = & \int_{0}^{t} \sqrt{n} \bigg( \frac{1}{n} \mathbb{F}_{{X}} \!\left({\tilde{X}(s)} \right) - \mathbb{H}_{{x}} \!\left( {\frac{1}{n}X(s) , \theta (s)} \right) + \mathbb{H}_{{x}} \!\left( {\frac{1}{n}X(s) , \theta (s)} \right) \\ &{} - \mathbb{H}_{{x}} \!\left( {x (s) , \vartheta (s)} \right) - \frac{1}{\sqrt{n}} \nabla \mathbb{H}_{{x}} \!\left( {x(s), \vartheta(s)} \right) \, Y(s) \bigg) \, {d} {s} .\end{align*}

Note that the strong law of large numbers in Theorem 1 establishes uniform convergence (in probability) of the operators $ n^{-1} \mathbb{F}_{{X}} \!\left({\tilde{X}(s)} \right)$ and $\mathbb{H}_{{x}} \!\left( {\frac{1}{n}X(s) , \theta (s)} \right) $ , and the latter operator is Lipschitz continuous on its domain (see [Reference Jacobsen, Burch, Tien and Rempała30]). In light of Theorem 1 and A3, it follows from the Lipschitz continuity of various multinomial compensators $C_m^{k}$ introduced in the proof of Lemma 2 that

\begin{equation*}\lim_{n \rightarrow \infty} \sqrt{n} \!\left( \frac{1}{n} \mathbb{F}_{{X}} \!\left({\tilde{X}(s)} \right) - \mathbb{H}_{{x}} \!\left( {\frac{1}{n}X(s) , \theta (s)} \right) \right) = 0.\end{equation*}

Moreover, we have just shown $M \overset{\mathcal{D}}{\implies} G\ \text{in}\ D^{(3)}$ . If V remains finite on the entirety of $\mathcal{T}_{0}$ , the matrix-valued function $\nabla \mathbb{H}_{{x}} \!\left( {x(s), \vartheta(s)} \right) $ is continuous, and $\lim_{n \rightarrow \infty} Y(0) = U(0) $ , for some non-random U(0), then we have $\sup_{t \in \mathcal{T}_{0}} | \Delta (t) | \xrightarrow[]{ {P}} 0 $ following Theorem 1, and by an application of the continuous mapping theorem we conclude

\begin{align} Y \overset{\mathcal{D}}{\implies} U\ \text{in}\ D^{(3)}\ \text{as}\ n \rightarrow \infty , \nonumber \end{align}

where the Gaussian semimartingale U satisfies Equation (4.19) with the Gaussian martingale G being such that $ \left\langle {G} \right\rangle = \left[ {G} \right] =V$ . This completes the proof.

5.1. Percolation

There is a connection between the stochastic SI model and the percolation theory known from statistical physics and developed to study the process of liquid filtering (‘percolating’) through a porous medium. Classical equilibrium mechanics studies its stationary behaviour and is premised upon the axiom that the underlying quantum-mechanical laws are designed so as to maximize the entropy. The stationary distribution of such a stochastic system is given by the Boltzmann ensemble. This classical treatment of the subject, however, does not explain the non-equilibrium behaviour of the dynamical system, i.e., when it is still in a transient phase. Consequently, the non-equilibrium behaviour of percolation has aroused much interest in recent times. Some notable contributions include [Reference Hinrichsen29, Reference Barato and Hinrichsen5]. The standard treatment of percolation, both equilibrium and non-equilibrium, has been extended in another important direction concerning the structure of the porous medium. Traditionally it has been studied on lattices and grids. Of late, however, percolation on random graphs has also been considered ([Reference Baroni, van der Hofstad and Komjáthy9, Reference Callaway, Newman, Strogatz and Watts19, Reference Van der Hofstad46]). Continuing in this direction, we shall treat (non-equilibrium) percolation as a dynamical process on a CM random graph and study its behaviour over a finite time interval.

One of the key quantities of interest in the study of non-equilibrium percolation is the time evolution of the number of wetted sites (also called ‘active’ vertices in the literature). The correspondence between our stochastic SI model as described in Section 2.2 and non-equilibrium percolation is visible if we treat the infected vertices as the ones wetted during the process of percolation. Accordingly, in this context, we give the process X(t) an appropriate new interpretation. The process $X_{{S}}(t)$ , for example, captures the number of unwetted sites until time t, and the process $X_{{SI}}$ captures the number of channels (bonds) through which the liquid can percolate. In Figure 1, the percolated component up to a given time (the wetted part of the graph) is shown in red. Having made the correspondence precise, we can apply Theorem 2 to approximate these quantities in the large graph limit.

Numerical illustration. In Figure 3, we show some simulation results to check the accuracy of our scaling limit. We compare the expected sample paths of $X_{{S}}$ and $X_{{SI}}$ provided by Theorems 1 and 2 with estimates obtained using simulations of Gillespie’s algorithm on a CM graph. In particular, we consider a Poisson degree distribution in Figure 3a and a 3-regular random graph in Figure 3b (obtained by the CM construction with degree distribution $p_k=\mathsf{1}\!\left({k=3}\right)$ ). In Figure 4, we compare the simulated sample paths of the true Gillespie dynamics and those corresponding to the diffusion approximation for a negative binomial degree distribution. Figures 3a, 3b, and 4 show convincing accuracy of the diffusion approximation. In Figure 5, we show the time evolution of the correlation coefficient between the jumps of $X_{{S}}$ and $X_{{SI}}$ , and also the expected sample path coupled with 95%-confidence ellipses in the space of $X_{{S}}$ and $X_{{SI}}$ . The orientation of the confidence ellipses is calculated as the angle of the eigenvector corresponding to the largest eigenvalue of the covariance matrix towards the x-axis. To be specific, the orientation is given by $\omega \,:\!=\, \arctan{e_2/e_1}$ , where $e \,:\!=\, (e_1, e_2)$ is the eigenvector corresponding to the largest eigenvalue of the covariance matrix. The lengths of the major and minor axes are determined using the eigenvalues and by looking up the probability table of the chi-squared distribution (recall that squared normal variates follow a chi-squared distribution). The MATLAB script used to draw the ellipses is based on a script provided by [Reference Spruyt45].

Figure 3.

Comparison of our diffusion approximation with simulation results obtained by Gillespie’s algorithm.

Figure 4.

Comparison of simulated sample paths. Left: Sample paths obtained through Gillespie’s algorithm. Right: Sample paths obtained through diffusion approximation. Simulation setting: $n=1000$ , negative binomial distribution with $r=2$ , $p=3/4$ .

Figure 5.

The figures on the left depict the time evolution of the correlation coefficient between jumps of $X_{{S}}$ and $X_{{SI}}$ as estimated from numerical simulations (via Gillespie’s algorithm), pitted against theoretical values computed from the FCLT (Theorem 2). The figures on the right show the expected sample path in the space of $X_{{S}}$ and $X_{{SI}}$ . The two lines correspond to numerical simulation and theoretical values. The dotted ellipses are the 95%-confidence ellipses based on estimates of covariances between $X_{{S}}$ and $X_{{SI}}$ from the diffusion approximation created using a MATLAB script provided by [Reference Spruyt45]. The arrows indicate the time direction. Above: Poisson distribution with mean 5. Below: r-regular random graph with $r=3$ . In both cases, $n=1000$ , $\alpha_{{S}}=0.9$ , and $\beta=0.5$ .

The existence of a giant component and the proportion of vertices on the giant component play an important role in percolation theory, especially from an equilibrium point of view in statistical mechanics. The case of a degree distribution $\{p_k \}_{k \in \mathbb{N}_0}$ such that $\sum_{k \in \mathbb{N}_0} k^2 p_k = 2 $ $\sum_{k \in \mathbb{N}_0} k p_k$ and $p_1=0$ (or, equivalently, $p_0 + p_2 = 1$ ) is a curious one, in that quite different behaviours of the giant component are observable for such a degree distribution. (The reader should refer to [Reference Janson and Luczak32] for examples of such behaviours.) Barring this exceptional case, in light of A3, the condition for existence of a giant component is satisfied (see [Reference Molloy and Reed39]) for our stochastic SI model in the traditional sense. To be precise, setting $\alpha_{{S}}=1$ and taking the asymptotic limit in time, one finds the fraction of vertices on the giant component to be $1- \psi(\theta_\infty)$ , where $\theta_\infty>0$ is the solution of $\partial\psi(1) \theta_\infty= \partial \psi( \theta_\infty)$ (see [Reference Janson, Luczak and Windridge31, Reference Molloy and Reed40]). However, as mentioned earlier, we take a non-equilibrium point of view and concern ourselves with the time evolution of the fraction of vertices on the infected part of the graph, the ‘percolated component’. As a by-product of the scaling limits in Theorem 1 and Theorem 2, the variable $\theta$ defined in Equation (2.5) gives us a tool to approximate the proportion of susceptible individuals in the population (and hence the proportion of infected vertices as well). We expect the fraction of infected individuals to converge in probability to $1- \alpha_{{S}} \psi(\vartheta)$ as $n \rightarrow \infty$ , $\vartheta$ being the scaling limit of $\theta$ . A fixed time interval $\mathcal{T}_{0}$ enables us to look for critical values in the space of the infection rate $\beta >0$ . This allows us to decide whether the system ‘percolates’ in the sense that the fraction of vertices on the percolated component achieves a value greater than a pre-specified one (usually close to unity) by time T. Using different colours in Figure 6, we depict the fraction of vertices on the percolated component as a function of both time and the infection rate $\beta$ (let us call such a figure a percolation profile) for three degree distributions with the same mean. Questions such as whether the system with an infection rate $\beta$ ‘percolates’ are immediately settled by drawing a horizontal line and checking whether the line passes through the colour corresponding to the pre-specified level. See Figure 7 for another comparative view, highlighting the need to take into account higher moments of the degree distribution.

Figure 6.

Comparison of percolation profiles of three degree distributions having the same mean. Left: Poisson distribution with mean 6. Middle: A heterogeneous population with degree distribution $p_k \,:\!=\, 0.7 \times \mathsf{1}\!\left({k=1}\right) + 0.2 \times \mathsf{1}\!\left({k=4}\right) +0.1 \times \mathsf{1}\!\left({k=45}\right)$ . Such a degree distribution represents a population segregated into three classes. Weak vertices constitute the biggest class, followed by medium-strength vertices and then strong vertices. Right: Negative binomial distribution with parameters $r=2$ , $p={3}/{4}$ . The figures show the time evolution of the fraction of vertices on the percolated component for varying infection rates $\beta$ . We assume the initial fraction of infected vertices is $0.1$ in all three cases. The yellow region in each of the plots corresponds to the terminal state. Questions such as whether the system with an infection rate $\beta$ ‘percolates’ are immediately settled by drawing a horizontal line and checking whether the line passes through the colour corresponding to a pre-specified level. It is worth noting that the limiting proportions of vertices in the giant components eventually getting infected are also quite different for the three degree distributions. While the proportion is around $0.91$ (approximately) for the negative binomial distribution and the hand-picked degree distribution in the middle, it is relatively high for the Poisson distribution (approximately $0.99$ ).

Figure 7.

Left: Comparison of the time evolution of the fraction of vertices on the percolated component for different degree distributions with the same mean. The 2-degree distribution in the plot refers to the degree distribution $p_k = 0.5 \times \mathsf{1}\!\left({k=1}\right) + 0.5 \times \mathsf{1}\!\left({k=9}\right)$ , where none of the vertices have degree 5 yet the average degree is 5. This presents a pathological case and highlights the need to take into account higher moments of the degree distribution. Right: Comparison of discounted cost against increasing average degree for different degree distributions. With increasing average degree the graphs lose sparsity and facilitate the spread of a computer virus. Therefore, they incur higher cost. When the average degree is very small, regular random graphs seem favourable compared to random graphs with negative-binomially distributed degrees. The costs are computed with $n=1000$ , $\gamma=1$ .

5.2. The strange case of Poisson-type degree distributions and the exactness of the pair approximation

We consider a particular class of degree distributions called ‘Poisson-type’ (PT) by [Reference Jacobsen, Burch, Tien and Rempała30]. A degree distribution with probability generating function $\psi$ is called PT if $\kappa(\vartheta )$ , defined in Equation (3.4), is a constant, i.e., $\kappa (\vartheta) =\kappa$ for some $\kappa \in \mathbb{R}$ (or, equivalently, $\partial{\psi (\vartheta)}= \partial{\psi (1)} \!\left(\psi (\vartheta)\right)^{\kappa}$ ). As a consequence, the operators defined in Equation (3.3) are also constants, and satisfy

\begin{align} \mathbb{D}^{r} {\psi\circ \vartheta} = \prod_{i=1}^{r-1} \left( i \kappa - i +1 \right) = \left( (r-1)\kappa -r +2 \right) \, \mathbb{D}^{r-1} {\psi\circ\vartheta} , \nonumber\end{align}

with $\mathbb{D}^{0} {\psi\circ \vartheta} =1$ . The PT class includes Poisson ( $\kappa=1$ , irrespective of the mean of the distribution), degenerate $\big($ r-regular random graphs, $\kappa =\frac{r-1}{r} <1\big) $ , binomial $\big(\kappa = \frac{N-1}{N} <1$ , independent of p for ${Bin}(N,p)\big)$ , and negative binomial $\big(\kappa = \frac{r+1}{r}>1$ , independent of p for ${NB}(r,p)\big)$ degree distributions. The PT class is particularly peculiar in that it totally decouples the vector $x = (x_{{S}}, x_{{SI}}, x_{{SS}})$ and the matrix-valued function V from the auxiliary variable $\vartheta$ , so that an autonomous system of ODEs can be obtained for x and V, rendering $\vartheta$ redundant. This allows for great simplification in the limiting equations. Define $\mathbb{G}_{{}} \!\left( {x} \right) \,:\!=\, (\mathbb{G}_{{S}} \!\left( {x} \right),\mathbb{G}_{{SI}} \!\left( {x} \right),\mathbb{G}_{{SS}} ( {x} ) )$ as

(5.1) \begin{align}\begin{aligned}\mathbb{G}_{{S}} \!\left( {x} \right) & \,:\!=\, -\beta x_{{SI}} , \\\mathbb{G}_{{SI}} \!\left( {x} \right) & \,:\!=\, \beta \kappa \frac{x_{{SI}}}{x_{{S}}} (x_{{SS}}- x_{{SI}}) - \beta x_{{SI}} , \\\mathbb{G}_{{SS}} \!\left( {x} \right) & \,:\!=\, -2 \beta \kappa \frac{x_{{SI}} x_{{SS}}}{x_{{S}}} .\end{aligned}\end{align}

Plugging $\mathbb{D}^{2} {\psi\circ \vartheta} =\kappa$ and $\mathbb{D}^{3} {\psi\circ\vartheta} =\kappa (2 \kappa -1) $ into Equation (4.4), we find that the matrix-valued function V is entirely determined by x. The following is immediate.

Corollary 1. (Scaling limit under PT distributions.) Assume A1, A2, and A3 for a CM graph $\mathcal{G}(\psi, n)$ with $\partial\psi (\vartheta) = \partial\psi (1) (\psi (\vartheta))^\kappa $ for some $\kappa \in \mathbb{R}$ . Then the following law of large numbers holds:

\begin{align*} \sup_{0<t \leq T} \left\lVert{n^{-1} X(t) -x(t)}\right\rVert \xrightarrow[]{ {P}} 0 , \end{align*}

where x is the solution of $ x(t) = x(0) + \int_{0}^{t} \mathbb{G}_{{}} \!\left( {x(s)} \right) \, {d} {s} $ with $x(0) = \alpha$ . Moreover, the fluctuation process Y defined in Equation (4.16) converges weakly to a continuous Gaussian vector semimartingale U satisfying

\begin{align*} U(t) = U(0) + G(t) + \int_{0}^{t} \nabla \mathbb{G} \!\left( {x(s)} \right) U(s) \, {d} {s} ,\end{align*}

where G is a Gaussian vector martingale such that $ \left\langle {G} \right\rangle = \left[ {G} \right] = V$ .

In fact, one can obtain a smaller system by expressing $x_{{SI}}$ and $x_{{SS}}$ explicitly as functions of $x_{{S}}$ (see [Reference Jacobsen, Burch, Tien and Rempała30]). This is remarkable because, under the PT class, the graph structure affects the scaling limits only through two summary statistics of $\psi$ , namely the mean $\partial \psi(1)$ and $\kappa=\mathbb{D}^{2} {\psi(1)}$ . Recall that $\kappa$ , as defined in Equation 3.4, is the limiting ratio of the average excess degree of a susceptible vertex chosen at random as a neighbour of an infected vertex, to the average degree of a susceptible vertex. Therefore it is, in general, dependent on time through $\vartheta$ . Under the PT class, this ratio remains constant throughout the entire course of time $\mathcal{T}_{0}$ . Moreover, the mean $\partial \psi(1)$ only affects the initial condition $x(0)=\alpha$ through Equation (3.2). The dynamics of the limiting process are then dictated by the constant $\kappa$ under the PT class.

Now we revisit the correlation equations approach of [Reference Rand43], from the ecology literature, to study the dynamics of counts of singles, pairs, triples, and quadruples of the form A, AB, ABC, ABCD, where $A,B,C,D \in \{{S}, {I}\}$ . Following [Reference Rand43], we use the notation $\left[ {\cdot} \right]$ to denote the count. In this mean-field approach, the dynamics of singles are described by those of pairs, the dynamics of pairs by those of triples, and so on. In this context, pair approximation refers to approximating the count of triples by pairs as

\begin{align*}\left[ {ABC} \right] \approx \kappa \frac{\left[ {AB} \right] \left[ {BC} \right]}{\left[ {B} \right]} ,\end{align*}

and closing the system at the level of pairs (also known as pair closure). In order to draw an analogy, we divide the counts by n and use the same notation for the scaled counts. We also set the same initial condition $([ {{S}}],[ {{SI}}], [ {{SS}} ]) = \alpha$ at $t = 0$ . The pair approximation then yields a system of ODEs for $([ {{S}} ],[ {{SI}} ],[ {{SS}} ])$ that exactly matches the limiting ODEs for $n^{-1}X$ , i.e.,

(5.2) \begin{align} \frac{\, {d}}{\, {d} {t}} {([ {{S}} ], [ {{SI}}], [ {{SS}}])} = \mathbb{G} \left( {([ {{S}} ], [ {{SI}}], [ {{SS}}])} \right) .\end{align}

Therefore, under the PT class, the pair approximation is exact in the sense that it correctly estimates the limiting means of various counts. By virtue of Corollary 1, our FCLT further enables it to correctly estimate all other higher limiting moments, because V is now entirely determined by the solution of Equation (5.2). As the PT class is quite big, our FCLT thus greatly enhances the usefulness of the pair approximation.

5.3. Spread of computer viruses

Epidemic models have been used in the context of the spread of computer viruses for some years now. The correspondence between our model and the application area under consideration is apparent without requiring much change in nomenclature. Early works in this direction did not take into account the inherent graph structure and assumed ‘homogeneous mixing’ in some sense. Recent works, however, have duly studied it on more realistic computer networks, which are often modelled as random graphs, without the assumption of ‘homogeneous mixing’. Lelarge, for example, based much of his work on classical Erdős–Rényi random graphs and CMs (see, e.g., [Reference Lelarge35]). Interested readers are referred to [Reference Kephart and White34, Reference Lelarge35, Reference Wierman and Marchette49] for an overview of relevant literature. Applying our results, we can approximate the number of virus-affected computers over time and the numbers of edges of different types. Additionally, one might be interested in estimating some ‘cost’ involving the count variables in a linear or nonlinear fashion. For instance, if the cost function is polynomial in the count variables, the mixed moments of various orders can be approximated by means of Theorem 2. To illustrate the concept using a simple example, we assume an exponentiated form for the incurred cost to emphasize the severity of a computer being virus-affected. We can then compute time-discounted expected incurred cost and study how it behaves with decreasing sparsity of the underlying graph. To this end, define

(5.3) \begin{equation}\begin{aligned}I(t) \,:\!=\, & \exp \bigl( {c X_I (t)} \bigr), \\C_\psi \,:\!=\, & \mathbb{E}\!\left[{\int_{\mathcal{T}_{0}} \exp \bigl( {- \gamma t} \bigr) I(t) \, {d} {t}}\right] = \int_{\mathcal{T}_{0}} \exp \bigl( {- \gamma t} \bigr) \mathbb{E}\!\left[{I(t)}\right] \, {d} {t} ,\end{aligned}\end{equation}

where $c>0$ and $\gamma>0$ are constants. In Figure 7, we plot the discounted cost $C_\psi $ against an increasing average degree of the underlying graph, engendering decreasing sparsity. When the average degree is very small, regular random graphs seem favourable compared to random graphs with negative-binomially distributed degrees.