# Group-Based Susceptible-Infectious-Susceptible Model in Large-Scale Directed Networks

Authors: Xu Wang; Bo Song; Wei Ni; Ren Ping Liu; Y. Jay Guo; Xinxin Niu; Kangfeng Zheng
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Epidemic models trade the modeling accuracy for complexity reduction. This paper proposes to group vertices in directed graphs based on connectivity and carries out epidemic spread analysis on the group basis, thereby substantially reducing the modeling complexity while preserving the modeling accuracy. A group-based continuous-time Markov SIS model is developed. The adjacency matrix of the network is also collapsed according to the grouping, to evaluate the Jacobian matrix of the group-based continuous-time Markov model. By adopting the mean-field approximation on the groups of nodes and links, the model complexity is significantly reduced as compared with previous topological epidemic models. An epidemic threshold is deduced based on the spectral radius of the collapsed adjacency matrix. The epidemic threshold is proved to be dependent on network structure and interdependent of the network scale. Simulation results validate the analytical epidemic threshold and confirm the asymptotical accuracy of the proposed epidemic model.


---

## Body

## 1. Introduction

Epidemic models have been widely used to analyze sophisticated interactions in networks, e.g., virus attack and propagation in computer networks [1, 2], rumor spreading in social networks [3], and cascading failures [4]. As a basic epidemic model, the susceptible-infected-susceptible (SIS) model defines two node states (susceptible and infected) and captures two state transition processes, namely, theinfection from infected nodes to susceptible nodes and theself-healing of infected nodes. Earlier epidemic models omit topologies by assuming a network topology of a complete graph [5]. Network topologies, playing a key role in cyber security [6], are later considered and proved to have a strong impact on the epidemic propagation process [7].Epidemic models trade the modeling accuracy for complexity reduction. Markov-chain based epidemic models are able to precisely analyze the epidemic propagation process but require2N Markov states to capture the S/I states of N nodes and therefore can hardly be applied to large-scale networks [7, 8]. A number of topological epidemic models [8–12] decompose the 2N-state Markov process into N small Markov processes. This is achieved by using the expected infection probability of every node instead of the actual node state. A significant result from the models is that the epidemic threshold, under which the epidemic will eventually die out, is given by 1/λ1(A), where λ1(A) is the largest eigenvalue of the adjacency matrix of the network topology [9].Network features, e.g., the degree distribution of scale-free networks [13], can be employed to simplify epidemic models by adopting the degree-based mean-field approach [14]. Specifically, nodes with the same degree are assumed to be infected with the same probabilities. An interesting result of the epidemic in scale-free networks is the absence of an epidemic threshold [15]. The degree-based mean-field approach has extended the SIS process, e.g., the epidemic propagation with incubation and the epidemic with a recovery state [16, 17]. However, the degree-based epidemic model cannot capture epidemic propagations in specific networks.This paper presents a group-based continuous-time Markov model to quantitatively analyze the SIS process in large-scale directed networks. We start with the network modeling, where nodes are categorized into groups according to their connectivity. A collapsed adjacency matrix is proposed to describe the network topology. Based on the node groups, a continuous-time Markov model is proposed to capture the SIS-type propagation, where the state of a group is estimated by taking the mean-field approximation. Focusing on the problem of epidemic threshold, the proposed nonlinear model is linearized via omitting high-order terms around the disease-free point. The epidemic threshold is derived by performing matrix analysis on the Jacobian matrix of the linearized model and then validated by simulations. The key contributions of this paper can be summarized as follows:(i)
We propose a new modeling method, which groups nodes with the same connectivity in directed networks and models the epidemic propagation of the groups by using continuous-time Markov SIS models.(ii)
By taking the mean-field approximation, the proposed SIS model is asymptotically accurate with the decrease of effective spreading rate and/or the increase of node groups.(iii)
Linearization and stability analysis are carried out on the proposed SIS model to deduce the epidemic threshold, under which the epidemic eventually becomes extinct.(iv)
The epidemic threshold is proved to be dependent on network structure and interdependent of the network scale.Comprehensive simulations confirm the validity of the proposed mean-field epidemic model and the deduced epidemic threshold in large-scale networks.The rest of this paper is organized as follows. In Section2, related works are reviewed. In Section 3, the directed network model is presented, followed by the proposed mean-field SIS model in Section 4. In Section 5, numerical and simulation results are provided, followed by conclusions in Section 6.


## 2. Related Work

