2.1. Random graph model

For each $n \in \mathbb{N}$ , we consider a vertex set $[n] = \{1, 2, \ldots, n\}$ . Each vertex $i \in [n]$ is assigned a deterministic parameter $s_i (n)\in \mathcal{S}$ . This parameter is called the vertex type, and it takes values in a compact metric space $\mathcal{S}$ . The type is a vertex characteristic that will determine its local connectivity properties. Examples of vertex types in a social network could be gender, nationality, or location of residence, to name a few. Let $\boldsymbol{s} (n)=(s_1 (n), \ldots, s_n (n))$ be the vector of the types of all vertices. We will often omit n and just write $\boldsymbol{s}$ and $s_i$ for $i\in [n]$ . We consider directed random graphs without self-loops. The connection probability $p_{ij} = p_{ij}(n)$ between two vertices $i, j \in [n]$ depends now on their types $s_i$ and $s_j$ , and is specified by some non-negative and Borel measurable kernel function: $\kappa\,:\,\mathcal{S}^2 \rightarrow \mathbb{R}$ : a directed edge between vertex i and j ( $i\neq j$ ) is present with probability

\begin{align*}p_{ij} = \min\{1, \kappa(s_i, s_j)/n\}.\end{align*}

Further, let the event that an edge is present be independent of the presence of all other edges.

2.2. Bootstrap percolation

In addition to the parameter $s_i$ we assign to each vertex $i\in [n]$ a second deterministic parameter $r_i(n) \in \mathbb{N}_0$ . The parameter $r_i(n)$ represents a threshold level of vertex i, and determines in the percolation process how many neighbors of the vertex i need to be infected for the vertex i to become infected itself. We denote by $\boldsymbol{r} (n)=(r_1(n),\ldots,r_n (n))$ the vector of thresholds.

Figure 1.

An example of a bootstrap percolation process on a directed graph with $n=10$ vertices, each having threshold 2. The process evolves over six rounds before terminating, as no further infections occur. The rounds are arranged from left to right and from top to bottom. Green circular vertices have not yet received any incoming edge from an infected vertex; blue pentagonal vertices have received exactly one incoming edge from an infected vertex; and violet star vertices are infected, either initially or during the process.

Figure 1 Long description

Panel A: The initial state of the directed graph with green circular vertices not yet infected, blue pentagonal vertices with one incoming edge from an infected vertex, and violet star vertices initially infected. Panel B: The first round of infection spread, showing changes in vertex states. Panel C: The second round of infection spread, with further changes in vertex states. Panel D: The third round of infection spread, continuing the process. Panel E: The fourth round of infection spread, with more vertices becoming infected. Panel F: The fifth round of infection spread, nearing the termination of the process. Panel G: The sixth and final round of infection spread, where no further infections occur, terminating the process.

More precisely, let $\mathbb{D}_0$ be the set of initially infected vertices, i.e. $\mathbb{D}_0\,:\!=\,\{ i\in [n] \mid r_i(n)=0 \}$ . The set $\mathbb{D}_0$ starts the process. Let $N(i)\,:\!=\,\{ j \in [n] \mid E_{ji}=1\}$ denote the set of neighbors with a directed edge pointing to vertex i, where $E_{ji}$ is a binary indicator of an edge from j to i. Then, in the first generation, those vertices get infected whose number of edges from vertices in $\mathbb{D}_0$ reaches or exceeds their threshold, i.e. $\mathbb{D}_1 = \{i \in [n]\,:\, |\mathbb{D}_0 \cap N(i)| \ge r_i(n)\}$ . As the infection continues to spread, the infected vertices in the mth generation, where $m \in \mathbb{N}$ , are given by

\begin{equation*} {\mathbb{D}}_m = \{i \in [n]\,:\, |{\mathbb{D}}_{m-1} \cap N(i)| \ge r_i(n)\}.\end{equation*}

Since there are n vertices in total, the spread certainly comes to an end after at most n steps, and $\mathbb{D}_{M} = \mathbb{D}_{M+1}=\cdots $ for some $M\leq n$ . We denote by $\mathbb{D}_{n}$ the final set of infected vertices. Note that given the realization of the random graph, the bootstrap percolation process is deterministic. In Figure 1 we exemplify the bootstrap percolation process for a graph with $n=10$ vertices. In this example graph, two vertices are initially infected and all remaining vertices have a threshold equal to 2. The graph is a random sample arising from a kernel that we specify in our case study in Section 4.

In this paper we investigate the fraction $n^{-1}|\mathbb{D}_{n}|$ of infected vertices as $n\rightarrow \infty$ , in the random graph described above. This requires that we have a sequence of random graphs parameterized by n. Recall that for fixed n, all relevant information about the probabilistic structure of the skeleton of the graph is encoded in $\kappa$ and $\boldsymbol{s} (n)$ , while the additional information required for the bootstrap percolation process is encoded in $\boldsymbol{r} (n)$ . A sequence of random graphs, together with their percolation parameters, can then be derived by specifying $\kappa$ and a sequence of vectors $(\boldsymbol{s} (n),\boldsymbol{r} (n))_{n\in \mathbb{N}}$ . We will pose a regularity condition that ensures that the proportion of vertices of each type and threshold converges as $n\rightarrow \infty$ .

Assumption 1. For each n and for given $k\in \mathbb{N}_0$ and Borel set $A \subset \mathcal{S}$ , let $U_k^{(n)}(A) = \{i \in [n]\,:\, r_i(n)=k, s_i(n) \in A\}$ be the set of vertices with threshold equal to k and type in A. Further, let $\nu^{(n)}(k,A) \,:\!=\, |U_k^{(n)}(A)| / n$ be their proportion. We will assume that there exists a measure $\nu$ on $\mathbb{N}_0 \times \mathcal{S}$ such that for each fixed k the measure $\nu(k,\cdot)$ is a Borel measure on $\mathcal{S}$ and that for every $k\in \mathbb{N}_0$ and Borel set A it holds that

\begin{align*}\nu^{(n)}(k,A) \xrightarrow[n\rightarrow \infty]{} \nu (k,A).\end{align*}

We denote by $\mu$ the marginal measure of $\nu$ on $\mathcal{S}$ , and by $\eta_k$ the Radon–Nikodym derivative of $\nu (k, \cdot)$ against $\mu$ on $\mathcal{S}$ ; that is, for every Borel set A,

(2.1) \begin{align} \mu(A)=\sum_{k=0}^{\infty} \nu(k,A),&\quad \nu(k, A) = \int_{A} \eta_k(s) \mathrm{d} \mu(s).\end{align}

One way to ensure that Assumption 1 is satisfied is by starting with a measure $\nu$ on $\mathbb{N}_0 \times \mathcal{S}$ and assigning types and thresholds to vertices independent and identically distributed from this distribution. Then, the strong law of large numbers ensures that the condition (2.1) holds. We provide examples in Section 4. Let the vector $\mathcal{V}\,:\!=\,(\kappa,\nu, \boldsymbol{s} (n),\boldsymbol{r} (n))_{n\in \mathbb{N}}$ collect all information about the vertex sequence, and denote the random graph with n vertices derived from this sequence by $G(n,\mathcal{V})$ . The random graph model used here is an adapted version of the model proposed in [Reference Bollobás, Janson and Riordan9], enriched by the threshold values $\boldsymbol{r}(n)$ , which are crucial parameters for the process we study. While the actual final set of infected vertices $\mathbb{D}_n$ depends on the realization of the random graph $G(n,\mathcal{V})$ , we will see that under Assumption 1 for large n, a law of large numbers holds, and we can determine the limit in probability of $n^{-1}|\mathbb{D}_n|$ for $n\rightarrow \infty$ purely in terms of $\kappa$ , $\nu$ , and $\mathcal{S}$ .

2.3. Results

In this section we present the main results of this paper about the final number of infected vertices at the end of the bootstrap percolation process. We pose the following assumption throughout this paper.

We provide specifications for $\kappa$ in Section 4. In light of Assumption 2, note that by the Tychonoff theorem, it follows from compactness of $\mathcal{S}$ that $\mathcal{S} \times \mathcal{S}$ is compact with respect to the product topology, and then in particular that $\kappa$ is bounded on $\mathcal{S} \times \mathcal{S}$ . We let in the following $M_{\kappa}$ be the bound of $\kappa$ . Our main result will show that under Assumptions 1 and 2 the final proportion of infected vertices $n^{-1}|\mathbb{D}_n| $ converges in probability to a quantity that can explicitly be determined by solving a fixed-point equation in a function space.

We now introduce the operators that will be important for the analysis of the bootstrap percolation process.

Related operators: Let $\mathcal{F}_{\mathrm{b}}$ be the set of bounded, non-negative, and Borel measurable functions on $\mathcal{S}$ ,

(2.2) \begin{align} \mathcal{F}_{\mathrm{b}}\,:\!=\,\{\,f\,:\,\mathcal{S} \rightarrow \mathbb{R}_+, \text{bounded, Borel}\}.\end{align}

We equip $\mathcal{F}_{\mathrm{b}}$ with the supremum norm $\|\cdot\|_{\infty}$ , defined by $\|f\|_{\infty}\,:\!=\,\sup_{s\in \mathcal{S}} |f(s)|$ , which turns $\mathcal{F}_{\mathrm{b}}$ into a metric space with metric given by $d(f_1,f_2)=\|f_1(s)-f_2(s)\|_{\infty}$ . We stress that $\mathcal{F}_{\mathrm{b}}$ is actually not a vector space but only a convex cone because it contains only the non-negative functions. Although $\mathcal{F}_{\mathrm{b}}$ is not a vector space we will still use the norm symbol $\|\cdot\|_{\infty}$ , which causes no problem because $\mathcal{F}_{\mathrm{b}}\subset \{ f\,:\,\mathcal{S} \rightarrow \mathbb{R}, \text{bounded}\}$ , which is a Banach space. We further define

(2.3) \begin{align} \mathcal{F}_1\,:\!=\,\{\,f\,:\,\mathcal{S} \rightarrow [0,1], \text{Borel}\}\subset \mathcal{F}_{\mathrm{b}},\end{align}

the subset of those functions that are bounded by 1, and the two constant functions $\mathcal{F}_{\mathrm{b}} \ni \boldsymbol{0}\,:\, \mathcal{S} \rightarrow \{0\}$ and $\mathcal{F}_{\mathrm{b}} \ni \boldsymbol{1}\,:\, \mathcal{S} \rightarrow \{1\}$ .

For a Borel measurable kernel function $\kappa\,:\,\mathcal{S}^2 \rightarrow \mathbb{R}$ , we define the operators $\Lambda_{\kappa}\,:\,\mathcal{F}_{\mathrm{b}}\rightarrow \mathcal{F}_{\mathrm{b}} , P_{\kappa}^k\,:\,\mathcal{F}_{\mathrm{b}}\rightarrow \mathcal{F}_1$ , and $\Psi_{\kappa}\,:\,\mathcal{F}_{\mathrm{b}}\rightarrow \mathcal{F}_1$ by

(2.4) \begin{equation} \begin{aligned} \Lambda_{\kappa} [f](\!\cdot\!) &\,:\!=\, \int_{s \in \mathcal{S}} \kappa(s, \cdot) f(s) \mathrm{d} \mu(s), \\ P_{\kappa}^k [f](\!\cdot\!) &\,:\!=\, \frac{\left(\Lambda_{\kappa} [f](\!\cdot\!)\right)^k}{k !} \mathrm{e}^{-\Lambda_{\kappa} [f](\!\cdot\!)}, \\ \Psi_{\kappa} [f](\!\cdot\!) &\,:\!=\, \sum_{k=0}^\infty \eta_k(\!\cdot\!)\left(1- \sum_{k'=0}^{k-1}P_{\kappa}^{k'} [f](\!\cdot\!)\right), \end{aligned}\end{equation}

