Simulation on SIS model and immunization Strategy Abstract The spread of the complex network in real life are everywhere, for example, the spread of infectious diseases in social networks, the transmission of computer viruses, the information transmission in online social networks . etc. These networks and co lication behaviors are very close to our lives and are even closely related to our safety and This paper takes the disease transmission as the starting point and introduces several classical propagation models We also simulate on the er random network, ba network and real network to study the dynamics of disease transmission. Additionally,, we also give the comparisons of some immunization Keywords: SIS model, transmission dynamics, immunization strategy 1 Introduction In the past, the outbreak of disease can cause mass casualties, and it is very difficult to control. Although our medical level is increasing day by day, the epidemic of infectious diseases can cause panic easily What's more, the current flow of personnel and material is more and more frequent and convenient, which also increases the speed and extent of the spread of disease. As a result, the study of network science to control the spread of disease is necessary to our society. Network transmission dynamics can help us better understand the process of epidemic spreading, predict the trend of the spread and develop more effective interventions to avoid unnecessary panic. If applied to information dissemination the transmission dynamics can also be used to control rumors or accelerate the rapid and effective dissemination of breaking The study of epidemic spreading is based upon the notion that a disease is conveyed by contact between an infected individual and an uninfected individual who is susceptible to the disease. An endemic stage is reached if a finite fraction of the population is infected. Several models have been proposed for epidemic dynamics differing in the disease stages the dynamical parameters, and the underlying structure of contacts. The most common models for the disease dynamics are the SIR, SIS and SIRS models, which represent the development of each individuals disease in a network. In this paper we will focus on the sis model where an infected individual is infective for some period of time and then is back to susceptible stage c Another issue regarding the model used is the underlying network topology the network of contacts between individuals determines which individuals can infect each other. In general, this network may also be dynamic and change during the spread of the disease. We will assume that the network is static during the epidemic outbreak 2 SIS model 2.1 Description of SIS model The Sir model is the basic model and represents the development of a disease in a network of connected individuals. S stands for the susceptible stage, where the individual is healthy. I stands for the infected stage where the individual is infected with the disease and can infect other individuals in contact with it. R is the removed stage where the individual is either recovered and has acquired immunization to the disease or otherwise permanently removed from the system If we define the proportion of the susceptible individuals infected individuals
Simulation on SIS model and Immunization Strategy Abstract: The spread of the complex network in real life are everywhere, for example, the spread of infectious diseases in social networks, the transmission of computer viruses , the information transmission in online social networks, etc. These networks and communication behaviors are very close to our lives and are even closely related to our safety and health. This paper takes the disease transmission as the starting point and introduces several classical propagation models. We also simulate on the ER random network, BA network and real network to study the dynamics of disease transmission. Additionally,, we also give the comparisons of some immunization strategies. Keywords: SIS model, transmission dynamics, immunization strategy 1 Introduction In the past, the outbreak of disease can cause mass casualties, and it is very difficult to control. Although our medical level is increasing day by day, the epidemic of infectious diseases can cause panic easily. What’s more, the current flow of personnel and material is more and more frequent and convenient, which also increases the speed and extent of the spread of disease. As a result, the study of network science to control the spread of disease is necessary to our society. Network transmission dynamics can help us better understand the process of epidemic spreading, predict the trend of the spread and develop more effective interventions to avoid unnecessary panic. If applied to information dissemination, the transmission dynamics can also be used to control rumors or accelerate the rapid and effective dissemination of breaking news. The study of epidemic spreading is based upon the notion that a disease is conveyed by contact between an infected individual and an uninfected individual who is susceptible to the disease. An endemic stage is reached if a finite fraction of the population is infected. Several models have been proposed for epidemic dynamics, differing in the disease stages, the dynamical parameters, and the underlying structure of contacts. The most common models for the disease dynamics are the SIR, SIS and SIRS models, which represent the development of each individual’s disease in a network. In this paper we will focus on the SIS model, where an infected individual is infective for some period of time, and then is back to susceptible stage. Another issue regarding the model used is the underlying network topology. The network of contacts between individuals determines which individuals can infect each other. In general, this network may also be dynamic and change during the spread of the disease. We will assume that the network is static during the epidemic outbreak. 2 SIS model 2.1 Description of SIS model The SIR model is the basic model and represents the development of a disease in a network of connected individuals. S stands for the susceptible stage, where the individual is healthy. I stands for the infected stage, where the individual is infected with the disease and can infect other individuals in contact with it. R is the removed stage, where the individual is either recovered and has acquired immunization to the disease or otherwise permanently removed from the system. If we define the proportion of the susceptible individuals, infected individuals
and recovered individuals at moment t as s(t), i(t) and r(t), we can get that s(t)+i(t)+r(t)=1 1 As to the Sis model, similarly, s stands for the susceptible stage, where the individual is healthy. I stands for the infected stage, where the individual is infected with the disease and can infect other individuals in contact with it. In the Sis model, every infected individual recovers to a susceptible stage at a constant rate. If we define the proportion of the susceptible individuals and infected individuals at moment t as s(t) and i(t), we can get that s(t)+i(t)=1 2.2 Infective critical value We assume that an infected individual will infect BS/N susceptible individuals randomly, and every infected individual will turn to a susceptible individual again at a constant rate y. The differential equation of the sis model can be described as (2.3) Bsi-yi (24) βi(1-i) The above based on a hypothesis that the possibility for every susceptible individual to be infected is the same. However, in the real life a person can only contact with several neighbors directly, which means that an infective node can only infect part of the neighbor nodes. Next, we consider the structure of the network when study the disease spread If an susceptible node has at least one infective neighbor, the possibility for this node to be infected is assumed as a constant B, constant rate of an infected node to turn to a susceptible again is assumed as y. We can define effective spreading rate as B Without loss of generality, we can assume y =1, which just influence the time scale of th We use p(t) to represent the density of infective individual at the moment t. The stable density of infective individual denote as p when t tends to infinity. There is a peak at the average degree of the whole network (k on the degree distribution of homogeneous network such as er random networks and wS small world networks and k decreases exponentially when As a result, we assume the degree of every node in the network approximates (k). Based on the average field theory, the correlation between degrees can be ignored when the scale of the network tends to infinity So, we can get p(t)+(k)p(t[1-p(t)] The first term on the right of the equal sign means that infective individuals recover to usceptible one at an unit rate, while the second term means the average density of the new infective individuals infected by one infective individual, which is related to the effective spreading rate, the degree of nodes and the possibility to contact with the healthy susceptible nodes. If we set the right-hand side of this equation to 0, we can get the infective critical value:
and recovered individuals at moment t as s(𝑡), i(𝑡) and r(𝑡), we can get that s(𝑡)+ i(𝑡)+ r(𝑡)=1 (2.1) As to the SIS model, similarly, S stands for the susceptible stage, where the individual is healthy. I stands for the infected stage, where the individual is infected with the disease and can infect other individuals in contact with it. In the SIS model, every infected individual recovers to a susceptible stage at a constant rate. If we define the proportion of the susceptible individuals and infected individuals at moment t as s(𝑡) and i(𝑡), we can get that s(𝑡)+ i(𝑡)=1 (2.2) 2.2 Infective critical value We assume that an infected individual will infect βS/N susceptible individuals randomly, and every infected individual will turn to a susceptible individual again at a constant rate γ. The differential equation of the SIS model can be described as: 𝑑𝑠 𝑑𝑡 = 𝛾𝑖 − 𝛽𝑠𝑖 (2.3) di dt = 𝛽𝑠𝑖 − 𝛾𝑖 (2.4) Then di dt = −γi + βi(1 − i) (2.5) The above based on a hypothesis that the possibility for every susceptible individual to be infected is the same. However, in the real life, a person can only contact with several neighbors directly, which means that an infective node can only infect part of the neighbor nodes. Next, we consider the structure of the network when study the disease spread. If an susceptible node has at least one infective neighbor, the possibility for this node to be infected is assumed as a constant β, constant rate of an infected node to turn to a susceptible again is assumed as γ. We can define effective spreading rate as λ = 𝛽 𝛾 (2.6) Without loss of generality, we can assume γ =1, which just influence the time scale of the spreading. We use ρ(𝑡) to represent the density of infective individual at the moment t. The stable density of infective individual denote as ρ when t tends to infinity. There is a peak at the average degree of the whole network 〈𝑘〉 on the degree distribution of homogeneous network such as ER random networks and WS small world networks , and k decreases exponentially when 𝑘 << 〈𝑘〉 or 𝑘 >> 〈𝑘〉. As a result, we assume the degree of every node in the network approximates 〈𝑘〉. Based on the average field theory, the correlation between degrees can be ignored when the scale of the network tends to infinity. So, we can get: ∂ρ(𝑡) ∂t = −ρ(𝑡) + 𝜆〈𝑘〉ρ(𝑡)[1 − ρ(𝑡)] (2.7) The first term on the right of the equal sign means that infective individuals recover to susceptible one at an unit rate, while the second term means the average density of the new infective individuals infected by one infective individual, which is related to the effective spreading rate, the degree of nodes and the possibility to contact with the healthy susceptible nodes. If we set the right-hand side of this equation to 0, we can get the infective critical value:
(28) So, if the effective spreading rate x<nc, then number of infective nodes will decrease ponentially, and the disease can not spread On the contrary, if the effective spreading rate a>Ac, the disease can spread and the number of infective nodes in the network will tend to a constant value 3 Immunization Obviously, choosing a proper immunization strategy is very important. Next, we will introduce hree different immunization strategies: random immunization also called uniform immunization),targeted immunization (also called selected immunization),acquaintance immunization 3.1 Random immunization cial networks are known to possess a broad distribution of the number of links, k emanating from a node. Examples are the web of sexual contacts, movie-actor networks, science citations and cooperation networks etc. Computer networks, both physical and logical, e- mail and trust networks are also known to possess wide, scale-free, distributions. Studies of epidemic spreading on broad-scale networks show that a large fraction of the nodes need to be immunized before the integrity of the network is compromised. This is particularly true for scale-free networks, and the network remains connected even after removal of most of its nodes in other words, with a random immunization strategy almost all of the nodes need to be immunized before an epidemic is arrested If we define the density of odes as g, then for random immunization, it means that the transmission rates a is reduced to A(1-g e have derived the infective critical value on the homogeneous networks like ER random networks or wS small world networks (3.1) So, we get the immune critica gc As for scale-free networks, the infective criticality is λc (3.3) So, we get the immune criticality (34) We can see that if x<ac, the g<o, it means that there is no need to implement any immunization strategy. And when (k2)-00, gc -1 which means that if the network is on a large scale, almost all the nodes need immunization to control the disease spreading 3.2 Targeted immunization hen the most highly connected nodes are targeted first removal of just a small fraction of the nodes results in the networks disintegration This has led to the suggestion of targeted immunization of the hubs the most highly connected nodes in the network) The simplest targeted immunization strategy calls for the immunization of the most highly
𝜆𝑐 = 1 〈𝑘〉 (2.8) So, if the effective spreading rate 𝜆<𝜆𝑐 , then number of infective nodes will decrease exponentially, and the disease can not spread. On the contrary, if the effective spreading rate 𝜆>𝜆𝑐 , the disease can spread and the number of infective nodes in the network will tend to a constant value. 3 Immunization Obviously, choosing a proper immunization strategy is very important. Next, we will introduce three different immunization strategies: random immunization (also called uniform immunization), targeted immunization (also called selected immunization), acquaintance immunization. 3.1 Random immunization Social networks are known to possess a broad distribution of the number of links, k, emanating from a node. Examples are the web of sexual contacts, movie-actor networks, science citations and cooperation networks etc .Computer networks, both physical and logical, e-mail and trust networks are also known to possess wide, scale-free, distributions. Studies of epidemic spreading on broad-scale networks show that a large fraction of the nodes need to be immunized before the integrity of the network is compromised. This is particularly true for scale-free networks, and the network remains connected even after removal of most of its nodes. In other words, with a random immunization strategy almost all of the nodes need to be immunized before an epidemic is arrested. If we define the density of immunizing nodes as g, then for random immunization , it means that the transmission rates λis reduced to λ(1-g). We have derived the infective critical value on the homogeneous networks like ER random networks or WS small world networks: 𝜆𝑐 = 1 〈𝑘〉 (3.1) So, we get the immune criticality: 𝑔𝑐 = 1 − 1 𝜆〈𝑘〉 (3.2) As for scale-free networks, the infective criticality is: 𝜆𝑐 = 〈𝑘〉 〈𝑘2〉 (3.3) So, we get the immune criticality: gc = 1 − 〈k〉 λ〈k 2〉 (3.4) We can see that if 𝜆<𝜆𝑐 , the 𝑔𝑐<0, it means that there is no need to implement any immunization strategy. And when 〈𝑘 2 〉 → ∞, 𝑔𝑐 →1 which means that if the network is on a large scale, almost all the nodes need immunization to control the disease spreading. 3.2 Targeted immunization: When the most highly connected nodes are targeted first, removal of just a small fraction of the nodes results in the network’s disintegration. This has led to the suggestion of targeted immunization of the HUBs (the most highly connected nodes in the network). The simplest targeted immunization strategy calls for the immunization of the most highly
connected individuals, which means that if a node has a largest degree, it is the first one to immune, and then the second the third Actually the methods to choose the targeted nodes to immune such as betweeness centrality closeness centrality, which we will introduce in the following pages 3.3 Acquaintance immunization One problem with the targeted immunization approach is that it requires a complete, or at least fairly good knowledge of the degree for each node in the network Such global information often proves hard to gather, and may not even be well-defined (as in social networks, where the number of social relations depends on subjective judging). the acquaintance immunization strategy works at low immunization rates, and obviates the need for global information. In the approach, we choose a random fraction p of the n nodes and look for a random acquaintance with whom they are in contact, thus, the strategy is purely local, requiring minimal information about randomly selected nodes and their immediate environments. The acquaintances, rather than the originally chosen nodes, are the ones immunized The reason why acquaintance immunization is more effective is bewilderingly simple: " You are more likely to be friends with someone who has more friends than with someone who has fewer friends"as the psychologist Satoshi Kanazawa puts it. You're more likely to know more popular people, and less likely to know less popular ones. Some people may be completely friendless, but you' re not friends with any of them. 3.4 Important nodes As for the targeted immunization how to choose the target nodes is also a question worth explo (1)degree centrality The first method is based on degree centrality We choose the nodes with a larger degree value to immune (2)betweeness centrality The second is based on betweenness centrality Node i 's betweenness centrality is defined as his formula S≠L≠t nst (35) gst is the number of the shortest paths from node s to node t, nst is the number of the shortest paths from node s to node t which passes through the node I betweenness centrality describes the node i's ability to control the information dissemination along the shortest paths. So if we can choose the node with a larger betweeness centrality the spreading process will be easier to slow down or cut off. (3)closeness centrality The third is based on closeness centrality. Node i 's closeness centrality is defined as this formula CC=1 (36) di is the average shortest path between node i and other nodes if the closeness centrality is larger, it means the node is closer to other nodes In the same way we can use this index to choose the nodes to immune (4)k-shell decomposition method
connected individuals, which means that if a node has a largest degree, it is the first one to immune, and then the second one, the third one and so on. Actually, there are some other methods to choose the targeted nodes to immune such as betweeness centrality, closeness centrality, which we will introduce in the following pages. 3.3 Acquaintance immunization One problem with the targeted immunization approach is that it requires a complete, or at least fairly good knowledge of the degree for each node in the network. Such global information often proves hard to gather, and may not even be well-defined (as in social networks, where the number of social relations depends on subjective judging). The acquaintance immunization strategy works at low immunization rates, and obviates the need for global information. In the approach, we choose a random fraction p of the N nodes and look for a random acquaintance with whom they are in contact , thus, the strategy is purely local, requiring minimal information about randomly selected nodes and their immediate environments . The acquaintances, rather than the originally chosen nodes, are the ones immunized. The reason why acquaintance immunization is more effective is bewilderingly simple: “You are more likely to be friends with someone who has more friends than with someone who has fewer friends” as the psychologist Satoshi Kanazawa puts it. You're more likely to know more popular people, and less likely to know less popular ones. Some people may be completely friendless, but you're not friends with any of them. 3.4 Important nodes As for the targeted immunization, how to choose the target nodes is also a question worth exploring. (1)degree centrality The first method is based on degree centrality. We choose the nodes with a larger degree value to immune. (2)betweeness centrality The second is based on betweenness centrality. Node i ‘s betweenness centrality is defined as this formula: 𝐵𝐶𝑖 = ∑ 𝑛𝑠𝑡 𝑖 𝑔𝑠𝑡 𝑠≠𝑖≠𝑡 (3.5) 𝑔𝑠𝑡 is the number of the shortest paths from node s to node t, 𝑛𝑠𝑡 𝑖 is the number of the shortest paths from node s to node t which passes through the node I. betweenness centrality describes the node I ‘s ability to control the information dissemination along the shortest paths. So if we can choose the node with a larger betweeness centrality, the spreading process will be easier to slow down or cut off. (3)closeness centrality The third is based on closeness centrality. Node i ‘s closeness centrality is defined as this formula: 𝐶𝐶𝑖 = 1 𝑑𝑖 (3.6) 𝑑𝑖 is the average shortest path between node i and other nodes. If the closeness centrality is larger, it means the node is closer to other nodes. In the same way, we can use this index to choose the nodes to immune. (4)k-shell decomposition method
k-shell decomposition method is a coarse graining classification method based on the nodes importance. First we delete all the nodes which degree is equal to 1 and their links. Then, more nodes like this may appear, and we delete them again Repeat this operation until no more nodes which degree is equal to 1 appear. So we define all the nodes deleted and their links the l-shell. And in the same way we can get 2-shell, 3-shell and so on. Finally, every node in the network belong to a unique ks It' s obviously that if we want to stop the spread of the disease, we need to choose the nodes belonging to a larger k s 4 Simulation and discussion 4.1 Dataset In this paper, we use three datasets to simulate the sis model and immunization str The first one is the er random model this network has 5000 nodes, and the possibility of the connection between the nodes p=0.001, so we can get the expected number of average degree is 5. At last, we got a network with 5000 nodes and 12601 links The second one is the ba model. this network also has 5000 nodes with m=3. Finally, we got network with 5000 nodes and 14995 links The third one is a dataset downloaded from the internet these data sets correspond to the contacts and friendship relations between students in a high school in Marseilles, france, in December 2013, as measured through several techniques. Each node represents one student in the high school, and the link between two nodes means that the two students are friends. The original dataset has 1828 nodes however, most of the students reported they have no friends, which means that these nodes are isolated and having no connection with other nodes. So we delete all these isolated nodes and renumber the rest nodes in the network. Finally, we get the network of the friendship in the high school with 133 nodes and 1336 links 4.2 simulation results and discussion First, we simulate the disease spreading on the er random network (see Figure 1)
k-shell decomposition method is a coarse graining classification method based on the nodes’ importance. First we delete all the nodes which degree is equal to 1 and their links. Then, more nodes like this may appear, and we delete them again. Repeat this operation until no more nodes which degree is equal to 1 appear. So ,we define all the nodes deleted and their links the 1-shell. And in the same way, we can get 2-shell, 3-shell and so on. Finally, every node in the network belong to a unique 𝑘𝑠 It’s obviously that if we want to stop the spread of the disease, we need to choose the nodes belonging to a larger 𝑘𝑠 . 4 Simulation and discussion 4.1 Dataset In this paper, we use three datasets to simulate the SIS model and immunization strategy. The first one is the ER random model. This network has 5000 nodes, and the possibility of the connection between the nodes p=0.001, so we can get the expected number of average degree is 5. At last, we got a network with 5000 nodes and 12601 links. The second one is the BA model. This network also has 5000 nodes with m=3. Finally, we got a network with 5000 nodes and 14995 links. The third one is a dataset downloaded from the internet. These data sets correspond to the contacts and friendship relations between students in a high school in Marseilles, France, in December 2013, as measured through several techniques. Each node represents one student in the high school, and the link between two nodes means that the two students are friends. The original dataset has 1828 nodes, however, most of the students reported they have no friends, which means that these nodes are isolated and having no connection with other nodes. So we delete all these isolated nodes and renumber the rest nodes in the network. Finally, we get the network of the friendship in the high school with 133 nodes and 1336 links. 4.2 simulation results and discussion First, we simulate the disease spreading on the ER random network (see Figure 1)