The SIS model was firstly developed for biological infectious diseases, which defines two states for a node, i.e., susceptible or infected [5]. A susceptible node can be infected with probability β by an infected neighbor. An infected node can be cured with probability γ. Recently, various states were introduced into the SIS model. Kephart et al. [18] and Vojnovic et al. [19] proposed a new “warning” state at every node, in addition to the “infected” and “susceptible” states. The probability of a node switching to the “warning” state depends on the population of nodes in the warning state and is independent of the network topology. The SIS model was extended with “quarantined”, “vaccinated”, and “delay” states, to capture the time-delayed worm propagation in computer networks [20]. These models significantly simplified the dynamic process by omitting the impact of network topologies.The network topologies can have a strong impact on epidemic propagations [11]. In [8], the continuous-time Markov process was adopted to model epidemic propagations in specific topologies, where every Markov state collects the states of all nodes in the network. The second largest eigenvalue of the Markov transition matrix determines the convergence rate to the absorbing virus-free state. With a discrete-time Markov model, the convergence rate was proved to be asymptotically bounded [7]. The Markov models can be decomposed into N small Markov processes in N-node networks by applying the mean-field theory to achieve tractability [8, 10–12]. The decomposed N Markov processes deduced a widely approved result that a virus dies out quickly if β/γ<1/λ1(A), where A is the adjacency matrix of the network, and λ1(A) is the largest eigenvalue of A. The network can also be dynamic, where nodes can transfer among communities [21]. The simulation results on two communities revealed that the node mobility can accelerate the malware propagation and improve the epidemic threshold.Some network features can be employed to simplify epidemic models and improve tractability. Pastor-Satorras et al. [15] derived the probability of a node being infected as a function of the expected number of its infected neighbors in scale-free networks. The number of infected nodes at the equilibrium state was given by ρ≈2e-1/mτ, where m is a network generation parameter and τ is the effective spreading rate. Zou et al. [22] simulated the propagation of Internet email worms in scale-free graphs and showed that the aforementioned result can be overestimated due to the implicit homogeneous mixing assumption. Meanwhile, Li et al. showed the analysis on scale-free graphs is inaccurate for specific topologies [23].The statistic topology models are generally based on undirected networks. However, there is an intrinsic directionality in the propagation in specific types of dynamics, e.g., infectious disease spreading [24] and information transmission [25]. Directed networks, sets of vertices, and a collection of directed edges that connect pairs of ordered vertices are useful to represent specific transmissions with intrinsic directionality in the propagation [14]. Meyers et al. [26] employed the percolation theory to predict disease transmission through semidirected contact networks, where edges may be directed or undirected and found that the probability of an epidemic and the expected fraction of a population infected during an epidemic can be different in semidirected networks, in contrast to the routine assumption that these two quantities are equal. Li et al. [27] defined the directionality ξ as the percentage of unidirectional links and found that the lower bound of the epidemic threshold increases with a growing ξ, implying that the directionality hinders the propagation of epidemic processes. In [28], Khanafer et al. studied the stability of an SISN-intertwined Markov model over arbitrary directed network topologies and showed that when the basic reproduction number is greater than one, the epidemic state is locally exponentially stable, and when the network is not initialized at the disease-free state, the epidemic state is globally asymptotically stable.


## 3. The Directed Network Model

We consider the SIS epidemic process in a strongly connected network withN nodes connected by directed edges. Each node in the network can be in either a susceptible (S) or an infected (I) state. An infected node can infect its susceptible neighbors along the directed edges at the rate of β per edge. Infected nodes can independently recover to be susceptible at the rate of γ.We suppose that theN nodes in a network G can be categorized into n groups, denoted by G1, G2, ⋯, Gn, where the nodes in the same group have the same out-degrees and the same number of edges to the nodes in the same destination group. The number of Gi-nodes can be denoted by Ni (here, ∑i‍Ni=N). Given the node groups, we define a collapsed adjacency matrix, denoted by A, to describe the topology of G. The (i,j)-th entry of the matrix, denoted by aij, describes the number of edges from a Gi-node pointing to Gj-nodes. As a result, G can be described by the node number vector N=[N1,N2,…,Nn] and the collapsed adjacency matrix A. Figure 1 provides an example of node categorization, where N=7 nodes are categorized into n=3 groups, i.e., N=[2,3,2]. Its collapsed adjacency matrix can be given by(1)A=a11a12a13a21a22a23a31a32a33=030012100Figure 1
An example of networks we considered where 7 nodes are categorized into three groups according to the connection between them.Other notations are defined as follows:[A]i (A∈{S,I}) denotes the number of Gi-nodes in state A. ABij denotes an edge starting from a Gi-node and ending at a Gj-node, where the Gi-node and the Gj-node are in states A and B, respectively. [AB]ij denotes the number of ABij edges. Let ABCijk ([ABC]ijk′) denote the number of edge pairs consisting of ABij and BCjk (ABij and CBkj), as illustrated by Figure 2. Numerical relationships between states of nodes and states of edges satisfy(2a)Ni=Si+Ii;(2b)aijNi=SSij+SIij+ISij+IIij;(2c)aijSi=SSij+SIij;(2d)aijIi=ISij+IIij;(2e)Si=Ni-Ii=Ni-1aijISij+IIij.Here, (2a) is because any node is in either an S or I state. (2b) is because any edge is in one of the four states given in the right-hand side (RHS) of (2b). Meanwhile, edges can be classified according to the state of the starting point, as given by (2c) and (2d). (2e) is deduced from (2a), (2b), and (2d).Figure 2
An example ofABCijk and ABCijk′.


