An Epidemic Threshold Set for Networks
July 15, 2026
1 Introduction↩︎
In the modern era, complex networks—such as online social networks, computer systems, and the Internet of Things (IoT)—have transformed global communication. However, this high connectivity also accelerates the rapid diffusion of unwanted spreading processes, including misinformation, computer viruses, and epidemic pathogens [1]–[4]. Following foundational breakthroughs in complex network theory [5], [6], modeling and analyzing these propagation dynamics has emerged as a vital research area with profound implications for information security, public health, and social sciences [3], [7], [8].
Epidemic modeling on networks is largely rooted in classical biological frameworks, such as the Susceptible-Infected-Recovered (SIR) and Susceptible-Infected-Susceptible (SIS) models [9]–[12]. Among these, the discrete-time SIS model on networks has been widely studied. A fundamental question in this domain is determining the conditions under which an epidemic persists or dies out—a transition point mathematically defined as the global epidemic threshold [13]–[15].
However, real-world networks are rarely homogeneous. Instead, they typically exhibit distinct community structures—dense clusters of internal connections paired with sparse links between different communities [16]–[18]. This structural heterogeneity causes local spreading dynamics to diverge significantly across the network [19], [20].
In this paper, we consider a discrete-time SIS spreading model analogous to those investigated in [13], [14], which exhibits distinct structural differences from the SIS variations discussed in [9], [11], [21], [22].
Contributions
A major limitation of existing epidemic threshold studies [13]–[15], [23]–[25] is their neglect of community structures, as a single global epidemic threshold \(\tau = \frac{1}{\lambda_1(A)}\) cannot capture local vulnerabilities. To address this, we introduce a community-level epidemic threshold set [thresholdprofile] to quantify and compare local epidemic thresholds among all individual communities. Mathematically, we prove Theorem 1, establishing that any local epidemic threshold is bounded below by the global epidemic threshold. We then validate our theoretical findings and Corollaries 1–2 through numerical simulations. Ultimately, this localization provides a community-oriented perspective for analyzing propagation. Future research could integrate this approach with tighter threshold bounds—such as those proposed by Van Mieghem et al. [23] or Ruhi et al. [25]—to further improve targeted mitigation strategies.
Outline
The remainder of this paper is organized as follows. Section 2 describes the investigated epidemic model and formalizes the definition of the epidemic threshold. In Section 3, we propose the community-level epidemic threshold set and establish a comparative theorem regarding the relationship between local epidemic thresholds and the global epidemic threshold. Subsequently, in Section 4, we compute the epidemic threshold sets and measure the aggregate infection quantity of each community via numerical simulations on real and synthetic datasets. Finally, we conclude the paper and discuss future research directions in Section 5.
2 Preliminaries↩︎
2.1 The Discrete-Time SIS Model↩︎
Consider an undirected, connected network \(G=(V,E)\) with \(|V|=n\). Let \(A=(A_{ij})_{n\times n}\) be the adjacency matrix of \(G\), where:
\[A_{ij}= \begin{cases} 1, & \text{if there is an edge between node } i \text{ and node } j,\\ 0, & \text{otherwise.} \end{cases}\]
In the SIS model, each node exists in exactly one of two discrete states at any given time step: Susceptible (\(S\)) or Infected (\(I\)). During a single time step, the disease transmission probability across any edge is \(\beta\); that is, a susceptible node \(S\) can be infected by each of its infectious neighbors \(I\) with probability \(\beta\). Simultaneously, an infected node \(I\) recovers and returns to the susceptible state \(S\) with probability \(\delta\) per time step. Note that we assume \(\beta\) and \(\delta\) are homogeneous across the entire network \(G\). Henceforth, we uniformly refer to \(\beta\) and \(\delta\) as the transmission rate and recovery rate, respectively. This epidemic propagation process can be rigorously modeled as a Markov chain with \(2^n\) states. Wang et al. [13] and Chakrabarti et al. [14] investigated a discrete-time SIS Model detailed below.
Let \(p_i(t)\) denote the probability that node \(i\) is infected at time step \(t\). Let \(N(i)\) be the set of neighbors of node \(i\), i.e., \(N(i)=\{j\in V:A_{ij}=1\}\). The probability that node \(i\) is not infected by any of its neighbors at time \(t\) is a random variable given by: \[\begin{align} \label{neighborhood-infected} \zeta_i(t)=\prod\limits_{j\in N(i)} \left(1-\beta p_j(t-1)\right) =\prod_{j=1}^n \left(1-\beta A_{ij}p_j(t-1)\right). \end{align}\tag{1}\] We assume that probabilities \(p_j(t-1)\) are independent of each other.
Using Equation 1 , we obtain the discrete-time SIS propagation model that we investigate throughout this paper ([14]): \[\begin{align} \label{main-model} p_i(t+1) = 1 - \left[(1-p_i(t)) + \delta p_i(t)\right]\prod_{j=1}^n \left(1-\beta A_{ij}p_j(t)\right). \end{align}\tag{2}\]
![Figure 1: State transition diagram of the SIS model in [14].](/article/2607.14048/_pdflatex/fhijubzt.png "fig:")
Remark 1.
The discrete-time SIS model in [14] slightly modifies the earlier formulation in [13]. In [14], the authors neglected the higher-order term \(\dfrac{1}{2}\delta p_i(t)\left(1 - \zeta_i(t+1)\right)\). This neglect is justified because the model in [13] can be asymptotically approximated to yield Equation (7) in [14], which corresponds precisely to Model 2 investigated herein.
In the investigated SIS model, the recurrence relation is non-linear because the probability that a node resists infection from its neighbors is expressed as a product. Consequently, this system is governed by a Nonlinear Dynamical System* (NLDS).*
2.2 Epidemic Threshold of a Propagation Model with Homogeneous Transmission and Recovery Rates↩︎
We recall the formal definition of the epidemic threshold on a network as formulated by Chakrabarti et al. [14] (see also [13]).
Definition 1 (Epidemic Threshold). A positive real value \(\tau\) is defined as the epidemic threshold for NLDS on a network if it satisfies the following two conditions:
If \(\dfrac{\beta}{\delta}<\tau\), the epidemic dies out exponentially over time.
If \(\dfrac{\beta}{\delta}>\tau\), the epidemic persists and can break out across the network.
Here, the ratio \(\frac{\beta}{\delta}\) is termed the effective spreading rate* ([10]).*
Thus, when a network’s effective spreading rate exceeds its epidemic threshold, a disease outbreak occurs. Conversely, when the effective spreading rate falls below the threshold, the epidemic dies out over time.
In [13] and [14], the authors defined an explicit epidemic threshold directly determined by the network’s adjacency matrix \(A\).
Definition 2 ([14]). The value \(\tau=\frac{1}{\lambda_1(A)}\) is defined as the epidemic threshold of the network \(G\), where \(\lambda_1(A)\) denotes the largest eigenvalue (spectral radius) of the adjacency matrix \(A\).
Following the calculations in [14], the condition for the disease-free state, where \(p_i(t) \to 0\) for all \(i \in V\) as \(t \to \infty\), is \(\frac{\beta}{\delta} < \frac{1}{\lambda_1(A)}\).
3 Community-Level Epidemic Threshold Set↩︎
3.1 Epidemic Threshold Set with Homogeneous Transmission and Recovery Rates↩︎
Given a network with \(K\) disjoint, connected communities, we formulate the SIS model 2 on the induced subgraph of each community \(C_g\) independently. This setup temporarily disregards inter-community edges while keeping the transmission (\(\beta\)) and recovery (\(\delta\)) rates unchanged.
Let \(A_g\) be the adjacency matrix of \(C_g\). Following Definition 2, the local epidemic threshold of community \(C_g\) is defined as: \[\tau_g = \frac{1}{\lambda_1(A_g)}, \quad g = 1, \dots, K\] Hereafter, \(\tau\) and \(\tau_g\) denote the global and local epidemic thresholds, respectively.
Definition 3 (Epidemic Threshold Set). The ordered set of positive real numbers \[\mathcal{T}_A = (\tau_1,\tau_2,\ldots,\tau_{K})\] is defined as the epidemic threshold set* of the network \(G\), where \(\tau_g =\frac{1}{\lambda_1(A_g)}\) denotes the local epidemic threshold associated with community \(C_g\), for \(g = 1, \dots, K\).*
We can rank the communities in ascending order of their local epidemic thresholds (re-indexing if necessary) such that: \[\tau_{1}\leq \tau_{2}\leq \cdots \leq \tau_{{K}}.\]
3.2 Comparison and Evaluation↩︎
After establishing the community-based threshold set, we compare the local epidemic threshold of an individual community with the global epidemic threshold.
By Definition 2, the global epidemic threshold is given by \(\tau=\frac{1}{\lambda_1(A)}\). The following theorem establishes a fundamental inequality connecting the global epidemic threshold to the local epidemic thresholds.
Theorem 1. The local epidemic threshold of any community is greater than or equal to the global epidemic threshold. That is, for every community \(C_g\), we have: \[\tau_g\geq \tau.\] Furthermore, it holds that \(\tau \le \tau_1 \le \dots \le \tau_K\).
Proof. Let \(P\) be a permutation matrix that groups all nodes belonging to community \(C_g\) into a single contiguous block within the matrix \(A\). We can express the transformed matrix as: \[\hat{A}= P^T A P = \begin{pmatrix} A_g & R\\ R^T & A_{\bar g} \end{pmatrix},\] where \(A_g\) is the adjacency matrix of the subgraph induced by community \(C_g\), \(A_{\bar g}\) is the adjacency matrix of the remainder of the network, and \(R\) represents the bipartite cut (inter-community edges) connecting \(C_g\) to \(V\setminus C_g\).
Since \(P\) is an orthogonal permutation matrix (\(P^T=P^{-1}\)), \(A\) and \(\hat{A}\) are similar matrices. Consequently, they share the exact same set of eigenvalues (spectrum).
Let \(u_g\in \mathbb{R}^{|C_g|}\) be the eigenvector corresponding to the largest eigenvalue \(\lambda_1(A_g)\) of \(A_g\), meaning \(A_g u_g = \lambda_1(A_g)u_g\). We construct an expanded vector in \(\mathbb{R}^n\) by zero-padding the remaining entries: \(\tilde{u}_g = \begin{pmatrix} u_g\\ 0 \end{pmatrix}.\) According to the Rayleigh quotient theorem for real symmetric matrices (see [26]), the largest eigenvalue of \(\hat{A}\) satisfies: \[\lambda_1(\hat{A}) = \max_{x\neq 0} \frac{x^T \hat{A} x}{x^T x}.\]
Since \(\tilde{u}_g\neq 0\), it follows directly that \(\lambda_1(\hat{A}) \geq \frac{\tilde{u}_g^T \hat{A}\tilde{u}_g}{\tilde{u}_g^T\tilde{u}_g}.\) Then, we have: \[\tilde{u}_g^T \hat{A}\tilde{u}_g = \begin{pmatrix} u_g^T & 0 \end{pmatrix} \begin{pmatrix} A_g & R\\ R^T & A_{\bar g} \end{pmatrix} \begin{pmatrix} u_g\\ 0 \end{pmatrix} = u_g^T A_g u_g.\]
Simultaneously, we have \(\tilde{u}_g^T\tilde{u}_g = u_g^T u_g.\) Therefore, we obtain: \[\frac{\tilde{u}_g^T \hat{A}\tilde{u}_g}{\tilde{u}_g^T\tilde{u}_g} = \frac{u_g^T A_g u_g}{u_g^T u_g} = \lambda_1(A_g).\]
It follows that \(\lambda_1(\hat{A})\geq\lambda_1(A_g)\). Since \(A\) and \(\hat{A}\) have the same spectrum, \(\lambda_1(A)=\lambda_1(\hat{A})\), and hence \(\lambda_1(A)\geq\lambda_1(A_g)\). Because both eigenvalues are positive, \(\frac{1}{\lambda_1(A_g)}\geq\frac{1}{\lambda_1(A)}\). Therefore, \(\tau_g\geq\tau\), which completes the proof. ◻
Corollary 1. If an epidemic cannot break out across the entire network, it cannot break out independently within any individual community.
Proof. By Theorem 1, for any community \(C_g\), we have \(\tau_g\geq \tau\). If the effective spreading rate is below the global epidemic threshold, then \(\frac{\beta}{\delta}<\tau\). Consequently, for every community \(C_g\), the inequality \(\frac{\beta}{\delta}<\tau\leq \tau_g\) holds. Thus \(\frac{\beta}{\delta}<\tau_g, \forall g=1,2,\ldots, K.\) According to Definition 1, since the effective spreading rate is below the local epidemic threshold of every community, the epidemic cannot break out in any community. ◻
Corollary 2. If an epidemic is able to break out within any community, it will inevitably trigger an outbreak across the entire global network.
Proof. Suppose there exists a community \(C_g\) whose effective spreading rate exceeds its local epidemic threshold, i.e., \(\frac{\beta}{\delta}>\tau_g\). By Theorem 1, we know that \(\tau_g\geq\tau\). It immediately follows that \(\frac{\beta}{\delta}>\tau_g\geq\tau\), yielding \(\frac{\beta}{\delta}>\tau\). According to Definition 1, since the effective spreading rate exceeds the global epidemic threshold, a global epidemic outbreak is guaranteed. ◻
4 Numerical Experiments↩︎
4.1 Datasets↩︎
We evaluate the proposed epidemic threshold sets on two datasets: one synthetic network (Network1) and one real-world contact network (Haslemere).
For the first dataset, we randomly select the number of communities \(K\) uniformly in the range \([8, 12]\), and set the community sizes \(|C_g|\) between \(45\) and \(90\) nodes. For each community, the internal connection probability \(p_{\mathrm{in}}\) is chosen randomly from \([0.08, 0.16]\), while the inter-community connection probability \(p_{\mathrm{out}}\) between different modules is drawn from \([0.002, 0.012]\). The resulting probability matrix is symmetrized to generate an undirected graph. We designate this synthetic network as Network1.
The second dataset is the Haslemere contact network [27], [28]. Here, nodes represent residents of Haslemere, and edges represent interpersonal physical contacts captured via wearable sensors. The raw graph contains \(469\) nodes and \(1,262\) edges, with a maximum degree of \(37\). Because the raw data contains severe high-degree outliers, a preprocessed version was generated by pruning specific edges attached to high-degree hubs, removing isolated nodes, and ensuring that both the overall network and each individual community remain connected. The preprocessed network consists of \(369\) nodes and \(808\) edges, with a capped maximum degree of \(8\).
4.2 Computation of Community Epidemic Threshold Sets and Comparison with the Global Epidemic Threshold↩︎
In our first experiment, we construct the community-level epidemic threshold set for each network. We evaluate each community \(C_g\) and its corresponding induced sub-adjacency matrix \(A_g\) independently. The global epidemic threshold of the entire graph is computed via \(\tau=\frac{1}{\lambda_1(A)}\), where \(A\) is the full adjacency matrix of network \(G\).
For each community \(C_g\), we compute and report the following metrics:
\(|C_g|\): The number of nodes in community \(C_g\).
\(|E_g|\): The number of internal edges in community \(C_g\) (edges where both endpoints reside within \(C_g\)).
\(\tau_g\): The local epidemic threshold of community \(C_g\), calculated as \(\tau_g=\frac{1}{\lambda_1(A_g)}\).
\(\tau_g-\tau\): The spectral gap between the local epidemic threshold of community \(C_g\) and the global epidemic threshold.
\(\mathrm{Rank}\): The ordinal rank of the community sorted in ascending order of its local epidemic threshold \(\tau_g\).
The statistical results and calculated metrics of two datasets are summarized in the tables below.
Consistent with Theorem 1, all local epidemic thresholds \(\tau_g\) are greater than the global epidemic threshold \(\tau\). While these local thresholds differ minimally in synthetic Network 1, they exhibit a distinct split in the Haslemere network: the first four communities have closely aligned thresholds, whereas the remaining four vary widely and deviate further from \(\tau\).
4.3 Simulating the SIS Model on the Network↩︎
In our second experiment, we simulate the discrete-time SIS dynamics 2 on two datasets Network1 and Haslemere.
Given the global infection probability vector \(P(t)=(p_1(t),p_2(t),\ldots,p_n(t))^T.\) Let \(p_g(t)=\left(p_i(t)\right)_{i\in C_g}\) denote the sub-vector restricted to community \(C_g\). To quantify the aggregate infection quantity within community \(C_g\) at time step \(t\), we define the formula: \[Q_g(t) = \|p_g(t)\|_1 = \sum_{i\in C_g}p_i(t).\]
We simulate disease under two cases using an identical initial condition: \(10\) nodes are randomly selected across the global network as initial seeds, each assigned an initial infection probability chosen randomly from \([0.87, 0.98]\).
Case 1: The effective spreading rate falls below the global epidemic threshold.
We fix the recovery rate at \(\delta=0.4\) and choose the transmission rate \(\beta\) such that \(\frac{\beta}{\delta} = 0.95\,\tau.\)
For Network1, we set \(\frac{\beta}{\delta}=0.074\). For the Haslemere network, we set \(\frac{\beta}{\delta}=0.15\).
In this case, the disease fails to break out in any community, exactly as shown in Corollary 1. The aggregate infection probabilities \(Q_g(t)\) of all communities decay toward the disease-free equilibrium \(0\).
Case 2: The effective spreading rate exceeds the local epidemic thresholds of several communities while falling below those of the remaining ones.
We fix the recovery rate at \(\delta=0.4\) and choose \(\beta\) such that \(\frac{\beta}{\delta} = \frac{\tau_{\min}+\tau_{\max}}{2}\). Here, \(\tau_{\min}\) and \(\tau_{\max}\) denote the minimum and maximum local epidemic thresholds in the network, respectively.
For Network1, we set \(\frac{\beta}{\delta}=0.12\). For the Haslemere network, we set \(\frac{\beta}{\delta}=0.296\).
In this case, the selected \(\beta\) and \(\delta\) result in an effective spreading rate that exceeds the local epidemic thresholds of several communities while remaining below those of the remaining ones. Consistent with Corollary 2, the epidemic breaks out across the entire network. The aggregate infection levels \(Q_g(t)\) of all communities converge toward a non-zero equilibrium state.
Remark 2. Due to random seeding, initial infection levels \(Q_g(0)\) vary, leaving some communities temporarily uninfected (\(Q_g(0) = 0\)). Within a few steps, however, all modules reach \(Q_g(t) > 0\). This transition confirms that the infection inevitably spreads from seeded to unseeded communities via boundary edges.
5 Conclusion↩︎
In summary, this study established a community-level epidemic threshold set for discrete-time SIS dynamics, supported by numerical and simulation analyses. In future work, we plan to generalize this framework to alternative epidemic models and broader network topologies. Furthermore, this approach offers a scalable framework for investigating local propagation dynamics in massive networks by decomposing them into modular structures, which may inform future community-based risk assessment strategies.