where $\eta_k$ is the Radon–Nikodym derivative defined in (2.1) and the convention $0^0 = 1$ is used. We use bold centered dot notation with brackets $[\boldsymbol{\!\cdot\!}]$ for arguments that are function-valued $f \in \mathcal{F}_{\mathrm{b}}$ , and centered dot notation with parentheses $(\!\cdot\!)$ for arguments of type $s \in \mathcal{S}$ . In the following two lemmas, we state some important properties of the operators defined above. For $f, g \in \mathcal{F}_{\mathrm{b}}$ , we say that $f \le g$ if and only if $f(s) \le g(s)$ for all $s \in \mathcal{S}$ .

To state the next lemma we define subsets of $\mathcal{F}_{\mathrm{b}}$ and $\mathcal{F}_1$ defined in (2.2) and (2.3) that consist of continuous functions: For $\star \in \{b,1\}$ , define

(2.5) \begin{equation} \begin{aligned}\mathcal{F}_\star^{\mathrm{c}} &\,:\!=\,\{\,f\in \mathcal{F}_\star\,:\, f \text{ is continuous}\} \subset \mathcal{F}_\star, \\\mathcal{F}_\star^{\mathrm{Lip}} &\,:\!=\, \{\,f \in \mathcal{F}_\star\,:\, f \text{ is Lipschitz with constant } L_{\kappa} (1+M_{\kappa})M_{\kappa} \mathrm{e}^{M_{\kappa}}\} \subset \mathcal{F}_\star^{\mathrm{c}}.\end{aligned}\end{equation}

We will see that if a least fixed point of the operator $\Psi_{\kappa}$ exists, then it allows us to determine the limit in probability of the final proportion of infected vertices. By fixed point, we mean a function $f\in\mathcal{F}_{\mathrm{b}}$ such that $f = \Psi_{\kappa} f$ . With a Lipschitz condition on $\kappa$ , we can prove the existence of a least fixed point of $\Psi_{\kappa}$ .

Lemma 3. (Existence of the least fixed point.) Let $\kappa$ be Lipschitz continuous with constant $L_{\kappa}$ and $\mathcal{F}_1^{\mathrm{Lip}}$ as defined in (2.5). Further, let $\mathcal{H} \subset \mathcal{F}_1^{\mathrm{Lip}}$ be the set defined by

\begin{align*}\mathcal{H}\,:\!=\, \{\,f \in \mathcal{F}_1^{\mathrm{Lip}} \,:\, f = \Psi_{\kappa} f\}.\end{align*}

Then $\mathcal{H}\neq \emptyset$ , and $\mathcal{H}$ includes all the fixed points. Moreover, there exists a function $\eta_0 \leq \hat{f}\in \mathcal{H}$ such that $\hat{f}\leq h$ for every $h \in \mathcal{H}$ . We call $\hat{f}$ the least fixed point. Clearly, it then also holds that $\int_{\mathcal{S}} \hat{f} \mathrm{d} \mu =\min_{f \in \mathcal{H}} \big\{\! \int_{\mathcal{S}} f \mathrm{d} \mu \big\}$ .

Remark 2. Let us consider the special case of rank 1 models, a particular popular example being the Norros–Reittu model [Reference Norros and Reittu27]. Assume that the kernel $\kappa\,:\,\mathcal{S}^2 \rightarrow \mathbb{R}$ has multiplicative form, i.e. $\kappa (s,s')= \phi (s)\phi (s')$ with $\phi\,:\, \mathcal{S}\rightarrow \mathbb{R}$ continuous. From the definition of $\Lambda_{\kappa} [f], P_{\kappa}^k [f]$ , and $\Psi_{\kappa} [f]$ , it then follows that the fixed-point equation $f = \Psi_{\kappa} [f]$ can be written as

