The optimal edge for containing the spreading of SIS model

Numerous real-world systems, for instance, the communication platforms and transportation systems, can be abstracted into complex networks. Containing spreading dynamics (e.g., epidemic transmission and misinformation propagation) in networked systems is a hot topic in multiple fronts. Most of the previous strategies are based on the immunization of nodes. However, sometimes, these node--based strategies can be impractical. For instance, in the train transportation networks, it is dramatic to isolating train stations for flu prevention. On the contrary, temporarily suspending some connections between stations is more acceptable. Thus, we pay attention to the edge-based containing strategy. In this study, we develop a theoretical framework to find the optimal edge for containing the spreading of the susceptible-infected-susceptible model on complex networks. In specific, by performing a perturbation method to the discrete-Markovian-chain equations of the SIS model, we derive a formula that approximately provides the decremental outbreak size after the deactivation of a certain edge in the network. Then, we determine the optimal edge by simply choosing the one with the largest decremental outbreak size. Note that our proposed theoretical framework incorporates the information of both network structure and spreading dynamics. Finally, we test the performance of our method by extensive numerical simulations. Results demonstrate that our strategy always outperforms other strategies based only on structural properties (degree or edge betweenness centrality). The theoretical framework in this study can be extended to other spreading models and offers inspirations for further investigations on edge-based immunization strategies.

Appendix A 13

Introduction
The subject of containing spreading dynamics in networked systems has attracted substantial attention from multiple fronts, for instance, network science, statistical physics, and computer science. Some common spreading dynamics, including the epidemic transmission [1,2] and misinformation spreading [3,4], can influence all aspects of an individual's life and cause great impacts to the socioeconomic systems. The study of containing these spreading dynamics is of both theoretical and practical importance. Before getting into the problem of spreading containment, it is necessary to build suitable models to describe the spreading dynamics. Researchers have proposed various models for different spreading cases. For instance, the classic susceptible-infectedsusceptible (SIS) model [5] and the susceptible-infected-recovered (SIR) model [6,7], along with many of their extensions [8,9,10], have been widely applied to describe the spreading of disease or simple information (e.g., rumors). In these simple contagions, the susceptible individuals could be infected by a single contact with the infected ones. When it comes to modeling some complex information spreading, such as the behavior adoption [11] and political information [12,13], the susceptible individuals first assess the legality of the information and conduct a risk assessment. Then, they become infected with a probability that increases with the cumulative number of contacts with infected individuals. This mechanism is referred to as the social reinforcement [14,15]. The classical threshold model and other models extended from it incorporate this mechanism for complex contagions. More spreading models with other complex mechanisms are discussed in [16].
Based on different spreading models, researchers go further to develop containing strategies for the spreading dynamics. An effective containing strategy is supposed to effectively increase the spreading outbreak threshold [17] or decrease the outbreak size [18]. Many target containing strategies have been proposed, for instance, immunizing a fraction of nodes according to the centrality indexes of them, like their degree, betweenness, closeness, PageRank, and eigenvector centrality [19,20,21,22,23,24,25]. However, in the real-life, the identification of centrality-defined individuals sometimes can be time-consuming. Thus, researchers come up with strategies that do not rely on any centrality indexes of the nodes, such as the acquaintance immunization strategy [26,21,27,19,26], which is more suitable for practical applications. Besides, many containing strategies inspired by the methods from optimization and control [28,29,30,31,32,33,34] have been proposed by researchers as well. There are also some specific containing strategies for networks in different categories, for instance, the multiple networks [35], adaptive networks [36], and temporal networks [37].
All the strategies mentioned above are based on the immunization of nodes. However, these strategies are difficult to be put into practice sometimes. For instance, it is dramatic to isolate a fraction of train stations in the whole country for preventing the spreading of flu on the train transportation network, but it is more acceptable to suspend some connections in the network. Thus, the study of edge-based containing strategies should be emphasized. Some researchers have proposed strategies of deactivating edges selected by the properties of the adjacent nodes or the edges themselves [38,39]. Besides, some strategies incorporate both the structural characteristics of the network and parameters of the spreading process [40].
This study focus on the subject of determining the optimal edge for containing the spreading of the SIS model on complex networks. The theoretical framework we developed can find out the optimal or near-optimal edge for the spreading containment of the SIS model. By developing a perturbation method to the discrete-Markovianchain equations of the SIS model, we obtain a formula that approximately provides the decremental outbreak size after deactivating a certain edge in the network. Then, we determine the optimal edge by simply selecting the one with the largest decremental outbreak size. It is worth mentioning that the information of both network structure and spreading dynamics is considered in our theoretical framework.
The paper is organized as follows. Sec. 2 provides the model description. The detailed theoretical analysis is presented in Sec. 3. Then, we present the numerical simulations in Sec. 4. Finally, we provide a conclusion in Sec. 5.