## 4. Group-Based Mean-Field SIS Model

We propose to analyze the SIS process in directed networks by employing the mean-field approximation which uses a single average effect to approximate the effect of all the other individuals on any given individual. Thus, the same group of nodes in our model are evaluated by the same average estimation. The state transitions of nodes and edges in the SIS process can be given by(3a)dSidt=γIi-∑jβISji;(3b)dIidt=-γIi+∑jβISji;(3c)dSSijdt=γSIij+γISij-∑kβISSkij-∑kβSSIijk′;(3d)dSIijdt=-γSIij+γIIij+∑kβSSIijk′-∑kβISIkij;(3e)dISijdt=-γISij+γIIij-βISij+∑kβISSkij-∑kβISIijk′;(3f)dIIijdt=-2γIIij+βISij+∑kβISIkij+∑kβISIijk′.Here, (3a) and (3b) give the changing rate of susceptible and infected Gi-nodes. The RHS is because an infected Gi-node can be cured with the rate γ; a susceptible Gi-node can be infected with the rate β per edge by an infected Gj neighbor. In the continuous-time model, the time slot is infinitesimal that the infection rate can be summed together, i.e., ∑jβISji.Equations (3c)-(3f) capture the time-varying number of links. The first two terms on the RHS of (3c) are because an SSij edge can transfer from an SIij or ISij edge when the infected node is cured. The last two terms on the RHS of (3c) capture the cases where the starting Gi-node or the ending Gj-node is infected by its infected neighbors. (3d) is because an SIij edge can transfer to an SSij edge in the case that the infected Gj-node is cured at the rate γ; and to IIij in the case that the susceptible Gi-node is infected by its infected neighbors. SIij can transfer from IIij in the case that the infected Gi-node is cured with the rate γ or from SSij in the case that the susceptible Gj-node is infected by its infected neighbors. Different from previous SIS models in undirected networks, e.g., [15], SIij cannot transfer to IIij, as the epidemic can only propagate along directed edges. Equation (3e) can be similarly obtained attaching the infection process, i.e., -β[IS]ij. Equation (3f) is self-explanatory.Known as the disease-free equilibrium point, the equilibrium point of interest is([SI]ij,[IS]ij,[II]ij)=(0,0,0); i.e., all nodes are susceptible. The condition of the disease-free equilibrium point can be deduced by linearizing the SIS model given by (3a)–(3f). This is because the stability of the original nonlinear system can be determined by the eigenvalues of the linearized model as stated in Lyapunov’s First Method [29].To linearize the SIS model, the number of edge pairsABCijk and ABCijk′ is first estimated by using the number of unpaired edges. This is achieved by applying the moment closure approximation as evaluated in [30, 31]. As a result, we have(4a)ISSkij=ISkiSSijSi=ISkiSSijNi-ISip+IIip/aip;(4b)SSIijk′=ISkjSSijSj=ISkjSSijNj-ISjq+IIjq/ajq;(4c)ISIkij=ISkiSIijSi=ISkiSIijNi-ISip+IIip/aip;(4d)ISIijk′=ISijISkjSj=ISijISkjNj-ISjq+IIjq/ajq.In (4a), every susceptible Gi-node on average has SSij/Si edges pointing to Gj-nodes. Si is then estimated by employing (2e), where p and q are introduced to solve the equation. Here, p satisfies ISip+IIip>0 and aip>0; q satisfies ISjq+IIjq>0 and ajq>0. (4b)-(4d) can be similarly obtained.By substituting (4a)–(4d) into (3a)–(3f), (3c)-(3f) can be rewritten as(5a)dSSijdt=γSIij+γISij-∑kβISkiSSijNi-ISip+IIip/aip-∑kβISkjSSijSj;(5b)dSIijdt=-γSIij+γIIij+∑kβISkjSSijNj-ISjq+IIjq/ajq-∑kβISkiSIijNi-ISip+IIip/aip;(5c)dISijdt=-γISij+γIIij-βISij+∑kβISkiSSijNi-ISip+IIip/aip-∑kβISijISkjNj-ISjq+IIjq/ajq;(5d)dIIijdt=-2γIIij+βISij+∑kβISkiSIijNi-ISip+IIip/aip+∑kβISijISkjNj-ISjq+IIjq/ajq.The terms of [SS]ij can be suppressed by substituting (2b) into (5a)–(5d). As a result, we have(6a)dSIijdt=-γSIij+γIIij+∑kβISkjaijNi-SIij-ISij-IIijNj-1/ajqISjq+IIjq-∑kβISkiSIijNi-1/aipISip+IIip;(6b)dISijdt=-γISij+γIIij-βijISij+∑kβISkiaijNi-SIij-ISij-IIijNi-1/aipISip+IIip-∑kβISijISkjNj-1/ajqISjq+IIjq;(6c)dIIijdt=-2γIIij+βISij+∑kβISkiSIijNi-1/aipISip+IIip+∑kβISijISkjNj-1/ajqISjq+IIjq.Near the disease-free equilibrium point, (6a)–(6c) can be linearized by suppressing all higher order terms. As a result, we have(7a)dSIijdt≈-γSIij+γIIij+∑kβaijNiISkjNj;(7b)dISijdt≈-γ+βISij+γIIij+∑kβaijISki;(7c)dIIijdt≈-2γIIij+βISij.After the model has been linearized, the condition of the disease-free equilibrium point can be obtained by performing eigenvalue analysis on the Jacobian matrix of the linearization. The Jacobian matrix is a3n2×3n2 matrix and denoted by J. The nonlinear dynamic system is stable at the equilibrium point if and only if all the eigenvalues of the Jacobian matrix are negative, as stated by the Hartman-Grobman Theorem [32]. In other words, the epidemic is certainly extinct if(8)λ1J<0,where λ1(·) is the largest eigenvalue of the operator. J is the Jacobian matrix of (7a)–(7c) and can be given by(9)
J
=
J
11
J
12
J
13
J
21
7
J
21
J
22
J
23
J
31
J
32
J
33
=
J
11
J
12
J
13
0
J
∗
,where J11 is an n2×n2 diagonal matrix whose diagonal entries are -γ. We note that J21 and J31 are zero matrices. As a result, J is an upper block triangular matrix, and(10)λJ=λJ11∪λJ∗,where λ(·) is the set of eigenvalues of the operator.Here,J23, J32, and J33 are n2×n2 diagonal matrices. Their diagonal entries are γ, β, and -2γ, respectively. The entry in the (n(i-1)+j)-th row, (n(k-1)+l)-th column of J22, denoted by Jij,kl22, is given by(11)Jij,kl22=aijβ-γ+β,ifij=kl,i=l-γ+β,ifij=kl,i≠laijβ,ifij≠kl,i=l0,ifij≠kl,i≠l.By employing the Schur complement, i.e.,(12)J22J23J32J33I0-J33-1J32I=HJ230J33,we have λ(J∗)=λ(J33)∪λ(H), where H=J22-J23J33-1J32. The entry in the (n(i-1)+j)-th row, (n(k-1)+l)-th column of H, denoted by Hij,kl, is given by(13)Hij,kl=aijβ-γ+β2,ifij=kl,i=l-γ+β2,ifij=kl,i≠laijβ,ifij≠kl,i=l0,ifij≠kl,i≠l.We conclude thatλ(J)=λ(J11)∪λ(J33)∪λ(H). Note that J11 and J33 are diagonal matrices, and all the diagonal entries of them are negative, i.e., all the eigenvalues of J11 and J33 are negative. As a result, we have(14)λ1J<0⇔λ1H<0.The matrixH can be written as(15)H=P+Q,where Q is a diagonal matrix and can be given by Q=diag[-(γ+β/2)]. The entry in the (n(i-1)+j)-th row, (n(k-1)+l)-th column of P, denoted by Pij,kl, is given by(16)Pij,kl=aijβ,ifi=l0,otherwise.We have that all the eigenvalues of Q are -(γ+β/2) and(17)λH=λP-γ+β2.Note thatP is a n2×n2 sparse matrix and similar with a block matrix consisting of βA and zero matrices as given by(18)
P
=
X
-
1
β
A
0
0
0
X
.This is achieved by performing matrix operations on P. Thus, the eigenvalues of P can be given by(19)λP=β×λA∪0.Combining (8), (14), (17), and (19), the epidemic will become extinct if βλ1(A)-(γ+β/2)<0. In other words, the epidemic threshold, denoted by τ∗, is given by (20)τ∗=1λ1A-1/2.The epidemic dies out, if τ=β/γ<τ∗.