\begin{align*}f(s')= g\bigg(s',\phi(s') \int_{s\in \mathcal S} \phi(s)\, f(s)\,\mathrm{d}\mu(s)\bigg)\end{align*}

for monotonically increasing $g \,:\, \mathbb{R}_+ \rightarrow [0,1]$ given by

\begin{align*}g(s',z)=\sum_{k=0}^\infty \eta_k (s') \left(1- \sum_{k'=0}^{k-1}\frac{z^k}{k !} \mathrm{e}^{-z}\right).\end{align*}

Any fixed point must then be of the form $f_C(s) = g(s,\phi(s)\, C)$ with the constant $C \,:\!=\, \int_{s \in \mathcal S} \phi(s)\, f(s)\,\mathrm{d}\mu(s)$ . But for $f_C$ to satisfy the fixed-point condition, it must hold that $C = \int_{s\in \mathcal S} \phi(s)\, f_C(s)\,\mathrm{d}\mu(s)=\int_{s\in \mathcal S} \phi(s)\, g\bigl(s,\phi(s)\, C\bigr)\,\mathrm{d}\mu(s)$ . We therefore obtain a one- dimensional map

\begin{align*}F(C) \,:\!=\, \int_{s \in \mathcal S} \phi(s)\, g\bigl(s,\phi(s)\, C\bigr)\,\mathrm{d}\mu(s)\end{align*}

and fixed-point condition $C=F(C)$ . Once we find a fixed point $\hat{C}$ for F, the fixed point $\hat{f}$ can be obtained via $\hat{f} (s)= g\bigl(s,\phi(s)\, \hat{C}\bigr)$ , and conversely any fixed point arises in that way.

This consideration includes the simplest example of the homogeneous and sparse Erdős–Rényi graph with $c\gt 0$ fixed and $\kappa (s,s')=c=\phi (s)\phi (s')$ with $\phi (s)=\sqrt{c}$ . In this case, $\eta_k$ can be considered constant as the connection probability does not depend on the types, and

\begin{align*}g(s',z)=g(z)=\sum_{k=0}^\infty \eta_k \left(1- \sum_{k'=0}^{k-1}\frac{z^k}{k !} \mathrm{e}^{-z}\right).\end{align*}

Any fixed point $\hat{f}$ is then of the form $\hat{f} (s)= g\bigl(\sqrt{c}\, \hat{C}\bigr)$ and thus is a constant function. This recovers the well-known result about bootstrap percolation in this model; see [Reference Janson, Łuczak, Turova and Vallier23], where a one-dimensional fixed-point equation is derived.

The proof of Lemma 3 relies on an argument that requires us to find a subset $\mathcal{H}_1 \subset \mathcal{F}_{\mathrm{b}}$ of measurable functions that contains all fixed points of $\Psi_{\kappa}$ (if any) and that is such that for any subset $\mathcal{H}_2 \subset \mathcal{H}_1$ the pointwise supremum (respectively infimum) of the functions in $\mathcal{H}_2$ is a function in $\mathcal{H}_1$ . Because the supremum of measurable functions is not measurable in general, we need to choose a continuity property that is stable under our taking the supremum. Without the assumption that $\kappa$ is Lipschitz continuous, it is therefore not possible to show the existence of a fixed point, except for some special cases where either $\kappa$ is of a particular structural form or the thresholds of the vertices are all either 0 or 1.

Next we will specify the Fréchet derivative on a convex cone. Just as the Jacobian represents all partial and directional derivatives of a map from $\mathbb{R}^n$ to $\mathbb{R}^m$ , the Fréchet derivative does the same for functions between infinite-dimensional spaces. It is the linear operator that provides the best first-order approximation of a function near a point and encodes all directional derivatives at once. Recall that $\mathcal{F}_{\mathrm{b}}$ is a convex cone such that $a f_1 + b f_2 \in \mathcal{F}_{\mathrm{b}}$ for $f_1, f_2 \in \mathcal{F}_{\mathrm{b}}$ and any non-negative scalar $a,b\geq 0$ . Although the Fréchet derivative is usually defined on a vector space, it can be defined in the same spirit on $\mathcal{F}_{\mathrm{b}}$ . Let $C(\mathcal{F}_{\mathrm{b}},\mathcal{F}_{\mathrm{b}})$ be the space of continuous operators from $\mathcal{F}_{\mathrm{b}}$ to itself and

\begin{align*}L^+ (\mathcal{F}_{\mathrm{b}})\,:\!=\,\{ L\in C(\mathcal{F}_{\mathrm{b}},\mathcal{F}_{\mathrm{b}}) | L(a f_1 + b f_2)=aL(\,f_1) + b L(\,f_2) \,\,\, \text{ for all } a,b\in \mathbb{R}_+ , f_1,f_2\in \mathcal{F}_{\mathrm{b}} \}.\end{align*}

By definition, $L^+ (\mathcal{F}_{\mathrm{b}})$ is closed under linear combinations with non-negative scalars. For an operator $\Phi\,:\, \mathcal{F}_{\mathrm{b}} \rightarrow \mathcal{F}_{\mathrm{b}}$ , we call $D\Phi\,:\, \mathcal{F}_{\mathrm{b}} \rightarrow L^+(\mathcal{F}_{\mathrm{b}})$ the Fréchet derivative of $\Phi$ in $L^+(\mathcal{F}_{\mathrm{b}})$ if for all $f,h\in \mathcal{F}_{\mathrm{b}}$ it holds that

\begin{equation*}\lim_{\|h\|_{\infty}\rightarrow 0} \frac{\|\Phi(f+h) -\Phi(f) -D \Phi f [h] \|_{\infty}}{\|h\|_{\infty}}=0.\end{equation*}

Lemma 4 (Frìhet derivative.) The operator $\Psi_{\kappa} \,:\, \mathcal{F}_{\mathrm{b}} \rightarrow \mathcal{F}_{\mathrm{b}}$ is Fréchet differentiable at every point $f\in \mathcal{F}_{\mathrm{b}}$ , and the derivative $D \Psi_{\kappa}\,:\, \mathcal{F}_{\mathrm{b}} \rightarrow L^+(\mathcal{F}_{\mathrm{b}})$ is given by

(2.6) \begin{equation}D \Psi_{\kappa}f [\boldsymbol{\!\cdot\!}](\!\cdot\!) = \Lambda_{\kappa} [\boldsymbol{\!\cdot\!}] (\!\cdot\!) V[f](\!\cdot\!),\end{equation}

where $V[f](\!\cdot\!) \,:\!=\, \sum_{k=1}^{\infty} \eta_k(\!\cdot\!) P_{\kappa}^{k-1}[f] (\!\cdot\!)$ .

2.3.2. Resilience

In the previous section, we studied the final set of infected vertices for a random graph with a positive fraction of initially infected vertices, i.e. $\nu (0,\mathcal{S}) \gt 0$ . However, for a graph without any initial infection we now ask the following important question: If we impose infection on a certain proportion of vertices to start the percolation, to what extent does the final fraction of infected vertices depend on the proportion of imposed infection? Does it exceed a certain level $\Delta$ , no matter how small the infection is that we impose? This leads us to the question of resilience of the graph. To specify, we use the tilde notation to refer to the initially uninfected graph, starting from $\widetilde{\nu}(0, \mathcal{S}) = 0$ . We transform the graph from $\widetilde{\nu}(0, \mathcal{S}) = 0$ to $\nu(0, \mathcal{S}) \gt 0$ by setting the thresholds of some vertices to zero to mark them as infected, while keeping the thresholds of all other vertices unchanged. If there exists a lower bound $\Delta$ such that any proportion of imposed infection leads to at least $\Delta n$ infected vertices at the end of the process, we call the graph non-resilient. In contrast, we call it resilient if a reduction of the fraction of imposed infected vertices towards 0 ensures that also the final fraction of infected vertices approaches 0.

To formalize the setup, let $\widetilde{\mathcal{V}}\,:\!=\,(\kappa,\widetilde{\nu},(\boldsymbol{s} (n),\widetilde{\boldsymbol{r}} (n))_{n\in \mathbb{N}}$ be a vertex sequence that fulfills Assumption 1 and that is such that $\widetilde{\nu} (0,\mathcal{S})=0$ . For each $n\in \mathbb{N}$ , we now define a new threshold sequence $\boldsymbol{r} (n)= (r_1(n),\ldots,r_n (n))$ , which is such that for each $n\in \mathbb{N},1 \leq i\leq n$ either $r_i(n)=\widetilde{r}_i(n)$ or $r_i(n)=0$ . Note that this change does not affect the probabilistic structure of the random graph, which remains totally unchanged, but only marks some vertices as infected. For $k\in \mathbb{N}$ and Borel set $A\subset \mathcal{S}$ , define

\begin{align*}\nu^{(n)}(k,A) \,:\!=\, n^{-1} \sum_{i \in [n]} I_{\{k\}}(r_i)I_{A}(s_i),\end{align*}

where $I_{B}$ is the indicator function of set B. We further assume that for the new sequence there exists again a measure $\nu$ on $\mathbb{N}_0 \times \mathcal{S}$ such that for each fixed k the measure $\nu(k,\cdot)$ is a Borel measure on $\mathcal{S}$ , and that for every $k\in \mathbb{N}_0$ and Borel set A it holds that

\begin{align*}\nu^{(n)}(k,A) \xrightarrow[n\rightarrow \infty]{} \nu (k,A).\end{align*}

Moreover, we assume that $\nu (0,\mathcal{S})\gt 0$ . This means that as a result of the threshold changes, a fraction of vertices is infected, and these infected vertices start the percolation process. As before, let $\mathcal{V}\,:\!=\,(\kappa,\nu, \boldsymbol{s} (n),\boldsymbol{r} (n))_{n\in \mathbb{N}}$ .

By construction of $\mathcal{V}$ , where we impose infection on $\widetilde{\mathcal{V}}$ by changing the thresholds of some vertices to zero, we have the following relations for all Borel sets $A \subset \mathcal{S}$ :

(2.9) \begin{align} \widetilde{\nu}(k, A) - \nu (k, A) \geq 0\text{ for } k \geq 1, & \quad \nu(0, A) =\sum_{k=1}^\infty \left( \widetilde{\nu}(k, A) - \nu (k, A) \right).\end{align}

In the same fashion as in (2.1), for subset $A \subset \mathcal{S}$ , we denote the marginal distribution and the Radon–Nikodym derivative by

\begin{align*}\widetilde{\mu}(A) \,:\!=\, \sum_{k=0}^{\infty} \widetilde{\nu}(k, A),&\quad \widetilde{\nu}(k, A) = \int_{A} \widetilde{\eta}_k(s) \,\mathrm{d} \widetilde{\mu}(s).\end{align*}

We now define resilience and non-resilience as follows.

Definition 1. Let $\widetilde{\mathcal{V}}$ be the initial sequence of uninfected vertices and $\mathcal{V}$ be the sequence of vertices with imposed infections. Denote by $G(n, \widetilde{\mathcal{V}})$ and $G(n, \mathcal{V})$ the corresponding random graphs that have the same distribution and differ in thresholds.

We call the random graph $G(n, \widetilde{\mathcal{V}})$ :

1. (i) non-resilient if there exists $\Delta \gt 0 $ depending only on $\widetilde{\nu}$ such that

   \begin{align*}\lim_{n\rightarrow \infty} \mathbb{P} \left(|\mathbb{D}(G(n, \mathcal{V}))|/n \ge \Delta\right)=1;\end{align*}

2. (ii) resilient if for all $\alpha \gt 0$ there exists $\delta \gt 0$ such that

   \begin{align*}\lim_{n\rightarrow \infty} \mathbb{P} \left(|\mathbb{D}(G(n, \mathcal{V}))|/n \lt \alpha \right)=1\end{align*}
   for $0\lt \nu(0,\mathcal{S}) \lt \delta$ .

In other words, for a non-resilient graph, no matter how small the initial infection is, the final fraction of infected vertices will always exceed a certain level, while for a resilient graph, the final fraction of infected vertices is small as long as the initial infection is small. In the following, we provide a condition that allows us to determine whether a random graph is resilient or non-resilient. We introduce the two operators $\widetilde{\Psi}\,:\, \mathcal{F}_{\mathrm{b}} \rightarrow \mathcal{F}_{\mathrm{b}}$ and $\Psi\,:\, \mathcal{F}_{\mathrm{b}} \rightarrow \mathcal{F}_{\mathrm{b}}$ corresponding to the uninfected graph $G(n,\widetilde{\mathcal{V}})$ and the infected graph $G(n,\mathcal{V})$ :

\begin{align*}\widetilde{\Psi} [f](\!\cdot\!) \,:\!=\, \sum_{k=1}^\infty \widetilde{\eta}_k(\!\cdot\!)\left(1- \sum_{k'=0}^{k-1}P_{\kappa}^{k'} [f](\!\cdot\!)\right), \quad \Psi [f](\!\cdot\!) \,:\!=\, \sum_{k=0}^\infty \eta_k(\!\cdot\!)\left(1- \sum_{k'=0}^{k-1}P_{\kappa}^{k'} [f](\!\cdot\!)\right),\end{align*}

where $P_{\kappa}^{k}$ is as defined in (2.4). Note that the summation of $\widetilde{\Psi}$ starts from $k=1$ as $\widetilde{\nu}(0, \mathcal{S}) =0$ . For the operator $\widetilde{\Psi}$ we can calculate the Fréchet derivative $D \widetilde{\Psi}f$ at f as in (2.6). The following theorem provides the resilience condition. Recall that $D \widetilde{\Psi} \boldsymbol{0}[h]$ is the Fréchet derivative of the operator $\widetilde{\Psi}$ at the point $\boldsymbol{0}$ , applied to h.

Theorem 2 (Resilience.) If there exists a continuous and non-negative function $h \in \mathcal{F}_{\mathrm{b}}$ such that:

1. (i) $D \widetilde{\Psi} \boldsymbol{0}[h] \gt h$ , then the graph is non-resilient;

2. (ii) $D \widetilde{\Psi} \boldsymbol{0}[h] \lt h$ , then the graph is resilient.

Moreover, the graph cannot be both non-resilient and resilient, i.e. there is no pair of functions $h, g \in \mathcal{F}_{\mathrm{b}}$ such that $D \widetilde{\Psi}\boldsymbol{0}[h] \gt h$ and $D \widetilde{\Psi}\boldsymbol{0}[g] \lt g$ hold at the same time.

Remark 3. It is worth noting that our notion of resilience is in some cases related to the existence of a giant component. In [Reference Bollobás, Janson and Riordan9, Theorem 3.1] it is shown that a giant component exists if the $\mathcal{L}^2$ norm of the operator $\Lambda_{\kappa}$ is larger than 1. In our model, if all the vertices have a threshold equal to 1, then our condition 1 implies that the $\mathcal{L}^2$ norm of $\Lambda_{\kappa}$ is larger than 1 and the network must have a giant component.

3.1. Final fraction of infected vertices

The proof strategy for Theorem 1 is illustrated in Figure 2. We first consider random graphs with a finite number of vertex types and a bounded threshold (FTBT), denoted by $G(n, \mathcal{V}^{\mathrm{d},\pm}_{L,K})$ , where L denotes the number of types and K denotes the maximal threshold. We then apply results from [Reference Wormald31] to show in Proposition 1 that the final number of infected vertices $|\mathbb{D}(G(n, \mathcal{V}^{\mathrm{d},\pm}_{L,K}))|$ in the FTBT random graph for large n is with high probability close to a solution of an L-dimensional fixed point equation. Next, the FTBT graphs $G(n, \mathcal{V}^{\mathrm{d},\pm}_{L,K})$ are embedded into graphs with a compact type space $\mathcal{S}$ , a stepwise constant kernel, and bounded threshold (SCBT), denoted by $G(n, \mathcal{V}^\pm_{L,K})$ , in such a way that they have the same final number of infected vertices ( $|\mathbb{D}(G(n, \mathcal{V}^{\mathrm{d},\pm}_{L,K}))|=|\mathbb{D}(G(n, \mathcal{V}^\pm_{L,K})|$ ).

Figure 2.

Road map to prove Theorem 1.

The SCBT graphs serve as lower ( $G(n, \mathcal{V}^-_{L,K})$ ) and upper ( $G(n, \mathcal{V}^+_{L,K})$ ) bounds for a graph having the original compact type space $\mathcal{S}$ and kernel with a bounded threshold K (CSBT). These random graphs are denoted by $G(n, \mathcal{V}_{K})$ . We obtain the SCBT graphs for the upper and lower bounds from a sequence of nested partitions of the space $\mathcal{S}$ , indexed by $L \in \mathbb{N}$ . On the basis of this sequence of partitions we can then define stepwise constant coupling kernels $\kappa_L^+$ and $\kappa_L^-$ for each $L \in \mathbb{N}$ . The kernels $\kappa_L^+$ and $\kappa_L^-$ dominate the original $\kappa$ from above and below, and the least fixed points of $\Psi_{\kappa_L^-}$ and $\Psi_{\kappa_L^+}$ converge to the least fixed point of $\Psi_{\kappa}$ . This allows us to couple the CSBT graph $G(n, \mathcal{V}_{K})$ with two sequences of random graphs $G(n, \mathcal{V}^{\pm}_{L,K})$ , one of which, for each random realization, has more edges than $G(n, \mathcal{V}_{K})$ , and the other has fewer edges. This leads to the bounds for the final fraction of infected vertices $|\mathbb{D}(G(n, \mathcal{V}^{-}_{L,K}))| \le |\mathbb{D}(G(n, \mathcal{V}_K))| \le |\mathbb{D}(G(n, \mathcal{V}^{+}_{L,K}))|$ .

In a next step we show that

\begin{align*}\lim_{L \to \infty}||\mathbb{D}(G(n, \mathcal{V}^{-}_{L,K}))|-|\mathbb{D}(G(n, \mathcal{V}^{+}_{L,K}))||=0\end{align*}

and determine $|\mathbb{D}(G(n, \mathcal{V}^{-}_{L,K}))|$ for large n in Proposition 2. This finally leads to the proof of Theorem 1 for $|\mathbb{D}(G(n, \mathcal{V}))|$ , the final infection in the random graph with the compact type space $\mathcal{S}$ and unbounded threshold $G(n, \mathcal{V})$ . One particular challenge in these approximations is that the fixed-point equations that determine $|\mathbb{D}(G(n, \mathcal{V}^{\pm}_{L,K}))|$ increase in dimension with increasing L.

In the first step of the proof, in which we determine the final fraction of infected vertices in the finite-type setting (FTBT) in Proposition 1, we can follow ideas in [Reference Amini, Cont and Minca2, Reference Amini, Fountoulakis and Panagiotou4, Reference Bichuch and Detering8, Reference Detering, Meyer-Brandis, Panagiotou and Ritter14, Reference Detering, Meyer-Brandis, Panagiotou and Ritter15] to apply the concentration results in [Reference Wormald31] to derive the finite-dimensional fixed-point equation that allow us to determine the final outcome of the process. All the remaining ideas of the proof, including the approximations, embeddings, and operator results involved are entirely new.

Definition 2 (Graph with finite vertex type and bounded threshold (FTBT).) For fixed $L,K \in \mathbb{N}$ we consider a random graph with vertices having types in the set $[L]=\{1, \ldots, L\}$ and thresholds $m \in [K] \cup \{0\}=\{0, \ldots, K\}$ . The proportion of vertices with certain threshold and type is described by quantities $(\boldsymbol{\nu}^{l,(n)}_k)_{l \in [L], \ k \in [K] \cup \{0\}}$ , where

\begin{equation*}\boldsymbol{\nu}^{l,(n)}_k = n^{-1}\sum_{i \in [n]} I_{\{k\}}(r_i)I_{\{l\}}(s_i).\end{equation*}

We assume that there exist constants $(\boldsymbol{\nu}^{l}_k )_{l \in [L], \ k \in [K] \cup \{0\}}$ , to which the proportion of vertices with a certain type and threshold converges:

\begin{equation*}\boldsymbol{\nu}^{l,(n)}_k \xrightarrow[n\rightarrow \infty]{} \boldsymbol{\nu}^{l}_k.\end{equation*}

For the connection probability, we define a discrete kernel $\kappa^{\mathrm{d}}_L\,:\, [L]^2 \rightarrow \mathbb{R}$ . Note that we use a superscript d to distinguish the kernel defined on $[L]^2$ from the one defined on $\mathcal{S}^2$ . Then, for vertices $i,j \in [n]$ with types $s_i, s_j \in [L]$ , their connection probability is given by $\min \{ 1, \kappa^{\mathrm{d}}_L (s_i, s_j) /n\}$ . We define the vertex sequence $\mathcal{V}_{L,K}^{\mathrm{d}} =(\kappa^{\mathrm{d}}_L,\nu, \boldsymbol{s} (n),\boldsymbol{r} (n))$ for this graph, and denote by $G(n,\mathcal{V}_{L,K}^{\mathrm{d}})$ the resulting random graph.

For this finite-type vertex sequence, the percolation process can be fully described by the solution of a system of ordinary differential equations (ODEs) of dimension L. The final fraction of infected vertices $n^{-1}|\mathbb{D}(G(n, \mathcal{V}_L^{\mathrm{d}}))|$ is then, for large n, determined from the least joint zero of this system. For $l\in [L]$ and $k\in \mathbb{N}_0$ , with slight abuse of notation, we define the functions $\nu_k^l\,:\, [0,1]^{L} \rightarrow \mathbb{R}$ by

(3.1) \begin{equation}\begin{aligned}\nu_0^l(\textbf{z}) &= - z^l + \nu_{0}^l(\boldsymbol{0}) + \sum_{k'=1}^K \nu_{k'}^l(\boldsymbol{0})\left( 1 - \sum_{k''=0}^{k'-1} p(k'',\lambda^l(\textbf{z})) \right), \\\nu_k^l(\textbf{z}) &= \sum_{k'=k}^K \nu_{k'}^l(\boldsymbol{0}) p(k' -k,\lambda^l(\textbf{z}))\quad \mbox{for all } 1 \le k \le K-1, \\\nu_K^l(\textbf{z}) &= \nu_{K}^l(\boldsymbol{0}) p(0,\lambda^l(\textbf{z})),\end{aligned}\end{equation}

where $\nu_{k}^l(\boldsymbol{0})$ is the initial proportion of vertices with type l and threshold k, $p(k, \lambda) \,:\!=\, \tfrac{\lambda^k}{k!}\mathrm{e}^{-\lambda}$ is a Poisson probability function, $\textbf{z}\,:\!=\,(z^l)_{l \in [L]} \in [0,1]^{L}$ is an L-dimensional vector, and $\lambda^l(\textbf{z}) \,:\!=\, \sum_{l' \in [L]} \kappa^{\mathrm{d}}(l',l) z^{l'}$ . Note that the quantities $\textbf{z}$ , $\lambda$ , and $p(k, \lambda)$ are the discrete counterparts of the operators f, $\Lambda$ , and P defined in (2.4). In a sequential formulation introduced in Appendix A, $\nu_{k}^l$ tracks the proportion of type l vertices that need k more infected neighbors to become infected. The argument vector contains for each type $l\in [L]$ the fraction of vertices of this type that are infected and whose impact on the system has already been explored.

Define the least joint zero as

(3.2) \begin{align}\widehat{\textbf{z}} \,:\!=\, \operatorname*{min} \left\{ \textbf{z}\in [0,1]^{L} \,:\,\big( \nu_0^l(\textbf{z}) \big)_{l\in [L]}= \boldsymbol{0} \right\},\end{align}

where the minimum is with respect to the partial order obtained from the componentwise comparison $\le$ . The existence of $\widehat{\textbf{z}}$ follows from the Knaster–Tarski fixed-point theorem. The following proposition determines the final fraction of infected vertices in $G(n,\mathcal{V}^{\mathrm{d}}_{L,K})$ .

Proposition 1 (Final fraction of infected vertices for a graph with finite vertex type (FTBT).) Let $\nu (0,\mathcal{S})\gt 0$ and let $\widehat{\textbf{z}}$ be the least fixed point defined in (3.2). If for some vector $(w^l)_{l \in [L]} \gt \boldsymbol{0}$ and $\sum_{l\in[L]} w^l \le 1$ , the condition

(3.3) \begin{align} \sum_{l' \in [L]} w^{l'} \frac{\partial \nu_0^l(\widehat{\textbf{z}})}{\partial z^{l'}} \lt 0 \quad \textit{for}\;\textit{all}\; l \in [L]\end{align}

holds for the graph with finite vertex type $G(n,\mathcal{V}_{L,K}^{\mathrm{d}})$ , then it holds that

\begin{align*}n^{-1}|\mathbb{D}(G(n,\mathcal{V}_{L,K}^{\mathrm{d}}))| \xrightarrow[n\rightarrow\infty]{p} \sum_{l\in [L]} \widehat{z}^l.\end{align*}

Remark 4. If the condition (3.3) does not hold then still for every $\varepsilon\gt 0$

\begin{align*}\lim_{n\rightarrow \infty} \mathbb{P}\left( n^{-1}|\mathbb{D}(G(n,\mathcal{V}_{L,K}^{\mathrm{d}}))|\ge \sum_{l\in[L]} \widehat{z}^l -\varepsilon \right)=1.\end{align*}

For a given FTBT random graph sequence $\mathcal{V}_{L,K}^{\mathrm{d}} =(\kappa^{\mathrm{d}}_L,\nu, \boldsymbol{s} (n),\boldsymbol{r} (n))$ , we may define a partition $\{\mathcal{S}_L^l\}_{l \in [L]}$ of the compact type space $\mathcal{S}$ and a measure $\nu\,:\, [K]\cup \{0\} \times \mathcal{S} \to \mathbb{R}_+$ such that $\nu(k, \mathcal{S}_L^l) = \nu_k^l$ for all $k \in [K]\cup \{0\}$ and $l \in [L]$ . Let $\mu(\!\cdot\!) = \sum_{k=0}^K \nu(k, \cdot)$ . The finite-dimensional description of the graph $G(n,\mathcal{V}^{d}_{L,K})$ can then be related to the operator $\Psi_{\kappa_L}$ of an SCBT graph $G(n,\mathcal{V}_{L,K})$ that has a piecewise constant kernel $\kappa_L\,:\, \mathcal{S} \times \mathcal{S} \to \mathbb{R}_+$ .

Definition 3 (Embedding graph.) For a partition $\{\mathcal{S}_L^l\}_{l \in [L]}$ define the stepwise kernel $\kappa_L(s, s')\,:\, \mathcal{S} \times \mathcal{S} \rightarrow \mathbb{R}$ and the vertex sequence $\mathcal{V}_{L,K}$ by

\begin{align*}\kappa_L(s, s') \,:\!=\,\sum_{l,l' \in L} I_{\mathcal{S}^l}(s) I_{\mathcal{S}^{l'}}(s') \kappa^{\mathrm{d}}_L(l, l'),&\quad \mathcal{V}_{L,K} \,:\!=\, (\kappa_L, \nu, (\boldsymbol{s}(n), \boldsymbol{r}(n))).\end{align*}

Then the resulting graph $G(n, \mathcal{V}_{L,K})$ is called the embedding graph of $G(n, \mathcal{V}^{\mathrm{d}}_{L,K})$ .

By construction, $G(n, \mathcal{V}^{\mathrm{d}}_{L,K})$ and $G(n, \mathcal{V}_{L,k})$ have the same distribution, and by coupling the two random graphs, we may even ensure that $|\mathbb{D}(G(n,\mathcal{V}_{L, K}))|=|\mathbb{D}(G(n, \mathcal{V}^{\mathrm{d}}_{L,K})|$ . This allows us to extend the result of Proposition 1 for FTBT graphs to SCBT graphs. The functionals (3.1) for $G(n, \mathcal{V}^{\mathrm{d}}_{L,K})$ and the functionals (2.4) for $G(n, \mathcal{V}_{L,k})$ are related in the following sense: For the vector $\textbf{z}_L=(z_L^1, \ldots , z_L^L) \in [0,1]^{L}$ , define a finite-dimensional function $f_L(s)\,:\, \mathcal{S} \rightarrow [0,1]$ by

(3.4) \begin{align}f_L(s) \,:\!=\, \sum_{l \in [L]} \frac{1}{\mu(\mathcal{S}_L^l)} z_L^l I_{\mathcal{S}_L^l}(s).\end{align}

Then by the definition of $f_L$ , it holds that $P_{\kappa}^k [f_L](s)=p(k,\lambda^l (\textbf{z}_L))$ for $s\in \mathcal{S}_L^l$ and any $k \in [K] \cup\{0\}$ . This implies

(3.5) \begin{equation}\begin{aligned}\nu_0^l(\textbf{z}_L) &= - z_L^l + \sum_{k'=0}^K \nu_{k'}^l(\boldsymbol{0}) \left( 1 - \sum_{k''=0}^{k'-1} p(k'',\lambda^l(\textbf{z}_L))\right) \\ &= - \int_{\mathcal{S}_L^l} f_L(s) \mathrm{d} \mu(s) + \int_{\mathcal{S}_L^l}\Psi_{\kappa_L} [f_L](s) \mathrm{d} \mu(s)\end{aligned}\end{equation}

for all $l\in [L]$ , where $\nu_0^l(\textbf{z}_L)$ and $\nu_k^l(\boldsymbol{0})$ are defined in (3.1), and we also used that $\nu_{k}^l(\boldsymbol{0}) =\int_{\mathcal{S}_L^l} \eta_k (s) \mathrm{d} \mu(s)$ . Because all fixed points of $\Psi_{\kappa_L}$ are step functions by Lemma 7, the first zero $\widehat{\textbf{z}}_L$ of $(\nu_0^l(\textbf{z}))_{l\in [L]}$ and the first fixed point $\hat{f}_L$ of $\Psi_{\kappa_L}$ are related by

(3.6) \begin{align}\hat{f}_L(s)\,:\!=\, \sum_{l \in [L]} \frac{1}{\mu(\mathcal{S}_L^l)} \widehat{z}_L^l I_{\mathcal{S}_L^l}(s),&\quad \sum_{l \in [L]} \widehat{z}_L^l = \int_{\mathcal{S}} \hat{f}_L (s) \mathrm{d} \mu(s).\end{align}

Moreover, for $0\lt w_l\lt 1, \ \sum_{l \in [L]} w_j = 1$ , and $h_L\in \mathcal{F}_{\mathrm{b}}$ defined by

\begin{align*}h_L(s) \,:\!=\, \sum_{l \in [L]} \tfrac{1}{\mu(\mathcal{S}_L^l)}w^l I_{\mathcal{S}_L^l}(s),\end{align*}

it holds that

(3.7) \begin{equation}\begin{aligned}\sum_{l' \in [L]} w^{l'} \frac{\partial \nu_0^l(\textbf{z}_L)}{\partial z^{l'}} &= - w^l + \left(\sum_{l' \in [L]} \kappa_L^{\mathrm{d}}(l',l) w^{l'}\right) \nu_1^l(\textbf{z}_L) \\ &= - \int_{\mathcal{S}_L^l} h_L(s) \mathrm{d} \mu(s) + \int_{\mathcal{S}_L^l} D \Psi_{\kappa_L} f_L [h_L] (s) \mathrm{d} \mu(s).\end{aligned}\end{equation}

On the left-hand side we have the directional derivative of the multivariate function $(\nu_0^l(\textbf{z}))_{l\in [L]}$ , while on the right-hand side we have an expression that involves the Fréchet derivative in the direction $h_L$ . The identity will allow us to derive stopping criteria for the percolation process in $G(n,\mathcal{V}_{L,K})$ from the Fréchet derivative of $\Psi_{\kappa}$ .

Because of the equalities (3.5), (3.6), and (3.7) we say that $G(n,\mathcal{V}^{\mathrm{d}}_{L,K})$ is embedded into $G(n,\mathcal{V}_{L, K})$ . This embedding will allow us to describe the final default fraction $|\mathbb{D}(G(n,\mathcal{V}_{L, K}))|=|\mathbb{D}(G(n, \mathcal{V}^{\mathrm{d}}_{L,K})|$ in terms of the functionals (2.4) for $G(n,\mathcal{V}_{L, K})$ . We next apply this observation to analyze the lower and upper bounds of the final fraction of infected vertices in CSBT graphs by constructing its coupling graphs. For this we first specify a sequence of partitions for $\mathcal{S}$ based on the following lemma. Let $d\,:\, \mathcal{S} \times \mathcal{S} \to \mathbb{R}_+$ be the metric of the type space $\mathcal{S}$ , and for subset $\mathcal{R} \subset \mathcal{S}$ , define $\mathrm{diam}(\mathcal{R})\,:\!=\, \sup_{x, y \in \mathcal{R}} d(x,y)$ .

For a CSBT graph $G(n, \mathcal{V}_K)$ , we construct two sequences of coupling SCBT graphs, indexed by $L \in \mathbb{N}$ , $G(n, \mathcal{V}_{L, K}^-)$ , and $G(n, \mathcal{V}_{L, K}^+)$ as follows. In the following we often drop the dependence of L on m to simplify notation.

Definition 4 (Coupling graphs.) Let $\{\mathcal{S}_{L(m)}^l\}_{l \in [L(m)]}$ be a sequence of partitions for the type space $\mathcal{S}$ according to Lemma 5. In the following we omit m and just write L. For each L, define the lower coupling graph $G(n, \mathcal{V}_{L, K}^-)$ and the upper coupling graph $G(n, \mathcal{V}_{L, K}^+)$ as random graphs with vertex sequences $\mathcal{V}_{L, K}^-\,:\!=\,(\kappa_L^-,\nu, \boldsymbol{s} (n),\boldsymbol{r} (n))$ and $\mathcal{V}_{L, K}^+\,:\!=\,(\kappa_L^+,\nu, \boldsymbol{s} (n),\boldsymbol{r} (n))$ , where the stepwise kernels $\kappa_L^{\pm}(s, s')$ are given by

\begin{align*}\kappa_L^+(s, s') &\,:\!=\, \sum_{l,l' \in [L]} I_{\mathcal{S}_L^l}(s) I_{\mathcal{S}_L^{l'}}(s') \mathop{\sup}\nolimits_{x \in \mathcal{S}_L^l, y \in \mathcal{S}_L^{l'}} \kappa(x,y), \\\kappa_L^-(s, s') &\,:\!=\, \sum_{l,l' \in [L]} I_{\mathcal{S}_L^l}(s) I_{\mathcal{S}_L^{l'}}(s') \inf_{x \in \mathcal{S}_L^l, y \in \mathcal{S}_L^{l'}} \kappa(x,y).\end{align*}

Moreover, edges of $G(n, \mathcal{V}_{L, K}^{\pm})$ are generated as follows. For any pair of vertices $i,j \in [n]$ in a graph G, let $E_{ij}(G)$ be the binary indicator that i connects to j. For $i,j \in [n]$ , $i\neq j$ , let $U_{ij} \sim \textit{Uniform([0,1])}$ , $E_{ij}(G(n, \mathcal{V}_{L, K}^-)) = I_{\{U_{ij} \le \kappa_L^- (s_i, s_j)\}}$ , $E_{ij}(G(n, \mathcal{V})) = I_{\{U_{ij} \le \kappa(s_i, s_j)\}}$ , and $E_{ij}(G(n, \mathcal{V}_{L, K}^+)) = I_{\{U_{ij} \le \kappa_L^+ (s_i, s_j)\}}$ .

By construction of the coupling graphs it holds by $\kappa_L^- \le \kappa \le \kappa_L^+$ that

\begin{align*}\mathbb{P}(E_{ij}(G(n, \mathcal{V}_{L, K}^-)) \le E_{ij}(G(n, \mathcal{V}_K)) \le E_{ij}(G(n, \mathcal{V}_{L, K}^+)))=1\end{align*}

as desired, and it follows that

\begin{align*}\mathbb{P}(|\mathbb{D}(G(n, \mathcal{V}_{L, K}^-))| \le |\mathbb{D}(G(n, \mathcal{V}_K))| \le |\mathbb{D}(G(n, \mathcal{V}_{L, K}^+))|)=1.\end{align*}

Note that $G(n, \mathcal{V}_{L, K}^{\pm})$ embeds $G(n, \mathcal{V}_{L, K}^{\mathrm{d}, \pm})$ , and we have $|\mathbb{D}(G(n, \mathcal{V}_{L, K}^\pm))|=|\mathbb{D}(G(n, \mathcal{V}_{L, K}^{\mathrm{d},\pm}))|$ . Then $|\mathbb{D}(G(n, \mathcal{V}_L^{\mathrm{d},\pm}))|$ can be determined on the basis of the least joint zeros of the functions in (3.1). The embedding relations in (3.6) and (3.7) allow us to connect the finite-dimensional discrete description to the operators $\Psi_{\kappa_L^\pm}$ . We expect that

\begin{align*}\lim_{L \to \infty}||\mathbb{D}(G(n, \mathcal{V}_{L, K}^-))| - |\mathbb{D}(G(n, \mathcal{V}_{L, K}^+))||=0.\end{align*}

This can be shown with the convergence of the operators $\Psi_{\kappa_L^\pm}$ to $\Psi_{\kappa}$ on $\mathcal{F}_{\mathrm{b}}$ as $L \rightarrow \infty$ , as well as the convergence of their fixed points, provided in the following two lemmas.

Lemma 6 (Uniform convergence.) For $f, h \in \mathcal{F}_{\mathrm{b}}$ and a monotone sequence $\{\,f_L\}_{L\in \mathbb{N}} \in \mathcal{F}_{\mathrm{b}}$ such that $f_L \rightarrow f$ pointwise as $L \rightarrow \infty$ , it holds that

\begin{align*}\Psi_{\kappa_L^\pm} f_L \rightarrow \Psi_{\kappa} f,&\quad D \Psi_{\kappa_L^\pm} f_L[h] \rightarrow D \Psi_{\kappa} f[h]\end{align*}

uniformly in $\mathcal{S}$ .

Lemma 7 (Uniform convergence of fixed points.) Assume that a least fixed point $\hat{f}$ of $\Psi_{\kappa}$ exists and that there exists a non-negative continuous function $h \in \mathcal{F}_{\mathrm{b}}$ and small $\epsilon \gt 0$ such that $D \Psi_{\kappa} \hat{f} [h] - h \lt - \epsilon \boldsymbol{1}$ . Then each of the $\Psi_{\kappa^\pm_L}$ has a least fixed point, denoted by $\hat{f}_L^\pm$ . The fixed point $\hat{f}_L^\pm$ is a step function that is constant on the sets $\{\mathcal{S}^l_L \}_{l\in L}$ . Moreover, as $L \rightarrow \infty$ , the following convergences hold:

\begin{align*}\hat{f}_L^\pm \rightarrow \hat{f} \textit{ uniformly}, &\quad D \Psi_{\kappa^\pm_L} \hat{f}_L^\pm [h]\rightarrow D \Psi_{\kappa} \hat{f} [h] \textit{ uniformly}, & \int_{\mathcal{S}}\hat{f}_L^\pm \mathrm{d} \mu \rightarrow \int_{\mathcal{S}} \hat{f} \mathrm{d} \mu.\end{align*}

The following proposition determines the final fraction of infected vertices of $G(n, \mathcal{V}_K)$ .

Proposition 2 (Final fraction of infected vertices for a graph with a bounded threshold (CSBT).) Let $\hat{f}_K$ be the least fixed point of $\Psi_{\kappa}$ . Assume that for some positive continuous function $h \in \mathcal{F}_{\mathrm{b}}$ and small $\epsilon\gt 0$ the following derivative condition holds:

(3.8) \begin{align} D \Psi_{\kappa} \hat{f}_K [h] - h \lt - \epsilon \boldsymbol{1}.\end{align}

Then the final fraction of infected vertices in $G(n,\mathcal{V}_K)$ converges:

\begin{align*}n^{-1}|\mathbb{D}(G(n,\mathcal{V}_K))|\xrightarrow[n\rightarrow \infty]{p} \int_{\mathcal{S}} \hat{f}_K \mathrm{d} \mu.\end{align*}

Proof. For $G(n,\mathcal{V}_{K})$ , build the coupling graphs $G(n,\mathcal{V}_{L,K}^\pm)$ as specified in Definition 4. It then holds for the final fraction of infected vertices $|\mathbb{D}(G(n,\mathcal{V}_{K}))|$ that

(3.9) \begin{align} \mathbb{P}(|\mathbb{D}(G(n, \mathcal{V}_{L,K}^-))| \le |\mathbb{D}(G(n, \mathcal{V}_K))| \le |\mathbb{D}(G(n, \mathcal{V}_{L,K}^+))|)=1.\end{align}

Let $\hat{f}^\pm_{L,K}$ be the least fixed points of $G(n,\mathcal{V}_{L,K}^\pm)$ , which by Lemma 7 are step functions. Construct the corresponding embedded finite-type graphs $G(n,\mathcal{V}_{L,K}^{\mathrm{d},\pm})$ and let $\widehat{\textbf{z}}^\pm_{L,K}$ be the corresponding least joint zeros as defined in (3.2). The relation between the operator of $G(n,\mathcal{V}_{L,K}^\pm)$ and that of $G(n,\mathcal{V}_{L,K}^{\mathrm{d},\pm})$ is shown in (3.4)–(3.6) when we replace ( $\kappa_L$ , $f_L$ , $\kappa^{\mathrm{d}}_L$ , $\textbf{z}_L$ ) with ( $\kappa^\pm_L$ , $\hat{f}^\pm_{L,K}$ , $\kappa^{\mathrm{d}, \pm}_L$ , $\widehat{\textbf{z}}^\pm_{L,K}$ ). We will use such replacement throughout this proof whenever we refer to those equations.

By Lemma 7, there exists an $L_0 \in \mathbb{N}$ such that $\|D\Psi_{\kappa^\pm_L}\hat{f}^\pm_{L,K}[h] - D\Psi_{\kappa} \hat{f}_K[h]\|_\infty \lt \epsilon/2$ for $L \ge L_0$ . Then with the inequality (3.8) it follows that

(3.10) \begin{align}D\Psi_{\kappa^\pm_L}\hat{f}^\pm_{L,K}[h] - h &= \big(D\Psi_{\kappa^\pm_L}\hat{f}^\pm_{L,K}[h] - D\Psi_{\kappa} \hat{f}_K [h]\big) + (D\Psi_{\kappa} \hat{f}_K[h] - h) \nonumber\\ & \lt \Big(\frac{\epsilon}{2} - \epsilon\Big) \boldsymbol{1} = - \frac{\epsilon}{2} \boldsymbol{1}.\end{align}

If we let $L \ge L_0$ and combine (3.7) with (3.10), we obtain

\begin{align*}\sum_{l' \in [L]} w^{l'} \frac{\partial \nu_0^l(\widehat{\textbf{z}}^\pm_{L,K})}{\partial z^{l'}} \lt - \frac{\epsilon}{2} \quad \mbox{for all } l \in [L],\end{align*}

which is the condition that allows us to apply Proposition 1 to $G(n,\mathcal{V}_{L,K}^{\mathrm{d},\pm})$ . Therefore, the final fraction of infected vertices of the embedded graph with finite vertex types converges:

(3.11) \begin{align} n^{-1}|\mathbb{D}(G(n,\mathcal{V}^\pm_{L,K}))| \xrightarrow[n\rightarrow \infty]{p} \sum_{l\in[L]} \widehat{z}^{\pm, l}_{L,K} = \int_{\mathcal{S}} \hat{f}^\pm_{L,K} \mathrm{d} \mu,\end{align}

where we use (3.6) on the right-hand side. Finally, we recall the inequality (3.9), and apply the convergence lemma (Lemma 7) to (3.11) to obtain

\begin{align*} n^{-1}|\mathbb{D}(G(n,\mathcal{V}_{L,K}^+))| \xrightarrow[n\rightarrow \infty]{p} \int_{\mathcal{S}} \hat{f}^+_{L,K} \mathrm{d} \mu \xrightarrow[L \rightarrow \infty]{} \int_{\mathcal{S}} \hat{f}_K \mathrm{d} \mu, \\ n^{-1}|\mathbb{D}(G(n,\mathcal{V}_{L,K}^-))| \xrightarrow[n\rightarrow \infty]{p} \int_{\mathcal{S}} \hat{f}^-_{L,K} \mathrm{d} \mu \xrightarrow[L \rightarrow \infty]{} \int_{\mathcal{S}} \hat{f}_K \mathrm{d} \mu,\end{align*}

and hence the result follows.

Finally, given the above results, we are now able to prove Theorem 1.

Proof of Theorem 1. Note that $\sum_{k=1}^{\infty} \nu(k,\mathcal{S}) = 1$ implies that for all $\epsilon \gt 0$ there is a $K_0 \in \mathbb{N}$ such that for $K \ge K_0$ we have $\sum_{k=K+1}^{\infty} \nu(k, \mathcal{S}) \lt \epsilon$ . Define $\epsilon_{K}(\!\cdot\!)\;:\; \mathcal{S} \rightarrow [0,1]$ by

\begin{align*}\epsilon_{K}(\!\cdot\!) \,:\!=\, \sum_{k=K+1}^{\infty} \nu (k, \cdot), &\quad \epsilon_{K} \equiv \epsilon_{K}(\mathcal{S}),\end{align*}

and note that $\lim_{K \rightarrow \infty }\epsilon_{K} =0$ . We build an upper coupling graph $G(n,\overline{\mathcal{V}}_K)$ and a lower coupling graph $G(\lfloor(1-\epsilon_K)n\rfloor,\underline{\mathcal{V}}_K)$ with vertex sequences $\overline{\mathcal{V}}_K \,:\!=\, (\kappa,\overline{\nu}^K,(\boldsymbol{s} (n),\boldsymbol{r} (n))$ and $\underline{\mathcal{V}}_K \,:\!=\, (\kappa,\underline{\nu}^K,(\boldsymbol{s} (\lfloor(1-\epsilon_K)n\rfloor),\boldsymbol{r} (\lfloor(1-\epsilon_K)n\rfloor)$ . Their vertex distributions are

\begin{align*}\overline{\nu}^K(k,\cdot) = \begin{cases} \nu(k,\cdot), & 0\le k \le K-1, \\ \sum_{k'=K}^{\infty} \nu(k',\cdot), & k = K, \end{cases} \quad \underline{\nu}^K(k,\cdot) = \frac{\nu(k, \cdot)}{1 - \epsilon_K}, \quad & 0 \le k \le K.\end{align*}

For $G(n,\overline{\mathcal{V}}_K)$ , we clip the largest thresholds to K by mapping all vertices in $G(n,\mathcal{V})$ with threshold $k \ge K$ into vertices with only threshold K in $G(n,\overline{\mathcal{V}}_K)$ . Hence, $G(n,\overline{\mathcal{V}}_K)$ is more vulnerable to infection than $G(n,\mathcal{V})$ . For the sequence $\underline{\mathcal{V}}_K$ , we exclude vertices with thresholds larger than K. Their proportion is $\epsilon_K$ . We then consider the graph $G(\lfloor(1-\epsilon_K)n\rfloor,\underline{\mathcal{V}}_K)$ with only $(1- \epsilon_K)n$ vertices. This is equivalent to considering a graph with n vertices in which the vertices with large threshold values are considered non-infectable. Hence, in absolute numbers $G(\lfloor(1-\epsilon_K)n\rfloor,\underline{\mathcal{V}}_K)$ has fewer infected vertices than $G(n,\mathcal{V})$ . Consequently, by such a construction and again a coupling argument, we have the following inequality:

(3.12) \begin{align} \mathbb{P}(n^{-1}|\mathbb{D}(G(\lfloor(1-\epsilon_K)n\rfloor,\underline{\mathcal{V}}_K))| \le n^{-1}|\mathbb{D}(G(n,\mathcal{V}))| \le n^{-1}|\mathbb{D}(G(n,\overline{\mathcal{V}}_K))|)=1.\end{align}

The operators for $G(n,\overline{\mathcal{V}}_K)$ and $G(\lfloor(1-\epsilon_K)n\rfloor,\underline{\mathcal{V}}_K)$ are given by

\begin{align*}\overline{\Psi}_K [f](\!\cdot\!) &\,:\!=\, \sum_{k=0}^K \frac{\mathrm{d} \overline{\nu}^K(k, \cdot)}{\mathrm{d} \overline{\mu}^K(\!\cdot\!)}\left(1- \sum_{k'=0}^{k-1}P^{k'} [f](\!\cdot\!)\right), \\\underline{\Psi}_K [f](\!\cdot\!) &\,:\!=\, \sum_{k=0}^K \frac{\mathrm{d} \underline{\nu}^K(k, \cdot)}{\mathrm{d} \underline{\mu}^K(\!\cdot\!)}\left(1- \sum_{k'=0}^{k-1}P^{k'} [f](\!\cdot\!)\right).\end{align*}

The graphs $G(n,\overline{\mathcal{V}}_K)$ and $G(\lfloor(1-\epsilon_K)n\rfloor,\underline{\mathcal{V}}_K)$ are CSBT random graphs, and we can therefore determine $|\mathbb{D}(G(\lfloor(1-\epsilon_K)n\rfloor,\underline{\mathcal{V}}_K))|$ and $|\mathbb{D}(G(n,\overline{\mathcal{V}}_K))|$ with Proposition 2. Using essentially the same techniques as used in Lemmas 6 and 7, we can easily show the existence of the least fixed points $\overline{f}_K$ (respectively $\underline{f}_K$ ) for $\overline{\Psi}_K$ (resp. $\underline{\Psi}_K$ ), and further prove the following convergence for $K\rightarrow \infty$ :

(3.13) \begin{equation} \begin{aligned}\overline{f}_K, \underline{f}_K \rightarrow \hat{f} \text{ uniformly}, \quad D \overline{\Psi}_{K} \overline{f}_K[h], D \underline{\Psi}_{K} \underline{f}_K[h] \rightarrow D \Psi_\kappa \hat{f} [h] \text{ uniformly},\end{aligned}\end{equation}

and

\begin{align*}\int_{\mathcal{S}}\overline{f}_K, \int_{\mathcal{S}}\underline{f}_K \rightarrow \int_{\mathcal{S}} \hat{f}.\end{align*}

Finally, by the condition (2.7) on the derivative $D \Psi_\kappa$ , the second convergence in (3.13) implies that $D \overline{\Psi}_{K}$ and $D \underline{\Psi}_{K}$ satisfy such a derivative condition for K large. Therefore, applying Proposition 2, we obtain

\begin{align*}\frac{|\mathbb{D}(G(\lfloor(1-\epsilon_K)n\rfloor ,\underline{\mathcal{V}}_K))|}{(1-\epsilon_K)n} \xrightarrow[n\rightarrow \infty]{p} \int_{\mathcal{S}} \underline{f}_K \xrightarrow[K\rightarrow \infty]{} \int_{\mathcal{S}} \hat{f} \xleftarrow[K\rightarrow \infty]{} \int_{\mathcal{S}} \overline{f}_K \xleftarrow[n\rightarrow \infty]{p} \frac{|\mathbb{D}(G(n,\overline{\mathcal{V}}_K))|}{n}.\end{align*}

Then, together with use of the inequality (3.12) and $\epsilon_K \rightarrow 0$ , (2.8) follows.

3.2. Resilience

For the proof of non-resilience, we first note that the existence of a function $h\in \mathcal{F}_{\mathrm{b}}$ such that $D \widetilde{\Psi} \boldsymbol{0}[h] \gt h$ implies by continuity of the derivative that there exists $\alpha \gt 0$ such that $\widetilde{\Psi}[a h] \gt 0$ for $a \in (0, \alpha ]$ . We will then see that for the operator $\Psi $ of the infected network it holds that $\Psi [a h] \geq \widetilde{\Psi}[a h] \gt 0$ for $a \in (0, \alpha ]$ . The next lemma ensures that a fixed point $\hat{f}$ of $\Psi$ (if any) is such that $\hat{f} \geq \alpha h$ , which will provide the lower bound. Recall the definition of $\mathcal{F}_1^{\mathrm{c}}$ in (2.5).

To show resilience, we use Lemma 6 together with the embedding (3.7) to derive upper approximating kernels $\kappa_L^+$ and coupling graphs $G(n,\mathcal{V}_L^+)$ . The derivative condition then allows us to show that the expected infection across all generations of the process is bounded by $C \nu(0, \mathcal{S})$ , where $C\gt 0$ results from a geometric series. A simple Markov estimate then provides the bound for $|\mathbb{D}(G(n,\mathcal{V}_L^+))|$ (see Proposition 5).

Proof of Theorem 2. Note that $\boldsymbol{0}$ is a fixed point of $\widetilde{\Psi}$ . First, for part (i), we show that, given the inequality condition, there exists another fixed point $\widetilde{f} \in \mathcal{F}_{\mathrm{b}}$ of $\widetilde{\Psi}$ with $\widetilde{f}\gt \boldsymbol{0}$ , which provides the lower bound of the total infected proportion for $G(n,\mathcal{V})$ . For such h, we can take a small $\epsilon \gt 0$ such that

(3.14) \begin{align} D \widetilde{\Psi}\boldsymbol{0}h(\!\cdot\!) &=\Lambda_{\kappa} [h] (\!\cdot\!)\sum_{k=1}^\infty \widetilde{\eta}_k(\!\cdot\!) P_{\kappa}^{k-1}[\boldsymbol{0}] (\!\cdot\!) \nonumber\\ &= \Lambda_{\kappa} [h] (\!\cdot\!)\widetilde{\eta}_1(\!\cdot\!) \gt (1-\epsilon) \Lambda_{\kappa} [h] (\!\cdot\!) \widetilde{\eta}_1(\!\cdot\!) \gt h(\!\cdot\!),\end{align}

where $\eta_k$ is the Radon–Nikodym derivative defined in (2.1). Then, if we take $a \in (0,1)$ , by the mean value theorem, there exists a $\xi \in (0,1)$ such that

\begin{align*}\widetilde{\Psi} [\boldsymbol{0} + ah] - \widetilde{\Psi} \boldsymbol{0} &= D\widetilde{\Psi} [\xi ah] [ah] = \Lambda_{\kappa} [ah] \sum_{k=1}^\infty\widetilde{\eta}_k P_{\kappa}^{k-1}[\xi ah]\\ &= a\Lambda_{\kappa}[h] \widetilde{\eta}_1 \sum_{k=1}^\infty \frac{\widetilde{\eta}_k }{\widetilde{\eta}_1 } P_{\kappa}^{k-1}[\xi ah] \\ &\ge a\Lambda_{\kappa}[h] \widetilde{\eta}_1 P_{\kappa}^{0}[\xi ah] = a\Lambda_{\kappa}[h] \widetilde{\eta}_1 \mathrm{e}^{- \xi a \Lambda_\kappa h}.\end{align*}

Since $\mathrm{e}^{- \xi 0 \Lambda_\kappa h} = \boldsymbol{1}$ and $\mathrm{e}^{- \xi a \Lambda_\kappa h}$ is continuous in a and h is bounded, there exists a small neighborhood $(0, a_\epsilon] \subset (0, 1)$ such that $\mathrm{e}^{- \xi a \Lambda_\kappa h(s)} \ge 1-\epsilon$ for all $a \in (0, a_\epsilon]$ and $s \in \mathcal{S}$ . Therefore, with the inequality (3.14), we obtain

\begin{align*}\widetilde{\Psi}[ah] \gt a\Lambda_{\kappa}[h] \widetilde{\eta}_1(\!\cdot\!) (1- \epsilon) \gt a h \mbox{ for all } a \in (0, a_\epsilon].\end{align*}

Then, expanding the expression for $\Psi[ah]$ and using the relations for $\eta_k$ and $\widetilde{\eta}_k$ indicated by (2.9), we derive the following inequality:

\begin{align*}\Psi[ah] &= \sum_{k=0}^\infty \eta_k\left(1- \sum_{k'=0}^{k-1}P_{\kappa}^{k'} [ah]\right) \\ &= \sum_{k=0}^\infty (\eta_k - \widetilde{\eta}_k)\left(1- \sum_{k'=0}^{k-1}P_{\kappa}^{k'} [ah]\right) + \sum_{k=0}^\infty \widetilde{\eta}_k\left(1- \sum_{k'=0}^{k-1}P_{\kappa}^{k'} [ah]\right)\\ &= \eta_0 + \sum_{k=1}^\infty (\eta_k - \widetilde{\eta}_k)\left(1- \sum_{k'=0}^{k-1}P_{\kappa}^{k'} [ah]\right) + \widetilde{\Psi}[ah]\\ &= \sum_{k=1}^\infty (\widetilde{\eta}_k - \eta_k) + \sum_{k=1}^\infty (\eta_k - \widetilde{\eta}_k)\left(1- \sum_{k'=0}^{k-1}P_{\kappa}^{k'} [ah]\right) + \widetilde{\Psi}[ah]\\ &= \sum_{k=1}^\infty (\widetilde{\eta}_k - \eta_k)\sum_{k'=0}^{k-1}P_{\kappa}^{k'} [ah] + \widetilde{\Psi}[ah] \ge \widetilde{\Psi}[ah] \gt ah.\end{align*}

By Lemma 8, we know that $\Psi$ does not have a fixed point between $\boldsymbol{0}$ and $a_\epsilon h$ . Therefore, by Theorem 1, the final fraction of infected vertices of $G(n, \mathcal{V})$ must be greater than $\alpha \,:\!=\, \int_{\mathcal{S}} a_{\epsilon} h \mathrm{d} \mu$ , where $\alpha$ is independent of the imposed infection $\nu_0$ . Hence, we have shown the non-resilient case (i).

For the resilient case (ii), we first observe that

\begin{align*}D \widetilde{\Psi}\boldsymbol{0} [h] = \Lambda_{\kappa} [h] \widetilde{\eta}_1 \ge \Lambda_{\kappa} [h] \eta_1 =D \Psi\boldsymbol{0} [h],\end{align*}

which implies that $D \Psi\boldsymbol{0} [h] \lt h $ by the assumption in (ii). Because $D\Psi \boldsymbol{0} [h]$ and h are continuous, it follows that $D\Psi \boldsymbol{0} [h] - h$ is continuous, and therefore attains a maximum. Thus, we can find $\epsilon^*$ sufficiently small such that

\begin{align*}D\Psi \boldsymbol{0} [h] - h \lt -\epsilon^*.\end{align*}

Following the approximation in Section 3.1, we may find a sequence $\{\mathcal{S}_{L}^l\}_{l \in [L]}$ of partitions for the type space $\mathcal{S}$ , and coupling kernels $\kappa^+_L\geq \kappa $ , such that

\begin{align*}\|D\Psi_{\kappa^+_L} \boldsymbol{0} [h] - D\Psi \boldsymbol{0} [h]\|_\infty \lt \frac{\epsilon^*}{2}\end{align*}

for $L\geq L_0$ . For each L, let $h_L (s) = \sum_{l \in [L]} I_{\mathcal{S}_L^l}(s)\sup_{x \in \mathcal{S}_L^l} h(x)$ . By continuity of the function $h\mapsto D \Psi\boldsymbol{0} [h]$ there exists $L_1\gt 0$ such that $\|D\Psi_{\kappa^+_L} \boldsymbol{0} [h] - D\Psi_{\kappa^+_L} \boldsymbol{0} [h_L]\|_\infty \lt {\epsilon^*}/{4}$ for $L\geq L_1$ . It follows that $\|D\Psi_{\kappa^+_L} \boldsymbol{0} [h_L] - D\Psi \boldsymbol{0} [h]\|_\infty \lt {3\epsilon^*}/{4}$ for $L \geq \max \{L_0,L_1 \}$ . This implies that

\begin{align*}D\Psi_{\kappa^+_L} \boldsymbol{0} [h_L] - h_L \lt -\frac{\epsilon^*}{4}.\end{align*}

By the embedding results in the previous section, it follows from (3.7) for the discrete counterpart $\kappa^{\mathrm{d},+}_L$ of the kernel $\kappa^{+}_L$ that

\begin{align*}\sum_{l' \in [L]} w^{l'} \frac{\partial \nu_0^l(\boldsymbol{0}_L)}{\partial z^{l'}} &= - w^l + \left(\sum_{l' \in [L]} \kappa^+_L(l',l) w^{l'}\right) \nu_1^l(\textbf{z}_L) \\ &= - \int_{\mathcal{S}_L^l} h_L(s) \mathrm{d} \mu(s) + \int_{\mathcal{S}_L^l} D \Psi_{\kappa_L} \boldsymbol{0} [ h_L ] (s) \mathrm{d} \mu(s),\end{align*}

with $w^l=h_L(s) \mu (\mathcal{S}_L^l)$ for $s\in \mathcal{S}_L^l$ and where $\boldsymbol{0}_L=(0,\ldots,0)$ . Along the lines of the proof of Proposition 5, there exists $C\gt 0$ subject to

\begin{align*}n^{-1}|\mathbb{D}(G(n,\mathcal{V}_L^+))| \xrightarrow[\nu(0, \mathcal{S}) \rightarrow 0]{p} 0,\end{align*}

which finishes the proof since

\begin{align*}\mathbb{P}(|\mathbb{D}(G(n,\mathcal{V}))| \le |\mathbb{D}(G(n,\mathcal{V}_L^+))|)=1.\end{align*}

4.1. Neural network fixed-point approximation

An M-layer ( $M\in \mathbb{N}$ ) neural network $f^{\mathrm{NN}}\,:\,\mathbb{R}^{d_x} \rightarrow \mathbb{R}^{d_y}$ maps $d_x$ -dimensional input to $d_y$ -dimensional output and has the form

\begin{align*}f^{\mathrm{NN}} = \sigma_M \circ W_M \circ \cdots \circ \sigma_1 \circ W_1,\end{align*}

where $\circ$ denotes componentwise composition, for $1 \le m \le M$ , $d_0 = d_x$ , and $d_M=d_y$ , $W_m\,:\, \mathbb{R}^{d_{m-1}} \rightarrow \mathbb{R}^{d_m}$ are composable affine maps such that

\begin{align*}W_m(\boldsymbol{x}) = \boldsymbol{\theta}_m \boldsymbol{x} + \boldsymbol{b}_m, \quad \boldsymbol{\theta}_m \in \mathbb{R}^{d_{m} \times d_{m-1}}, \quad \boldsymbol{b}_m \in \mathbb{R}^{d_{m}},\end{align*}

and $\sigma_m\,:\, \mathbb{R}^{d_m} \to [0,1]^{d_m}$ are some activation functions. The width $d_m$ for $1 \le m \le M$ of the mth layer of the neural network is a hyperparameter to be specified.

Let $\boldsymbol{\theta} = \{\boldsymbol{\theta}_m, \boldsymbol{b}_m\}_{m=1}^M$ collect the parameters, and we denote by $f^{\mathrm{NN}}(\!\cdot \! ;\, \boldsymbol{\theta})$ the neural network with parameters $\boldsymbol{\theta}$ . The following proposition ensures that the fixed point $\hat{f}$ can be approximated by a neural network.

Proposition 3. Let $\mathcal{S}$ be a compact subset of $\mathbb{R}$ . Assume that the least fixed point $\hat{f}$ of $\Psi_{\kappa}$ exists. Then for any $\epsilon \gt 0$ , there exists a neural network $f^{\mathrm{NN}}(\!\cdot;\,\boldsymbol{\theta})\,:\, \mathcal{S} \rightarrow [0,1]$ , such that

\begin{align*} \sup\nolimits_{s\in\mathcal{S}} \|f^{\mathrm{NN}}(s;\, \boldsymbol{\theta}) - \hat{f}(s)\| \lt \epsilon, \quad \sup\nolimits_{s\in\mathcal{S}} \|f^{\mathrm{NN}}(s;\, \boldsymbol{\theta}) - \Psi_{\kappa}f^{\mathrm{NN}}(s;\, \boldsymbol{\theta})\| \lt \epsilon.\end{align*}

We propose approximating the least fixed point by the following procedure (the corresponding pseudocode is provided in Algorithm 1).

1. (i) For $j=0$ , initialize a neural network $f^{\mathrm{NN}}(\!\cdot;\,\boldsymbol{\theta}_0)$ with parameter $\boldsymbol{\theta}_0$ .

2. (ii) Evaluate the objective function:

   (4.1) \begin{align} J(\boldsymbol{\theta}_j) = \frac{1}{N}\sum_{i=1}^N |f^{\mathrm{NN}}(x_i;\, \boldsymbol{\theta}_j) - \Psi_{\kappa}^{\mathrm{NN}}f_j^{\mathrm{NN}}(x_i;\, \boldsymbol{\theta}_j)| + \gamma \int_\mathcal{S} f^{\mathrm{NN}}(s;\boldsymbol{\theta}_j)\mathrm{d} \mu(s), \end{align}
   where $0 \lt \gamma \lt 1$ is a parameter and $\{x_0, \ldots, x_N\}$ are data points sampled from $\mathcal{S}$ . The first term is the mean absolute error between the neural network $f^{\mathrm{NN}}$ and $\Psi_{\kappa}^{\mathrm{NN}}f^{\mathrm{NN}}$ (to be defined below) over the data points. For small $\gamma$ , minimizing the first term ensures convergence to a fixed point. The second term approximates the integrated value of the fixed point. Adding it to the loss function penalizes large values and steers the algorithm to converge towards the least fixed point. The coefficient $\gamma$ should be chosen small enough such that the algorithm will prioritize the convergence to zero of the first term.

3. (iii) Evaluate the gradient $\nabla_{\boldsymbol{\theta}} J(\boldsymbol{\theta}_j)$ and obtain the new parameter $\boldsymbol{\theta}_{j+1}$ with gradient descent

   (4.2) \begin{align} \boldsymbol{\theta}_{j+1} = \boldsymbol{\theta}_j - \alpha_j \nabla_{\boldsymbol{\theta}} J(\boldsymbol{\theta}_j), \quad j \leftarrow j+1, \end{align}
   where $\alpha_j$ is the learning rate, and $\nabla_{\boldsymbol{\theta}} J(\boldsymbol{\theta}_j)$ is calculated by automatic differentiation [Reference Baydin, Pearlmutter, Radul and Siskind7].

4. (iv) Repeat steps 2 and 3 until the stopping criterion $J(\boldsymbol{\theta}_{\cdot}) \lt \epsilon$ is reached for some $\epsilon \gt 0$ . We obtain an approximation $\hat{f}_{\epsilon}^{\mathrm{NN}}$ to the least fixed point $\hat{f}$ .

Algorithm 1.

Neural network approximation of the least fixed point.

Algorithm 1 Long description

The image displays a step-by-step algorithm for approximating the least fixed point using a neural network. The algorithm begins with initialization, where a neural network with parameter theta_0 is initialized. Next, the objective function J(theta_j) is calculated, which includes a mean absolute error term and an integrated value term. The gradient of the objective function is then evaluated, and the parameters are updated using gradient descent. This process is repeated until the stopping criterion J(theta_j) is less than or equal to a small positive value epsilon. The algorithm aims to approximate the least fixed point by minimizing the objective function and ensuring convergence to a fixed point.

Remark 7. Calculation of $\Psi_{\kappa}f^{\mathrm{NN}}(\!\cdot\!)$ requires $\Lambda_{\kappa}f^{\mathrm{NN}}(\!\cdot\!) = \int_{s \in \mathcal{S}} \kappa(s, \cdot) f^{\mathrm{NN}}(s) \mathrm{d} \mu(s)$ . The integral can be approximated numerically with Riemann sums in the following manner. Consider a data grid of $\mathcal{S}$ with $M_\mathcal{S}$ points, denoted by $\mathcal{X}_\mathcal{S} = \{s_0, s_1, \ldots, s_{M_\mathcal{S}}\}$ . Then calculate

\begin{align*}\Lambda_{\kappa}^{\mathrm{NN}} f^{\mathrm{NN}}(\cdot;\, \boldsymbol{\theta}) \,:\!=\, \sum_{m=0}^{M_\mathcal{S}-1} \kappa(s_m, \cdot) f^{\mathrm{NN}}(s_m;\, \boldsymbol{\theta}) \mu([s_m, s_{m+1}]) \approx \Lambda_{\kappa} f^{\mathrm{NN}}(\cdot;\, \boldsymbol{\theta}),\end{align*}

where the $\Lambda_{\kappa}^{\mathrm{NN}}$ operator approximates the integral operator $\Lambda_{\kappa}$ in (2.4) by a Riemann sum. We denote by $\Psi_{\kappa}^{\mathrm{NN}}$ the operator obtained by replacing the operator $\Lambda_{\kappa}$ in the definition of $\Psi_{\kappa}$ by $\Lambda_{\kappa}^{\mathrm{NN}}$ . For a sufficiently fine grid it follows that $\Psi_{\kappa}^{\mathrm{NN}}f^{\mathrm{NN}}(\cdot;\, \boldsymbol{\theta}) \approx \Psi{\kappa}f^{\mathrm{NN}}(\cdot;\, \boldsymbol{\theta})$ . The integral $\int_\mathcal{S} \hat{f}_{\epsilon}^{\mathrm{NN}}(s;\boldsymbol{\theta})\mathrm{d} \mu(s)$ approximates the $n\rightarrow \infty$ limit of the final fraction of infected vertices, and can be calculated via a simple Riemann sum.

4.2. Simulations

To illustrate numerically the convergence of the simulation results to the theoretical results of Theorem 1, we generate random graph realizations, compute the final fraction of infected vertices in each realization, and compare the resulting empirical distribution with the fixed point $\hat{f}$ and its integral $\int_{\mathcal{S}} \hat{f} \mathrm{d} \mu$ . To this end, we first introduce a new Monte Carlo algorithm for simulating random graphs and computing the outcome of the percolation process. The algorithm is based on straightforward matrix operations and can be implemented efficiently. The details are given in Algorithm 2.

Algorithm 2:

Simulation of the bootstrap percolation process

Algorithm 2: Long description

Panel A: The algorithm starts by initializing type vector L and threshold vector K based on given measures. Panel B: It initializes vectors for new and explored infections. Panel C: The algorithm then iterates through multiple realizations, sampling binary adjacency matrices and updating thresholds, new infections, and explored infections. Panel D: The process continues until no new infections occur, and the final number of infected vertices is computed.

Let $\mathbb{D}_m(\mathcal{S})/n$ be the final fraction of infected vertices for simulation m. By the results in Theorem 1 we expect this fraction to be close to $\int_{\mathcal{S}} \hat{f}(s)\mathrm{d}\mu(s)$ for all m. In addition, the empirical result in the next section shows that, for a subset $A \subset \mathcal{S}$ , the simulated final fraction of infected vertices with type in A is approximately $\int_A \hat{f}(s)\mathrm{d}\mu(s)$ . On the basis of this observation, we believe that Theorem 1 can be extended to determine the final fraction of infected vertices with type in a certain subset $A \subset \mathcal{S}$ .

4.3. Numerical results

For the numerical experiments, we consider the following three kernel functions defined on the type space $\mathcal{S}=[0,1]$ , with $\mu$ being the uniform measure on $\mathcal{S}$ :

(4.3) \begin{equation} \begin{aligned}\kappa_1(x,y) &= \frac{10\sqrt{x^2+y^2}}{1+\sqrt{|x-y|}}, \\\kappa_2(x, y) &= \frac{5(\mathrm{e}^{x+0.5y} - 1)}{1 + \sqrt{|x-y|}}, \\\kappa_3(x, y) &= \frac{x+y}{|x-y| + |x-1| + |y-1|}.\end{aligned}\end{equation}

Figure 3 visualizes the three kernels. All three kernels, $\kappa_1$ , $\kappa_2$ , and $\kappa_3$ , exhibit the desired properties of heterogeneity and blocking. Heterogeneity arises from the fact that the connection probability varies across vertex types, as illustrated by the non-flat surfaces in Figure 3. Blocking exhibits the phenomenon that vertices of similar types have higher connection probabilities, indicated by the ridge structure in each surface. In particular, $\kappa_2$ exhibits stronger heterogeneity than $\kappa_1$ because of its exponentially increasing numerator, and also introduces asymmetry through the term $x + 0.5y$ . The kernel $\kappa_3$ behaves even more extremely, exploding at the point (1, 1). The bootstrap percolation is considered in a setting where 10% of vertices are initially infected and all remaining vertices have threshold 2. The initial infection is uniformly distributed among the vertices and is independent of the type, which corresponds to

\begin{align*}\nu(k, [a,b]) = I_{\{k=0\}}\frac{1}{10}|b-a| + I_{\{k=2\}}\frac{9}{10}|b-a|.\end{align*}

Figure 3.

Kernel functions in (4.3): (a) $\kappa_1$ , (b) $\kappa_2$ , and (c) $\kappa_3$ .

We first report the numerical results for $\kappa_1$ . The fixed point is computed with the use of Algorithm 1. The neural network consists of two hidden layers with 20 nodes each, followed by a hyperbolic tangent activation function. The parameters are optimized with the Adam algorithm. In Figure 4(a), the overlap of the functions $f^{\mathrm{NN}}$ and $\Psi_{\kappa}^{\mathrm{NN}} f^{\mathrm{NN}}$ indicates that the fixed point has been accurately identified. We compare the fraction of infected vertices obtained from the fixed point with the fraction obtained by Monte Carlo simulation via Algorithm 2. We generate $M=1000$ random graphs with $n=3000$ vertices, and determine for each sample the result of the bootstrap percolation process. The type space is discretized into $L=1000$ equal bins, and the final fraction of infected vertices is calculated for each type. Figure 4(b) compares the scatter plot of simulated fractions $f^{\mathrm{MC}}$ with the fixed point function $f^{\mathrm{NN}}$ . Each point corresponds to the infected fraction (scaled by the width of the bin) of one of the L types of one of the M simulations. The simulated $f^{\mathrm{MC}}$ scatters align with the function $f^{\mathrm{NN}}$ , indicating strong agreement between the simulations and the theoretical asymptotic result given by Theorem 1.

Figure 4.

Fixed point, its image, and simulated final fractions for $\kappa_1$ . (a) Fixed point $f^{\mathrm{NN}}$ approximated with Algorithm 2 and its image $\Psi_{\kappa}^{\mathrm{NN}} f^{NN}$ . (b) $f^{\mathrm{NN}}$ and simulated final fractions $f^{\mathrm{MC}}$ . The vertex type is given on the horizontal axis, and the function value or infected fraction is given on the vertical axis.

Figure 5.

Fixed point, its image, and simulated final fractions for (a) $\kappa_2$ and (b) $\kappa_3$ . The vertex type is given on the horizontal axis, and the function value or infected fraction is given on the vertical axis.

Figure 5 shows the corresponding results for $\kappa_2$ and $\kappa_3$ , obtained with the same procedure as used to generate Figure 4. For conciseness, we overlay the neural network fixed point, its image, and the simulated fractions in each plot. In both cases, the theoretical fixed point aligns well with the simulation results. At first glance, the scatter in Figure 5(b) appears more dispersed than in Figures 4(b) and 5(a). This effect is due to lower connection probabilities and the resulting smaller final infected fraction for the kernel $\kappa_3$ . Taking into account the scale of the vertical axis, we observe that the absolute deviation of the random outcomes from the $n\rightarrow \infty$ result is less than 2% across all three kernels. This highlights that the asymptotic results derived in Theorem 1 approximate the outcome of the infection process very well even for random graphs of moderate size.

Finally, we report the distribution of simulated final fractions of infected vertices for $\kappa_1$ ; the results for $\kappa_2$ and $\kappa_3$ are similar and are thus omitted. We compute the integral of the fixed point as $\hat{\tau} \,:\!=\, \int_{\mathcal{S}} \hat{f}\mathrm{d}\mu \approx \tau^{\mathrm{NN}} \,:\!=\,\int_\mathcal{S} f^{\mathrm{NN}} \mathrm{d} \mu=0.9273$ . By Theorem 1, the final fraction of infected vertices in a large graph is therefore expected to be $92.73\%$ . Figure 6(a) shows the distribution of final fractions obtained from the $M=1000$ simulations with $n=3000$ vertices. The results tightly concentrate between 90% and 94% and are centered near the theoretical value $92.73\%$ . The average simulated final fraction is $92.70\%$ .

Figure 6.

(a) Histogram and kernel density estimation of $M=1000$ simulated final fractions of infected vertices for a graph of size $n=3000$ . The final fraction is given on the horizontal axis, and the frequency is given on the vertical axis. (b) Average simulated final fractions of infected vertices and 95% confidence band for graphs with sizes $n = 200, 400, \ldots, 10000$ , based on $M=1000$ simulations per size. The graph size is given on the horizontal axis, and the final fraction is given on the vertical axis.

Since $\hat{\tau}$ quantifies the asymptotic limit as $n \rightarrow \infty$ , we further perform simulations with graph size $n=200, 400, \ldots, 10000$ , using $M=1000$ realizations for each size. Figure 6(b) reports the average simulated final fractions of infected vertices $\tau^{\mathrm{MC}}$ together with the 95% confidence band. As expected, the confidence band narrows as the graph size increases.

In conclusion, through numerical experiments with the three kernel functions, we validate that the final fraction of infected vertices formulated by the fixed point in Theorem 1 and computed via Algorithm 1 agrees closely with Monte Carlo simulation results obtained with use of Algorithm 2 already for random graphs of moderate size. Moreover, the fixed-point approach is computationally more efficient for obtaining an approximation of the default fraction compared with a Monte Carlo simulation and avoids the sampling error.