Model description
In this study, we consider the classic SIS model on a complex network G of N nodes and M edges. The SIS model is extensively applied to describe the spreading of simple information or disease. Each node in this model can be in two different states, that is, the susceptible state (S) and the infected state (I). Initially, we select a small fraction of nodes to be the infected seeds, keeping the others in the S state. Then, for every time step, each infected node tries to infect neighbors in the S state with probability λ. Afterward, all the nodes in the I state return to the S state with probability γ. Without loss of generality, we set γ = 0.5 in this study. Eventually, the dynamic system will reach the steady-state on network G, where the fraction of nodes in the I state fluctuates around a certain value ρ, that is, the outbreak size.
Let A be the adjacency matrix of the network G. Thus, A should be a square N × N matrix such that its element A ij = 1 when there is an edge between node i and j, and A ij = 0 when there is no edge. Previous studies [41,42] have demonstrated that the spreading outbreaks when the effective transmission probability β = λ/γ is larger than the reciprocal of the leading eigenvalue ω of A. That is to say, if λ c /γ = 1/ω, then the spreading will break out only when λ is larger than the critical value λ c = γ/ω. Otherwise, if λ < λ c , then no outbreaks will be observed, and no containing process is needed. Therefore, we focus on the case when λ > λ c in this study.
After deactivating a specific edge (i 0 , j 0 ) in the networks G, we get a new network G ′ . And the adjacency matrix A ′ of G ′ should be where the elementȦ ij = 1 only when (i, j) ∈ {(i 0 , j 0 ), (j 0 , i 0 )}. Denote ρ ′ as the outbreak size on the new network G ′ . We aim to find the optimal edge, which, if deactivated, can maximize the decremental outbreak sizeρ = ρ − ρ ′ .

Theoretical analysis
In this section, we first present the Discrete-Markovian-chain (DMC) approach [42,43] for the SIS model on the network G. Then, using a perturbation method for the DMC, we derive a formula that approximately provides the decremental outbreak size after deactivating an edge in the network G. Finally, using the formula, we study the problem of determining the optimal edge, which, if deactivated, can maximize the decremental outbreak size.

The Discrete-Markovian-chain approach for the SIS model
In this subsection, we adopt the discrete-Markovian-chain (DMC) approach to study the SIS model on the network G. The DMC approach can accurately predict the phase diagram for contact-based spreading dynamics in complex networks and overcomes the computational cost of Monte Carlo simulations [42].
To begin with, we define a set of discrete-time equations for the probability of individual nodes to be infected. Denote I i (t) as the probability that node i is in the I state at time t. Then, the node i is in the S state at time t with probability S i (t) = 1 − I i (t). If i is in the I state at t + 1, then either it was in the I state at t and has not recovered, or it was in the S state at t and has been infected by its infected neighbors. Thus, the evolution of I i (t) is where 1 − Θ i (t) is the probability that node i gets infected at time t, and When the dynamic system reaches the steady state, we have Taking all the nodes into consideration, the Eqs. (2) and (3) can be written in terms of vectors in the steady state as and where I and Θ are vectors of length N with entries I = ( I 1 , · · · , I N ) T and Θ = ( Θ 1 , · · · , Θ N ) T , respectively, and • denotes component-wise vector product. Combing the Eqs. (4) and (5), we obtain the expected outbreak size of the spreading on networks G as follows: 3.2. Determining the optimal edge for containing the spreading For convenience, we denote the new network we get after deactivating the specific edge l in the original network by G ′ l . Besides, the decremental outbreak sizeρ of the SIS model on network G after deactivating the specific edge l is denoted byρ l . The spreading outbreak size ρ l on the new network G l depends on the position of edge l. In this subsection, we introduce a perturbation method to obtain an approximate estimate of the decremental outbreak sizeρ l = ρ − ρ l after the deactivation of edge l. Then, we use the approximate estimate to determine the optimal edge, which, if deactivated, can maximize the decremental outbreak sizeρ.
Inferring from Eq. (1), we get the DMC equations of network G l as follows: and On the consideration that the fixed point I(∞) = [I 1 (∞), · · · , I N (∞)] T of G l will stays close to the fixed point I of G since only one edge has been deactivated, we iterate Eqs. (7) and (8) with initial condition I(0) = I. Then, we employ the decomposition of I(t) = I +İ(t) and Θ(t) = Θ +Θ(t). According to Appendix A, we can obtain the iteration formula ofİ(t) aṡ where Ψ is the N × N diagonal matrix with entries Ψ ij = 1/(1 − λ I j ) for i = j and Ψ ij = 0 for i = j. This equation can be written in terms of matrix multiplication as follows:İ where and Here, diag (·) denotes the diagonal matrix with the elements of the input vector as diagonal entries. Thus, the stationary solutionİ(∞) of the perturbed system satisfieṡ or in the closed forṁ Thus, an explicit relation between the deactivated edge l and the decremental outbreak size can be found aṡ In order to solve Eq. (15), we decompose Ξ as Ξ = Ξ 0 +Ξ, where depends only on A, anḋ depends only onȦ. For any edge l = (i, j), the matrixȦ can be written as sum of two outer productsȦ where u, v are vectors of length N with u k = δ k,i and v k = δ k,j for 1 ≤ k ≤ N. Define short notations as then it's easy to check thaṫ The Sherman-Morrison formula says that where Apply the Sherman-Morrison formula again gives where Again define short notations for convenience as follows, Then ξ can be checked satisfying By substituting Eq. (21) and Eq. (26) into Eq. (15), we can geṫ According to Eq. (23), we carefully expand Eq. (27) and geṫ Eq. (28) approximately provides the decremental outbreak size after deactivating the edge l = (i, j) in the network G. We can use the formula to determine the optimal edge for containing the spreading of the SIS model by simply selecting the edge with the highestρ l . As one can see, we obtain Eq. (28) through complicated derivations. Look into the right-hand of Eq. (28), we can observe that it incorporates both the information of networks structure (i.e., the adjacency matrix A) and spreading dynamics (i.e., λ, γ, I and Θ). Sec. 4 will show that Eq. (28) gives good predictions of the decremental outbreak size.