## 5. Simulation and Numerical Results

In this section, numerical and simulation results are presented to validate the proposed group-based SIS model and the deduced epidemic threshold. In every run of the simulations, the groups and the network topology, i.e., the scale and structure, are first set up, according to the rules specified in Section3; i.e., aij number of directed edges are added from a Gi-node to aij number of randomly selected Gj-nodes. The nodes do not connect themselves despite aii≥0. Then, the infection rate β and the curing rate γ are configured, based on the analytical epidemic threshold τ∗. The simulations are carried out on the NepidemiX [33], which is a Python library implementing simulations of epidemics. For initialization, randomly selected 10% of the nodes are infected. During a simulation run, the infected nodes can be cured at the rate of γ. Every infected node can infect its neighbors connected by edges at the rate of β. Every dot in the figures is the average of 100 independent runs under the same configurations, including the network topology, the percentage of initially infected nodes, β and γ.We first validate our model on a 1000-node network where nodes connect each other and form a complete graph. The infection and curing rates are set to beβ=0.0005 and γ=0.1 per time slot. τ=β/γ=0.005 is set to be larger than τ∗=0.001 to evaluate the proposed model. Ten percent of nodes are randomly chosen to be infected at t=0. Figure 3 plots the infection density, given by ∑[I]i/N, from t=0 to 30. The analytical results are numerically evaluated by employing (6a)–(6c) with the nodes evenly divided into 1, 2, 5, 10, 25, and 50 groups, respectively.Figure 3
The growth of infection density where a complete graph with 1000 nodes is considered.β=0.0005 and γ=0.1. The analytical results are obtained based on (6a)–(6c) by evenly dividing the nodes into 1, 2, 5, 10, 25, and 50 groups.From Figure3, we can see that the analytical results can asymptotically approach the simulation results with the increasing number of groups, e.g., from n=1 to n=50. The simulation results can outgrow the analytical results when the number of node groups is small. The analytical results under a single group of nodes, i.e., n=1, can substantially underestimate the infection density. The analytical result is only 83.8% (0.67/0.8) of the simulation result, when t=30. In contrast, the analytical results under 50 groups of nodes, i.e., when n=50, match the simulation results indistinguishably. This is because the proposed model is designed to decouple the state transitions of edges connecting nodes from different groups and estimate the number of edges connecting infected nodes and subsequently the population of infected nodes. The mean-field approximation is applied to model the interplay between the averaged ratios of infectious edges connecting different pairs of node groups. With an increasing number of node groups, the averaged ratio of infectious edges connecting a specific pair of node groups can become increasingly representative with a reducing deviation. In other words, the averaged ratio becomes increasingly precise for a reducing set of edges. In the special case where every node forms a group (i.e., the number of groups is n=1000), the ratio is exactly the probability at which an edge is infectious. The proposed model is able to capture the state transition of an edge under the averaged effect of all other individual edges, and can be fairly accurate given the large number of edges. Note that the number of groups, e.g., n=50, is far less than the network size, i.e., 1000. This finding allows us to model the epidemic propagation with a small number of differential equations. Figure 3 also shows that the analytical results can be accurate at the initial stage (or low infection densities) even with few node groups. This is because the state transitions of different edges are loosely coupled if only very few nodes are infected.We proceed to evaluate the model accuracy with different infection densities. This is done by adjusting the infection rate. A 1000-node network is considered where nodes connect each other and form a complete graph. The epidemic propagation with four effective spreading rates, i.e.,τ=β/γ=0.002,0.0015,0.0011, and 0.001, are simulated and analyzed. The values of τ are larger than, and close to, the analytical threshold. The infection rates are obtained by adjusting β while setting γ to 0.1. The analysis is based on (6a)–(6c) by evenly dividing the nodes into 5 groups to explore the applicability of the model to a small number of groups.From Figure4, we can see that the simulation results still overtake the analytical results when τ=0.0015 and 0.002. For example, the simulation result is 0.459 in the case of t=40 and τ=0.002, while the analytical result is only 0.418. However, the gap between simulation results and analytical results decreases with dropping τ, i.e., from τ=0.002 to 0.0015. When τ further declines, i.e., τ=0.0011 and 0.001, the analytical results are able to match the simulation results from the beginning to the end. According to (20), the epidemic threshold is given by τ∗=0.001. This figure reveals that the proposed mean-field model is asymptotically accurate with a decreasing τ and is able to precisely describe the epidemic propagation when the effective spreading rate is around the epidemic threshold.Figure 4
The infection density with the growth of time where a complete graph with 1000 nodes is considered. The analytical results are obtained based on (6a)–(6c) by evenly dividing the nodes into 5 groups where τ=β/γ=0.002,0.0015,0.0011, and 0.001, respectively.We evaluate the epidemic thresholdτ∗ given by (20) in Figure 5. Three networks with 500 nodes are considered, where nodes are divided into three groups (i.e., N=[100,200,200]). The impact of the network topology on the threshold is evaluated by varying the number of edges in the network. Without loss of generality, their collapsed adjacency matrix A is set to(21)A=α102020102020102020,where α=4,6, or 8. The curing rate γ is set to be 0.1. Ten percent of nodes are randomly selected to be infected at the initial state. The infection density at t=1000 is used as the stable infection density, as indicated by the y-axis. Evaluated with (20), the epidemic threshold is τ∗= 0.005, 0.0033, and 0.0025 when α= 4, 6, and 8, respectively. We can see from Figure 5 that τ∗ (the solid vertical lines) can precisely specify the epidemic thresholds. When τ<τ∗, the epidemic can be suppressed eventually. When τ>τ∗, the infection density grows with τ and also exhibits convexity. We can see that the network topology has a strong impact on the epidemic threshold and the infection density. Specifically, the threshold decreases with the growth of α. For example, τ halves from 0.005 to 0.0025, when α doubles from 4 to 8 (the number of edges doubles, as well). The infection density increases with the growth of α, especially around the threshold. For example, in the case of α=8 and τ=0.005, the infection density is 0.5 as compared to the infection density of α=4.Figure 5
The validation of epidemic threshold given by (20), where the y-axis is the infection density at t=1000. Three networks with 500 nodes are considered. γ is set to be 0.1. α=4,6,8 is used to adjust the number of edges.We note that the epidemic threshold, given by (20), is determined by the network structure A, rather than the number of nodes given by N. To illustrate this, we compare the number of infected populations in different scales of networks, illustrated by Figure 6. To be specific, N=δ×[10,20,20], where δ=2,4 and 6, respectively. Their collapsed adjacency matrices are obtained with (21) by letting α=1. As a result, τ∗=0.02. Figure 6 firstly confirms the accuracy of τ∗ illustrated by the solid vertical line. The observation that the three networks with the same structure but different scales share the same epidemic threshold validates that the epidemic threshold depends on the network structure rather than the scale. This finding can significantly reduce the complexity to deduce the epidemic threshold, i.e., from decomposing an N-dimensional matrix by using 1/λ1(A), given by [12], to decomposing an n dimensional matrix (n≪N). For example, N=1000 and n=5 in Figure 4, and N=500 and n=3 in Figure 5. It is interesting to notice that the infection densities are the same, e.g., 79.6/100≈158.8/200≈240/300 in the case of τ=0.1, although the infected population varies in different scales of networks. This can be the reason of that the epidemic threshold depends on the network structure rather than the network scale.Figure 6
The validation of epidemic threshold, where they-axis is the infected population at t=1000. Different scales of networks (N=100, 200, and 300, respectively) are considered. γ is set to be 0.1.


## 6. Conclusion

In this paper, we designed a continuous-time SIS model in large-scale networks. By categorizing nodes into groups, the model complexity was significantly reduced. The proposed epidemic model was validated to be asymptotically accurate with the decrease of the effective spreading rate and/or the increase of node groups. The epidemic threshold can be deduced with the largest eigenvalue of the collapsed adjacency matrix whose dimension is much smaller than the network scale. Simulation results corroborated the effectiveness of the model, as well as the analytical accuracy of the threshold in large-scale networks.



---

*Source: 1657164-2019-01-16.xml*