arXiv:2609.33682v1 [cs.SI] 27 Sep 2026
A Novel Approach for the SDIR Epidemic Model on Online Social Networks 1st Nguyen Hong Phuc
2nd Duong Khanh Ly
3rd Hoang Phi Dung
Faculty of Information Technology Posts and Telecommunications Institute of Technology Hanoi, Vietnam [email protected]
Faculty of Information Technology Posts and Telecommunications Institute of Technology Hanoi, Vietnam [email protected]
Faculty of Fundamental Sciences Posts and Telecommunications Institute of Technology Hanoi, Vietnam [email protected]
Abstract—Information diffusion can be controlled by restricting or removing links (edges) in online social networks, as well as in real-world networks. To identify the most influential links to remove while minimizing diffusion, previous studies have proposed upper bounds for spreading processes in SIR and SIS models, using supermodularity and weighted matrices to identify critical links in contact networks. However, in some cases, existing upper bounds are not sufficiently tight to accurately capture the effect of important edges, as in the SDIR model of [14]. We therefore propose a tighter upper bound for controlling diffusion in the SDIR model by directly analyzing the dynamics of the two state vectors D and I in a 2N -dimensional space. This approach yields an improved spectral-radius convergence condition and outperforms the previous method. Simulations on the synthetic Erdős-Rényi network and the real-world Haslemere dataset using a Greedy edge-deletion algorithm demonstrate its effectiveness for influence minimization on social networks. Index Terms—SDIR epidemic models, complex networks, discrete optimization, Markov chains, edge deletion, greedy, meanfield approximation.
I. INTRODUCTION Epidemic spreading models were introduced in the early twentieth century through the mathematical epidemiology work of W. O. Kermack and A. G. McKendrick [13]. Over the past two decades, seminal studies such as [1], [20] have shown that network topology plays a fundamental role in determining epidemic thresholds and dynamics (see, also [21]). However, classical models often assume instantaneous or memoryless state transitions, which do not capture complex behavioral responses on modern online social platforms, such as user hesitation, delayed sharing, or deliberate decision-making, nor malware behavior in computer networks and the Internet [17]. Consequently, epidemic models such as SIR, SIS, and their variants have become important tools in computer science, cybersecurity, malware analysis, online social networks, and complex-network theory [2], [5], [11], [12], [14], [18], [19], [23], [24], [26], [29]. Fundamental problems in this area include influence maximization, influence minimization, influence blocking, and network anomaly detection. Recently, interest in individual-based models has increased because complex networks effectively represent major technological platforms such as the Internet and online social networks [19], [25], [29], [30]. Building on the work of Pare
et al. [19] and [29], Khanh et al. [14] proposed the SDIR model to describe user behavior on online social networks. On platforms such as Facebook, TikTok, and X (Twitter), users may hesitate and consider whether to share received information before making a decision. Thus, sharing depends on user behavior and is stochastic. In this paper, we study the SDIR model using a different mathematical approach to tighten the results in [14]. Related Works Individual-based models have recently been studied extensively, bringing the analysis of dynamical systems on complex networks closer to real technological platforms [6], [7], [14], [17], [21], [29], [30]. Most of these models use either the Euler method [19], [30] or mean-field approximation [7], [14], [17], [21], [29]. More recently, alternative approaches extending the threshold-based method of Wang [28] have considered information or epidemic spreading within local communities of very large networks (see [8]). Models incorporating a delay state during propagation have also received increasing attention [16]. In contrast to influence maximization, influence minimization by reducing the number of infections has been considered in [4], [14], [22], [27], [29]. Contributions Unlike Khanh et al. [14], where the two states x(t) and y(t) are combined through the weighted quantity x(t) + Qy(t), we directly analyze the two full state vectors in the 2N dimensional space, thereby preserving their coupled dynamics. This approach removes the dependence on the auxiliary weighting matrix Q and yields a provably tighter spectral condition for model convergence in Theorem III.2. We then adopt the edge-deletion approach in [7], [14], [29] to minimize the number of infections, for which we derive the upper bound in Theorem IV.4 as a surrogate objective for the greedy edgedeletion algorithm. Theorem IV.7 further establishes that this bound is pointwise tighter than that proposed in [14]. Outline The remainder of this paper is organized as follows. Section II presents the SDIR model and the main assumptions. Sec-
tions III and IV introduce the proposed approach and clarify its differences from the previous method through the convergence result (Theorem III.1) and the spectral result (Theorem III.2); an upper bound is then derived (Theorem IV.4) and the main problem is formulated (Problem IV.2). Section V presents the edge-deletion algorithm (Algorithm 1), and numerical results on a synthetic network and a real-world network are reported in Section VI. Finally, Section VII concludes the paper, and the proofs are provided in Appendix. Notation Let R denote the set of real numbers. For any positive integer N , we have [N ] = {1, . . . , N }, I denotes the identity matrix, diag(ai ) denotes the diagonal matrix with diagonal entries ai , and ρ(A) is the spectral radius of any matrix A. The Euclidean norm of a vector and the induced matrix 2norm are denoted by ∥ · ∥, while ∥ · ∥1 denotes the 1-norm. For vectors or matrices of the same dimension, ≤ and ≥ are understood entrywise; for example, X ≤ Y if and only if Xij ≤ Yij for all i, j ∈ [N ]. II. MODEL DESCRIPTION
imation to the infection probability yields the deterministic SDIR model. x(t + 1) = (I − D + AS(t)B)x(t)
(1)
+ Wy(t) y(t + 1) = (I − A)S(t)Bx(t) + (I − W − D′ )y(t)
(2)
′
r(t + 1) = Dx(t) + D y(t) + r(t) Here, the vectors x(t), y(t), and r(t) contain the ith entries E[Ii (t)], E[Di (t)], and E[Ri (t)], respectively, for ∀i ∈ [N ]. The matrix S(t) = diag(si (t)), where si (t) = E[Si (t)] ∀i ∈ [N ], and the matrix B has entries Bij = E[βij (t)]. The remaining diagonal matrices are D = diag(E[δi (t)]), A = diag(E[αi (t)]), W = diag(E[ω PN i (t)]), and D′ = diag(E[δi′ (t)]). We also assume that j=1 Bij < 1, ∀i ∈ [N ]. Remark II.1. Unlike [14], where S(t) is replaced by S(0) to obtain a linear recurrence, we retain the time dependence of S(t). This directly reflects the variation of the susceptible state during propagation. Assumption 1. Di ≤ Di′ for all i ∈ [N ].
Ij1
This assumption is equivalent to Assumption 1 in [14].
βij1 (t) 1 − αi (t)
Ij2
βij2 (t)
Si
Di
δi′ (t)
Ri
ωi (t) αi (t)
Ii
δi (t)
βij3 (t)
Ij3
The SDIR model proposed in [14] extends the SIR model to describe information diffusion on social networks. The D (Delayable) state represents users (nodes) who have received information but hesitate to spread it immediately and may subsequently transition to state I or R. Consider a spreading process on a digraph G = (V, E) with N nodes. At each time step t, the state of node i ∈ V is represented by the indicator variables Si (t), Di (t), Ii (t) and Ri (t) ∈ {0, 1}, corresponding to the Susceptible (S), Delayable (D), Infected (I), and Recovered (R) states, respectively. Since each node occupies exactly one state at a time, Si (t) + Di (t) + Ii (t) + Ri (t) = 1, ∀i ∈ V, ∀t > 0. A neighboring node j of i in state I can infect node i with probability βij (t); upon successful infection, node i moves directly to state I with probability αi (t) or to the delay state D with probability 1 − αi (t). For node i in state D, draw p ∼ U [0, 1]. Node i moves to I if p < ωi (t), to R if ωi (t) ≤ p < ωi (t) + δi′ (t), and otherwise remains in D. Finally, node i recovers to R at rate δi (t) from state I. We assume that the parameters βij (t), αi (t), ωi (t), δi (t) and δi′ (t) are independent random variables with time-invariant distributions. Based on the information-spreading model in [14], taking expectations on both sides and applying mean-field approx-
Assumption 2. 0 < Wi + Di′ ≤ 1 for all i ∈ [N ]. The quantity Wi + Di′ represents the probability that a node leaves the delay state D at a given time step, either by transitioning to state I or to state R. Thus, this assumption ensures that the transition probabilities are valid and that a node eventually leaves state D after the delay process. III. GLOBAL CONVERGENCE OF DETERMINISTIC SDIR MODEL In the D-SIR model of Yi et al. [29], x(t + 1) is determined directly by a linear system based on x(t). In the SDIR model, the delay state D couples x(t) and y(t). We therefore analyze these two state vectors jointly. For convenience, let F = S(0)B. def x(t) For x(t), y(t) ∈ RN , define v(t) = ∈ R2N and y(t) I − D + AF W as consider the matrix M = (I − A)F I − W − D′ the state-transition matrix from v(0) to v(1). Theorem III.1. Consider the SDIR model satisfying ρ(M) < b = 0 is the unique equilibrium of (x, y); specifically, 1. Then v limt→∞ x(t) = limt→∞ y(t) = 0, and the system (x(t), y(t)) is exponentially stable at the origin for every initial state satisfying the model conditions. We next compare the convergence condition based on the 2N × 2N matrix M with that in [14]. Following [14], under Assumption this paper Q = diag(qi ) i h 1, we fix throughout Wi ′ with qi ∈ Wi +D ′ −D , 1 , provided that Wi + Di − Di > 0. i i If Wi + Di′ − Di = 0, which gives Wi = 0, we choose any
qi ∈ (0, 1]. Thus, qi > 0 for all i ∈ [N ]. Define GQ = A + Q(I − A) and MQ = I − D + GQ F is the comparison matrix used for evaluating the convergence condition in [14]. Theorem III.2. Under Assumption 1, we have ρ(M) ≤ ρ(MQ ). Moreover, it was shown in [14] that, under Assumption 1, ρ(MQ ) ≤ ρ(MSIR ) where MSIR = I − D + F, as given in [29]. Therefore, we have the following result. Corollary III.3. Under Assumption 1, we have ρ(M) ≤ ρ(MQ ) ≤ ρ(MSIR ). Consequently, if ρ(MSIR ) < 1, then ρ(M) < 1. IV. PROBLEM AND BOUNDING FUNCTION A. Main Problem To quantify the infection level of the network, for each i ∈ [N ], define mi (t) = xi (t) + yi (t) + ri (t) and let m(t) = x(t) + y(t) + r(t). Assume the initial state satisfies mi (0) = xi (0) + yi (0) + ri (0) ∈ [0, 1] for all iP ∈ [N ]. From (1), we N have mi (t + 1) − mi (t) = (1 − mi (t)) j=1 Bij xj (t). Since PN 0 ≤ xj (t) ≤ mj (t) ≤ 1, and j=1 Bij < 1, we have 0 ≤ PN j=1 Bij xj (t) < 1. If mi (t) ∈ [0, 1], then 0 ≤ 1−mi (t) ≤ 1, PN and hence 0 ≤ (1−mi (t)) j=1 Bij xj (t) ≤ 1−mi (t). Hence, 0 ≤ mi (t) ≤ mi (t + 1) ≤ 1. By induction, mi (t) ∈ [0, 1] for all t ≥ 0, and mi (t) is monotone non-decreasing over time. Thus, mi (t) can be interpreted as the probability that node i has left state S by time t, i.e., the probability that node i is in one of the states D, I, or R. Moreover, since si (t) = 1−mi (t) ∀t, S(t) is entrywise monotone non-increasing over time, and hence S(t) ≤ S(0). Let m∗ ∈ RN denote the vector with entries m∗i = supt≥0 mi (t) ∀i ∈ [N ]. def
For a deleted edge set P ⊆ Q, let B−P denote the matrix obtained from B by setting Bij = 0 for every edge (j, i) ∈ P , and define F−P = S(0)B−P . Correspondingly, define the comparison matrix M−P = I − D + AF−P W . (I − A)F−P I − W − D′ Under Assumption 2, the matrix W + D′ is invertible. Define T = W(W + D′ )−1 and Θ = A + T(I − A). Theorem IV.4. If ρ(M−P ) < 1, then the cumulative number of new infections after deleting the edge set P satisfies b ) = 1⊤ F−P (D − ΘF−P )−1 (x(0) + Ty(0)) . Φ(P ) ≤ Φ(P (4) Remark IV.5. If the original model satisfies ρ(M) < 1, then for every P ⊆ Q, we have B−P ≤ B, and therefore M−P ≤ M. Since M−P and M are nonnegative matrices, the monotonicity of the spectral radius [10] gives ρ(M−P ) ≤ ρ(M) < 1. Hence, the condition in Theorem IV.4 holds for every deleted edge set P ⊆ Q. We next compare the proposed upper bound with that in [14]. For P ⊆ Q, let MQ,−P = I−D+GQ F−P . Under the condition ρ(MQ,−P ) < 1, the upper bound in [14] is given by ΦQ (P ) = 1⊤ F−P (D − GQ F−P )
−1
(x(0) + Qy(0)) . (5)
Remark IV.6. ΦQ is monotone non-increasing and supermodular with respect to the deleted edge set P ⊆ Q, as given in [14]. Theorem IV.7. Under Assumption 1, if ρ(MQ,−P ) < 1 then b ) ≤ ΦQ (P ), Φ(P ) ≤ Φ(P
Definition IV.1. For a deleted edge set P , define Φ(P ) = ∥m∗ − m(0)∥1
B. Supermodular Upper Bound
(3)
as the cumulative number of new infections after the propagation process terminates. Problem IV.2. Given a digraph G = (V, E) and initial states x(0), y(0), r(0) such that x(0) + y(0) + r(0) ∈ [0, 1]N , let Q ⊆ E be a candidate set of edges and let k ≤ |Q| be a positive integer. Find a set P ∗ ⊆ Q with |P ∗ | ≤ k such that P ∗ ∈ argmin Φ(P ). P ⊆Q, |P |≤k
Remark IV.3. Finding an optimal solution P ∗ to Problem IV.2 is NP-hard. The proof is analogous to [29, Theorem 4.4]. Since Problem IV.2 is NP-hard, directly optimizing Φ(P ) is impractical for large networks. Therefore, when the model convergence condition holds, i.e., the probability of each node b ) as an being infected converges to zero, we construct Φ(P upper bound on Φ(P ) that is monotone and supermodular with respect to the deleted edge set P . This upper bound serves as a surrogate objective, enabling an efficient greedy edgeselection algorithm.
b ) and ΦQ (P ) are defined in (4) and (5), respecwhere Φ(P tively. Although the deterministic SDIR model in this paper retains S(t) in the recurrence, the upper bound in [14] remains a valid upper bound for the cumulative number of new infections considered here. Moreover, the theorem shows that jointly considering the two state vectors x(t) and y(t) yields an upper bound tighter than the upper bound proposed in [14]. b ) is monotone nonProposition IV.8. If ρ(M) < 1, then Φ(P increasing and supermodular with respect to the deleted edge set P ⊆ Q. All proofs are provided in the Appendix. V. EDGE DELETION ALGORITHM b ΦQ }, where Φ b Consider the objective function f ∈ {Φ, is the upper bound proposed in this paper and ΦQ is the upper bound in [14]. Since both functions are monotone nonincreasing and supermodular with respect to the deleted edge set, we apply the following Greedy algorithm to select k edges from the candidate edge set Q.
Algorithm 1 Greedy Algorithm (GA) b ΦQ }, a graph G, initial states, a Input: A function f ∈ {Φ, candidate edge set Q, and an integer k. Output: An edge set P ⊆ Q of size k. Initialize P ← ∅ for i = 1 to k do Compute f (P ∪ {e}) for each e ∈ Q\P e⋆ ← argmaxe∈Q\P f (P ) − f (P ∪ {e}) P ← P ∪ {e⋆ } end return P
To further validate the effectiveness of our method on realworld data, we next consider the Haslemere dataset collected in the UK through the BBC Pandemic project [9], [15]. Following the parameters in [14], the infection parameter is adjusted such that Bij ∈ [0.056, 0.063]. We compare the algorithms in terms of performance using the same deletion budget k = 210 from a candidate set Q of 520 edges. The corresponding results are shown in Fig. 2. 9
8
VI. NUMERICAL EXPERIMENTS In this section, we perform numerical simulations of (1) to validate the theoretical results. We compare the proposed Improved Greedy Algorithm (IGA) with the following three algorithms • Random [3]: Randomly delete one edge at each iteration. • Max-Degree [1]: Delete an edge incident to the highestdegree node at each iteration. • BGA: Algorithm 1 applied to f = ΦQ defined in (5). We first evaluate the proposed method on an Erdős-Rényi (ER) network with N = 700 and p = 0.023. The initial states are nonzero at |S| = 7 seed nodes, with xi (0) ∈ [0.80, 0.85] and yi (0) ∈ [0, 0.05]. We sample Bij ∈ [0.024, 0.034], Wi ∈ [0.15, 0.35], and Di ∈ [0.30, 0.48], with Wi + Di′ ≤ 0.95. For Ai , the seed nodes, 45 randomly selected non-seed nodes, and the remaining nodes use [0.50, 0.78], [0.65, 0.87], and [0.15, 0.35], respectively. We set |Q| = 3500 and k = 750; results are shown in Fig. 1. 20.0
Number of new infections
17.5
15.0
12.5
10.0
7.5
5.0 0
100
200
300
400
500
600
700
k
IGA
BGA
Max-Degree
Random
Fig. 1. Performance evaluation of edge deletion on Erdős–Rényi Network.
7 Number of new infections
b is called the The Greedy Algorithm (GA) that uses f = Φ Improved Greedy Algorithm (IGA), while the version using f = ΦQ is called the Baseline Greedy Algorithm (BGA). Based on Proposition IV.8 and Remark IV.6, the solution returned by the greedy algorithm guarantees an approximation ratio of (1 − 1e ) for the function f (∅) − f (·), with respect to the optimal solution.
6
5
4
3
2 0
50
100
150
200
k
IGA
BGA
Max-Degree
Random
Fig. 2. Performance evaluation of edge deletion on Haslemere Network.
The edge-deletion process of Algorithm 1 in Fig. 1 and b Fig. 2, using the two upper bounds Φ(·) and ΦQ (·), guides edge selection substantially more effectively than Random and Max-Degree. In particular, the improved algorithm, IGA, b using Φ(·) reduces infections faster than BGA, which uses ΦQ (·) from [14]. This observation is consistent with Theb orem IV.7, which shows that Φ(·) provides a tighter upper bound than ΦQ (·) and hence a more informative surrogate for ranking candidate edges by marginal reduction. Although the proposed analysis is performed in the 2N -dimensional space, the resulting upper bound in Theorem IV.4 only involves the inverse of an N × N matrix, as does ΦQ in [14]. Moreover, using the rank-one update strategy in [29], both IGA and BGA can be implemented with computational complexity O N 3 + k(N 2 + |Q|N ) . Finally, we compare two quantities that upper-bound the infection level of the two comparison systems on the same Haslemere dataset and with the same infection parameters as in Fig. 2. Specifically, we consider ∥LQ Mt v(0)∥1 for the proposed method and ∥MtQ (x(0) + Qy(0))∥1 for the method in [14], where LQ = [I Q] is used to ensure that the two quantities have the same initial value ∥x(0) + Qy(0)∥1 . Their decay rates are then governed by the spectral radii of the corresponding matrices, namely ρ(M) and ρ(MQ ). In Fig. 3, the quantity corresponding to the proposed method decreases and converges to zero faster than that of the method in [14]. This result is consistent with Theorem III.2, which gives ρ(M) ≤ ρ(MQ ).
4
3
2
1
0 0
100
200
300
400
500
Time step M
MQ
Fig. 3. Convergence comparison between M and MQ formulations.
VII. CONCLUSION Rather than relying on a weighted combination of the two states as in previous studies, this paper directly analyzes the SDIR model in the 2N -dimensional space. This formulation yields a tighter spectral convergence condition and a tighter upper bound for influence minimization, which is incorporated into a greedy edge-deletion algorithm. Experiments on the synthetic Erdős-Rényi network and the real-world Haslemere dataset demonstrate the effectiveness of the resulting Improved Greedy Algorithm (IGA) in reducing information spread. Future work will investigate broader network topologies, parameter sensitivity, and scalable implementations for larger networks. REFERENCES [1] R. Albert, H. Jeong, and A.-L. Barabási, “Error and attack tolerance of complex networks,” Nature, vol. 406, no. 6794, pp. 378–382, 2000. [2] H. J. Ahn and B. Hassibi, “Global dynamics of epidemic spread over complex networks,” in Proc. 52nd IEEE Conf. Decision and Control (CDC), 2013, pp. 4579–4585. [3] D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, “Network robustness and fragility: Percolation on random graphs,” Phys. Rev. Lett., vol. 85, pp. 5468–5471, 2000. [4] L. H. Chen, L. Hung, H. Lotze, and P. Rossmanith, “Online node- and edge-deletion problems with advice,” Algorithmica, vol. 83, pp. 2719– 2753, 2021. [5] W. Chen, C. Castillo, and L. V. Lakshmanan, Information and Influence Propagation in Social Networks. Morgan & Claypool Publishers, 2014. [6] D. X. Cho, T. H. Anh, N. T. L. Phuong, and N. K. Khoa, “Two-stage APT malware propagation model in computer networks,” Neural Comput. Appl., vol. 37, pp. 21805–21832, 2025. [7] H. P. Dung and D. K. Ly, “Minimizing cumulative infections in SIS epidemic models over networks via an edge deletion algorithm,” in Proc. 11th Int. Conf. Micro-Electronics, Electromagnetics and Telecommunications (ICMEET), Lecture Notes in Electrical Engineering, Springer, to appear, 2026. [8] H. P. Dung and N. H. Phuc, “A novel approach for epidemic threshold of networks,” 2026, arXiv:2607.14048. [9] J. A. Firth, J. Hellewell, P. Klepac, S. Kissler, A. J. Kucharski, and L. G. Spurgin, “Using a real-world network to model localized COVID-19 control strategies,” Nat. Med., vol. 26, pp. 1616–1622, 2020. [10] R. A. Horn and C. R. Johnson, Matrix Analysis. Cambridge University Press, 2012. [11] D. Kempe, J. M. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a social network,” in Proc. 9th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD), 2003, pp. 137– 146.
[12] D. Kempe, J. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a social network,” Theory Comput., vol. 11, no. 4, pp. 105–147, 2015. [13] W. O. Kermack and A. G. McKendrick, “A contribution to the mathematical theory of epidemics,” Proc. Roy. Soc. London A, vol. 115, no. 772, pp. 700–721, 1927. [14] T. V. Khanh, D. X. Cho, and H. P. Dung, “A novel discrete-time model of information diffusion on social networks considering users behavior,” in Proc. 40th Int. Conf. Infor. Networking (ICOIN), IEEE, 2026, pp. 650–655. [15] P. Klepac, S. Kissler, and J. Gog, “Contagion! The BBC Four Pandemic– the model behind the documentary,” Epidemics, vol. 24, pp. 49–59, 2018. [16] J. Liu, T. Saeed, and A. Zeb, “Delay effect of an e-epidemic SEIRS malware propagation model with a generalized non-monotone incidence rate,” Results Phys., vol. 39, Art. no. 105672, 2022. [17] P. Van Mieghem, “Virus spread in networks,” IEEE/ACM Trans. Netw., vol. 17, no. 1, pp. 1–14, 2009. [18] C. Nowzari, V. M. Preciado, and G. J. Pappas, “Analysis and control of epidemics: A survey of spreading processes on complex networks,” IEEE Control Syst., vol. 36, pp. 26–46, 2016. [19] P. E. Pare, J. Liu, C. Beck, B. Kirwan, and T. Basar, “Analysis, estimation, and validation of discrete-time epidemic processes,” IEEE Trans. Control Syst. Technol., vol. 28, no. 1, pp. 79–93, 2020. [20] R. Pastor-Satorras and A. Vespignani, “Epidemic spreading in scale-free networks,” Phys. Rev. Lett., vol. 86, pp. 3200–3203, 2001. [21] R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani, “Epidemic processes in complex networks,” Rev. Mod. Phys., vol. 87, pp. 925–979, 2015. [22] C. V. Pham, Q. V. Phu, H. X. Hoang, J. Pey, and M. T. Thai, “Minimum budget for misinformation blocking in online social networks,” J. Comb. Optim., vol. 38, pp. 1101–1127, 2019. [23] A. Ruhi and B. Hassibi, “SIRS epidemics on complex networks: Concurrence of exact Markov chain and approximated models,” in Proc. 54th IEEE Conf. Decision and Control (CDC), 2015, pp. 2919–2926. [24] P. Shakarian, A. Bhatnagar, A. Aleali, E. Shaabani, and R. Guo, Diffusion in Social Networks. Springer, 2015. [25] K. Sharkey, “Deterministic epidemiological models at the individual level,” J. Math. Biol., vol. 57, pp. 311–331, 2008. [26] T. C. Silva and L. Zhao, Machine Learning in Complex Networks. Cham, Switzerland: Springer, 2016. [27] J. Xie, F. Zhang, K. Wang, X. Lin, and W. Zhang, “Minimizing the influence of misinformation via vertex blocking,” in Proc. IEEE Int. Conf. Data Engineering (ICDE), 2023, pp. 789–801. [28] Y. Wang, D. Chakrabarti, C. Wang, and C. Faloutsos, “Epidemic spreading in real networks: An eigenvalue viewpoint,” in Proc. 22nd Int. Symp. Reliable Distributed Systems (SRDS), 2003, pp. 25–34. [29] Y. Yi, L. Shan, P. Pare, and K. H. Johansson, “Edge deletion algorithms for minimizing spread in SIR epidemic models,” SIAM J. Control Optim., vol. 60, no. 2, pp. 246–273, 2022. [30] M. Youssef and C. Scoglio, “An individual-based approach to SIR epidemics in contact networks,” J. Theor. Biol., vol. 283, pp. 136–144, 2011.
APPENDIX A. Proof of Theorem III.1 Proof. Since S(t) ≤ S(0) for all t ≥ 0, from (1) we I − D + AS(t)B W have v(t + 1) = v(t) ≤ (I − A)S(t)B I − W − D′ Mv(t). Since M ≥ 0, induction yields v(t) ≤ Mt v(0) for all t ≥ 0. Since ρ(M) < 1, there exist γ and C > 0 such that ρ(M) < γ < 1 and ∥Mt ∥ ≤ Cγ t . Thus, ∥v(t)∥ ≤ Cγ t ∥v(0)∥. Since limt→∞ γ t = 0, v(t) converges exponentially to 0. Specifically, limt→∞ x(t) = 0 and limt→∞ y(t) = 0. b = 0 is the unique equilibrium and the system Hence, v (x(t), y(t)) is exponentially stable at the origin for every initial state satisfying the model conditions.
B. Proof of Theorem III.2 Proof. From the choice of qi ∀i ∈ [N ] that we have fixed, Di ≤ Di′ + (1 − qi−1 )Wi for all i, which yields W + Q(I − W − D′ ) ≤ (I − D)Q. Moreover, since GQ F ≥ 0, we have (I − D)Q ≤ MQ Q. Hence, LQ M ≤ MQ LQ , where LQ = [I Q]. Since M ≥ 0, the Perron–Frobenius theorem guarantees the existence of z ≥ 0, z ̸= 0 such that Mz = ρ(M)z. Let u = LQ z. Since qi > 0, we have u ≥ 0 and u ̸= 0. From the above inequality, we obtain MQ u ≥ LQ Mz = ρ(M)u. By the subinvariance property of the Perron–Frobenius theorem [10, Chapter 8], it follows that ρ(M) ≤ ρ(MQ ). C. Proof of Theorem IV.4 Proof. As in the proof of Theorem III.1, since S(t) ≤ S(0), we have v(t + 1) ≤ M−P v(t). Since P∞M−Pt ≥ 0, v(t) ≤ Mt−P v(0). Since ρ(M ) < 1, −P t=0 M−P = (I2N − P∞ −1 M ) , and hence v(t) ≤ (I − M−P )−1 v(0). Let −P 2N t=0 P∞ ux x(0) = (I2N − M−P )−1 . Then, t=0 x(t) ≤ ux . uy y(0) D − AF−P −W We have I2N − M−P = . −(I − A)F−P W + D′ Therefore, (D − AF−P )ux − Wuy = x(0), and −(I − A)F−P ux + (W + D′ )uy = y(0). Under Assumption 2, W + D′ is invertible. From the second equation, uy = (W + D′ )−1 (y(0) + (I − A)F−P ux ) . Substituting into the first equation and using T = W(W + D′ )−1 yields (D − ΘF−P )ux = x(0) + Ty(0). We have det(I2N − M−P ) = det(W+D′ ) det(D−ΘF−P ). Since ρ(M−P ) < 1, det(I2N − M−P ) ̸= 0. Together with the invertibility of W + D′ , this implies that D − ΘF−P is invertible. Therefore, ux = (D − ΘF−P )−1 (x(0) + Ty(0)) . Thus, ∞ X
x(t) ≤ (D − ΘF−P )−1 (x(0) + Ty(0)) .
t=0
Moreover, m(t) − m(0) =
t−1 X
S(τ )B−P x(τ ) ≤ F−P
τ =0
Letting t → ∞ gives m∗ − m(0) ≤ F−P from (3),
t−1 X
x(τ ).
τ =0
P∞
t=0 x(t). Hence,
Φ(P ) = ∥m∗ − m(0)∥1 b ). ≤ 1⊤ F−P (D − ΘF−P )−1 (x(0) + Ty(0)) = Φ(P
D. Proof of Theorem IV.7 Proof. Similar to the proof of Theorem III.2, we can prove that ρ(MQ,−P ) ≥ ρ(M−P ). Since ρ(MQ,−P ) < 1, we have b ). ρ(M−P ) < 1, and Theorem IV.4 gives Φ(P ) ≤ Φ(P i Moreover, Ti = WiW+D ≤ q for all i ∈ [N ], so T ≤ Q ′ i i and Θ = A + T(I − A) ≤ A + Q(I − A) = GQ . Let ZT = D − ΘF−P and ZQ = D − GQ F−P . Then ZT ≥ ZQ . Since ρ(MQ,−P ) < 1 and ρ(M−P ) < 1, we have Z−1 Q ≥ 0
−1 −1 −1 −1 and Z−1 T ≥ 0. From ZQ − ZT = ZQ (ZT − ZQ )ZT ≥ 0, −1 −1 it follows that ZT ≤ ZQ . Moreover, since T ≤ Q, x(0) + Ty(0) ≤ x(0) + Qy(0). Therefore,
b ) = 1⊤ F−P Z−1 (x(0) + Ty(0)) Φ(P T ≤ 1⊤ F−P Z−1 Q (x(0) + Qy(0)) = ΦQ (P ). b ) ≤ ΦQ (P ). Thus Φ(P ) ≤ Φ(P E. Proof of Proposition IV.8 Proof. Let Ξ−P = D − ΘF−P , H(P ) = Ξ−1 −P , and z = x(0) + Ty(0). Consider an edge a = (j, i) ∈ / P and let c = Sii (0)Bij ≥ 0 and d = cΘii ≥ 0. After adding a to the deleted edge set, we have F−(P ∪{a}) = F−P − cui u⊤ j and Ξ−(P ∪{a}) = Ξ−P + dui u⊤ j . By the Sherman–Morrison formula, H(P ∪ {a}) = H(P ) −
dH(P )ui u⊤ j H(P ) 1 + du⊤ j H(P )ui
.
Since M−P ≤ M and ρ(M) P < 1, we have ρ(M−P ) < 1. ∞ k Hence, (I2N − M−P )−1 = k=0 M−P ≥ 0. By the −1 block inverse formula, H(P ) = Ξ−P is the upper-left block of (I2N − M−P )−1 , and therefore H(P ) ≥ 0. Thus, H(P ∪ {a}) ≤ H(P ), i.e., H(P ) is entrywise monotone nonincreasing. Next, Z 1 −1 H(P ) − H(P ∪ {a}) = d (Ξ−P + λdui u⊤ ui u⊤ j ) j 0 −1 · (Ξ−P + λdui u⊤ dλ. j )
Consider P1 ⊆ P2 and a ∈ / P2 . For every λ ∈ [0, 1], F−P1 − λcui u⊤ ≥ F − λcui u⊤ −P2 j j . The corresponding comparison matrices are nonnegative and bounded entrywise by M. Hence, their spectral radii are less than one, and by −1 the Neumann series [10, Chapter 8], (Ξ−P1 + λdui u⊤ ≥ j ) ⊤ −1 (Ξ−P2 + λdui uj ) . Since these matrices are nonnegative, it follows that H(P1 ) − H(P1 ∪ {a}) ≥ H(P2 ) − H(P2 ∪ {a}). Therefore, H(P ) is entrywise supermodular. Finally, using F−(P ∪{a}) = F−P − cui u⊤ j , we obtain ⊤ b b Φ(P ) − Φ(P ∪ {a}) = 1 F−P H(P ) − H(P ∪ {a}) z + c1⊤ ui u⊤ j H(P ∪ {a})z. Since all matrices and vectors above b ) ≥ Φ(P b ∪ {a}), so Φ(P b ) is monotone are nonnegative, Φ(P non-increasing. Moreover, for P1 ⊆ P2 and a ∈ / P2 , we have F−P1 ≥ F−P2 , H(P1 ) − H(P1 ∪ {a}) ≥ H(P2 ) − H(P2 ∪ {a}), and b 1 ) − Φ(P b 1∪ H(P1 ∪ {a}) ≥ H(P2 ∪ {a}). Therefore, Φ(P b 2 ) − Φ(P b 2 ∪ {a}). Hence, Φ(P b ) is monotone {a}) ≥ Φ(P non-increasing and supermodular with respect to P ⊆ Q.