Simulation results
For convenience, we refer to the containing strategy of deactivating the optimal edge L selected by Eq. (28) as the perturbation-based-strategy (PBS). In this section, extensive numerical simulations are performed to verify the containing performance of the PBS. Both synthetic and real-world networks are considered in our simulations. Note that the DMC approach can predict the results of the Monte Carlo simulations accurately and have a lower computational cost; thus, we conduct our numerical simulations based on the DMC approach instead of the Monte Carlo method [42]. According to Sec. 3, the proposed PBS in this study incorporates the information of both network structure and spreading dynamics. To better understand the importance of dynamic information in the PBS, we employ two contrast strategies that only consider the structure of networks. Denote f b as the edge betweenness centrality. Besides, the edge betweenness of the specific edge l = (i, j) is denoted by f b l . The first contrast strategy is to deactivate the edge with the highest f b . We refer to this strategy as betweenness-centrality-strategy (BCS) and the specific edge selected by the BCS as L B . Similarly, the second contrast strategy is based on the degree k of nodes; thus, it can be referred to as degree-based-strategy (DBS). Specifically, for the DBS, we select the edge with the highest degree product f d . For the specific edge l = (i, j), the degree product should be f d l = k i k j . The edge selected by the DBS is denoted by L D . First, we perform the containing strategies on two synthetic networks G 1 and G 2 . Both of them are scale-free (SF) networks with degree distribution p(k) ∼ k −α , where α denotes the degree exponent. We set α 1 = 2.3 and α 2 = 3.0 as the degree exponent of network G 1 and G 2 , respectively. One can find more information about the two networks in Tab. 1. Denoteρ as the decremental outbreak size obtained by simulations after deactivating the selected edge. Then, we rank the edges according to the values ofρ. We refer to this kind of edge rank as numerical rank r in the rest of the paper. To compare the performance of the strategies, we are particularly concerned about the optimal edges L, L B , and L D selected by PBS, BCS, and DBS, respectively. We compute the normalized numerical rank R = r/M of edges L, L B and L D . The smaller the R, the better the performance. As shown in the Figs. 1 (a) and (b), the DBS performs well on both synthetic networks when λ near the critical value λ c , but the performance fails quickly when λ becomes large. The BCS performs well only for several values of λ. However, the PBS performs well on both networks for all the values of λ. Figs. 1 (c) and (d) show the correspondingρ of edges L, L B and L D on the synthetic networks G 1 and G 2 , respectively. The larger theρ, the better the performance. By comparing theρ of L, L B and L D , we can draw the same conclusion as that demonstrated from Figs. 1  (a) and (b).
Second, we investigate the overall correlations between the edge ranks scored by Eq. (28) and the numerical ranks. To begin with, we compare the decremental outbreak sizeρ numerically computed by Eq. (28) with the decremental outbreak sizeρ obtained by simulations. Setting λ = 0.1, the results ofρ versusρ on the synthetic networks G 1 and G 2 are shown in the Figs. 2 (a) and (b), respectively. The results demonstrate that the values ofρ andρ are almost linearly correlated; that is to say, Eq. (28) can predict the decremental outbreak size well. To better understand the rank correlations for all the values of λ, we employ the Spearman rank correlation coefficient [44,45] to quantify the mentioned correlations. The Spearman rank correlation coefficient is defined as wherer l andṙ l are the ranks of edge l scored byρ andρ, respectively. Figs. 3 (a) and (b) shows the results of m s versus λ on the synthetic networks G 1 and G 2 , respectively. It can be seen that the value of m s keeps close to 1 for all the values of λ on both networks. That is to say, the edge ranks predicted by the Eq. (28) and the numerical ranks are strongly correlated for all the values of λ. Similarly, we also compute the Spearman rank correlation coefficient between the edge ranks scored by f b and the numerical ranks, along with the Spearman rank correlation coefficient between the edge ranks scored by f d and the numerical ranks. As shown in Figs. 3 (a) and (b), the edge ranks scored by f b or f d is positively correlated with the numerical ranks only when λ is near the λ c . When λ becomes large, their correlations become negative. The results in Figs. 3 (a) and (b) demonstrate that the Eq. (28) is sufficient to predict the numerical rank of edges, but the f b or f d is far from sufficient.  We now go further to investigate the structural properties of the optimal edge L selected by Eq. (28). The normalized structural statistics and f e L /f e max versus λ are shown in Figs. 4 (a)-(d), respectively, where f c L (f e L ) denotes the product of the closeness centrality (eigenvector centrality) of the nodes at the two ends of edge L. Note that f x max is the maximum value in {f x l }, where 1 ≤ l ≤ M and x ∈ {b, c, d, e}. As demonstrated in Fig. 4, when the value of λ is small, the optimal edge L has large f b and f e L /f e max . That is to say, when λ is slightly above the critical point λ c , the optimal edges should be those have high edge betweenness centrality and connect nodes with high closeness, degree, and eigenvector centrality. This can be explained by the fact that the outbreak size is small near the critical point, and the edge between nodes with high centrality can help to keep the cluster of nodes in I state. Thus, deactivating the edge with high centrality can well contain the spreading when λ is small. However, when the λ becomes large, the optimal This is because nodes with high centrality will have a high probability of being infected when λ is large; thus, deactivating the edge between nodes with high centrality becomes unnecessary.
Finally, we test the performance of the strategies on six real-world networks: (a) Residence hall [46], (b) Jazz musicians [47], (c) Facebook (NIPS) [48], (d) Air traffic control [49], (e) Hamsterster friendships [50], and (f) Physicians [51]. Tab. 1 provides some basic statistics of these networks. More detailed information of these networks can be found in [52], where they are downloaded from. Figs. 5 (a)-(i) show the decremental outbreak sizeρ obtained by simulations after deactivating the optimal edges L, L B or L D on the six real-world networks for different transmission probability λ. The results demonstrate that the PBS outperforms the two contrast strategies on all the six realnetworks and for all the values of λ studied.

Conclusions
Containing spreading dynamics (e.g., epidemic transmission and misinformation propagation) in the networked systems (e.g., transportation systems and communication platforms) is of both theoretical and practical importance. In this study, we developed a theoretical framework to determine the optimal edge for containing the spreading of the SIS model on complex networks.
To be specific, we performed a perturbation method to the DMC equations of the SIS model and obtained a formula that provides an approximate value of the decremental outbreak size after deactivating a certain edge in the network. Afterward, we determined the optimal edge by selecting the one with the largest decremental outbreak size. It is worth mentioning that the formula we obtained incorporates the information of both network structure and spreading dynamics. Extensive numerical simulations on both synthetic networks and real-world networks demonstrated that our strategy performs well for all the values of λ and outperforms those strategies based only on structure statistics (degree or edge betweenness centrality).
Previous strategies of containing spreading dynamics on complex networks are mostly based on node immunization, which can be socially and politically difficult in practice sometimes. The theoretical framework developed in this study offers inspirations for investigations on edge-based immunization strategies, which could be more practical for some specific real situations. Our theoretical framework could also be extended to other spreading models. which can be checked by substituting all possible combinations of A 0 ij andȦ ij . Divide by Θ i for both sides of Eq. (A.3) and substitute Θ i = N j=1 (1 − λA ij I j ) gives Note that the following relation holds since A ij ∈ {0, 1}. Similarly, when replacing A ij in Eq. (A.6) byȦ ij ∈ {0, 1}, we get Taking the logarithm on both sides of Eq. (A.5), expanding to the first orders of δp i (t), δq i (t), and applying the above relation can givė The terms in the last summation can be checked to satisfy log 1 − λȦ ij I j =Ȧ ij log 1 − λ I j .