key: cord-0924925-tahmgsas authors: Shams, Bita; Khansari, Mohammad title: On the impact of epidemic severity on network immunization algorithms date: 2015-10-23 journal: Theor Popul Biol DOI: 10.1016/j.tpb.2015.10.007 sha: a369cda4c477ea1d2f9ecd0965c14c5a381a08e9 doc_id: 924925 cord_uid: tahmgsas There has been much recent interest in the prevention and mitigation of epidemics spreading through contact networks of host populations. Here, we investigate how the severity of epidemics, measured by its infection rate, influences the efficiency of well-known vaccination strategies. In order to assess the impact of severity, we simulate the SIR model at different infection rates on various real and model immunized networks. An extensive analysis of our simulation results reveals that immunization algorithms, which efficiently reduce the nodes’ average degree, are more effective in the mitigation of weak and slow epidemics, whereas vaccination strategies that fragment networks to small components, are more successful in suppressing severe epidemics. A range of infectious disease outbreaks has been reported in the last decades. Influenza outbreaks have occurred in large public gatherings such as the 2002 winter Olympics in the USA, 2008 Olympics in Beijing, and the 2009 music festivals in Belgium (Chowell et al., 2012) . A large number of Toronto residents got infected during an outbreak of the severe acute respiratory syndrome (SARS) in 2003 (Svoboda et al., 2004) . In 2010, measles outbreaks of various sizes occurred in a majority of European Union countries (Steffens et al., 2010) . Severe outbreaks of infectious diseases do not only have great impacts on social life and healthcare, but they also affect the economy through productivity degradation and high cost of treatment (Hadidjojo and Cheong, 2011) . Hence, it is crucial to develop an effective strategy to prevent and control epidemic spreading through the population. Some of the traditional epidemic intervention procedures such as quarantine involve weakening or cutting the relationships (Hadidjojo and Cheong, 2011) . Vaccination is another strategy which not only protects immunized people, but also indirectly protects their friends by breaking transmission chains and reducing risk of infection (Cornforth et al., 2011) . From an economical perspective, mass vaccination (i.e. vaccinating the entire population) is not always feasible because of high cost and limitation of vaccination units (Chen et al., 2008; Restrepo et al., 2006; Schneider et al., 2011) . Therefore, an efficient immunization policy is required to minimize immunization costs as well as the number of infected individuals. The study of mathematical models for epidemic has a long history reaching back to 1920s when Kermack and Kendrick established the first birth-death model of epidemic spreading (Lewis, 2009) . By the end of the twentieth century, a variety of models had been proposed to more accurately represent epidemics dynamic. However, the majority neglect population variability in age, sex, contact rate, individual behavior, spatial patterning, etc. (Hartvigsen et al., 2007; Lewis, 2009; Miller and Hyman, 2007; Reluga, 2010; Ventresca and Aleman, 2013) . Therefore, a series http://dx.doi.org/10.1016/j.tpb.2015.10.007 0040-5809/© 2015 Elsevier Inc. All rights reserved. of deterministic and stochastic compartmental models has been proposed to capture the heterogeneity in contact patterns (Ferguson et al., 2003; Keeling et al., 1997; Lefevre and Picard, 1989; Meyers, 2006; Yorke et al., 1989) . Network epidemic is a recent advancement in epidemiology taking into account heterogeneous social structures of real population (Cai et al., 2014; Lewis, 2009; Meyers, 2006; Ventresca and Aleman, 2013) . Network epidemic studies dynamics of epidemic spreading through contact networks of host populations. A contact network is an undirected graph where nodes represent individuals and edges represent the relationship between pairs of individuals (Salathé and Jones, 2010; Youssef and Scoglio, 2011) . Due to faster dynamics of epidemics than changes in host populations, a static snapshot of contact networks is commonly considered in the literature (Christley et al., 2005; Eubank et al., 2004; Ferrari et al., 2006; Kitchovitch and Liò, 2011; Schneider et al., 2012; Youssef and Scoglio, 2011) . A great deal of research has been carried out both on network modeling of epidemic spreading (Eubank et al., 2004) and on finding the relations between network structure and epidemic parameters (Ames et al., 2011; Chakrabarti and Faloutsos, 2003; Chakrabarti et al., 2008; Youssef and Scoglio, 2011) . The results have provided major insights into the development of new immunization strategies. A large number of immunization algorithms have been proposed based on immunizing hubs (i.e. the nodes with highest degree) in networks (Cohen et al., 2003; Dezső and Barabási, 2002; Gallos et al., 2007; Gao et al., 2011; Gómez-Gardeñes et al., 2006; Hu and Tang, 2012; Pastor-Satorras and Vespignani, 2002) . The community structure of real networks has made it possible to immunize intercommunal individuals who play an important role in infectious propagation among different communities (Hébert-Dufresne et al., 2013; Masuda, 2009; Salathé and Jones, 2010; Yamada and Yoshida, 2012; Yoshida and Yamada, 2012) . There is another group of immunization schemes that attempts to raise the epidemic threshold by reduction of largest eigenvalue of network adjacency matrix (Chakrabarti and Faloutsos, 2003; Chakrabarti et al., 2008; Peng et al., 2010) . Recently, several other immunization approaches have been put forward that focus on reducing the size of the largest connected component (i.e. set of vertices that are reachable from each other) of the network of non-immunized nodes in order to reduce worst-case epidemic size (Schneider et al., 2012 (Schneider et al., , 2011 Shams and Khansari, 2013) . In spite of these efforts, a comprehensive analysis on performance of immunization algorithms has never been reported to our knowledge. Although several experiments have been conducted in order to evaluate immunization algorithms (see Table 1 ), they have significant shortcomings. Firstly, only a small number of efficient immunization algorithms are included (Schneider et al., 2012 (Schneider et al., , 2011 . Secondly, experiments are conducted based on a single network (Eames et al., 2009; Miller and Hyman, 2007; Ventresca and Aleman, 2013) or network structure (Hartvigsen et al., 2007) . Thirdly, only structural properties are considered (Masuda, 2009; Schneider et al., 2012; Shams and Khansari, 2014; Ventresca and Aleman, 2013) . And fourthly, none of these studies has considered the impact of epidemic severity on immunization algorithms (Hartvigsen et al., 2007; Ma et al., 2013; Salathé and Jones, 2010; Shams and Khansari, 2014; Ventresca and Aleman, 2013) . In this paper, we aim to address the question of how immunization algorithms reduce the number of infected individuals with regard to the severity of disease and the structure of the network. In this paper, we express the epidemic severity in terms of its infection rate. To overcome the challenge, we simulate the SIR model with different infection rates on various real and model networks which are immunized by well-known vaccination strategies. In the last decade, a number of immunization algorithms have been developed. Here, we explore six immunization strategies including degree immunization, effective degree immunization, betweenness immunization, eigenvector immunization, PageRank immunization, and stochastic hill-climbing immunization which are regarded as the most efficient strategies according to literature (Chen et al., 2008; Gallos et al., 2007; Hartvigsen et al., 2007; Hu and Tang, 2012; Masuda, 2009; Miller and Hyman, 2007; Restrepo et al., 2006; Salathé and Jones, 2010; Schneider et al., 2012 Schneider et al., , 2011 Ventresca and Aleman, 2013; Vidondo et al., 2012) . In addition to these popular approaches, we exploit random immunization as a control means of performance evaluation. Degree immunization (DI) algorithm immunizes nodes who have the highest number of interactions in the population (Dezső and Barabási, 2002; Hu and Tang, 2012; Pastor-Satorras and Vespignani, 2002) . Since the nodes with higher degree are more likely to spread disease due to their higher connections, vaccinating them reduces the contagion propagation through the population (Ventresca and Aleman, 2013) . Furthermore, immunizing hubs quickly reduces network density, which is an important factor in the growth rate of the epidemic (Hadidjojo and Cheong, 2011) . Effective degree immunization (EDI) is a modification of degree immunization which recalculates degree of vertices after immunization (i.e. removal) of highest degree node (Chen et al., 2008; Hu and Tang, 2012; Miller and Hyman, 2007; Schneider et al., 2012) . The idea behind this algorithm is that immunization of a node reduces the degree of its neighbors. So, vaccination of nodes based on their degree in initial network is not always the most efficient algorithm. Therefore, it is recommended to immunize nodes based on their effective degree which is their degree in the current network of non-immunized nodes during the immunization procedure (Hu and Tang, 2012) . This algorithm is also known as highest degree adaptive immunization in the literature (Chen et al., 2008; Schneider et al., 2012 Schneider et al., , 2011 . Betweenness immunization (BI) prioritizes nodes for vaccination regarding their betweenness centrality which is the proportion of time a node lies on the shortest path between other nodes (Freeman, 1978) . Nodes with high betweenness centrality, socalled bridge nodes, connect different communities of networks (Hébert-Dufresne et al., 2013; Salathé and Jones, 2010) . Therefore, their removal via vaccination breaks lots of transmission chains an infection that starts in a quota cannot easily propagate to other parts of the population. Eigenvector centrality of a node, the principal eigenvector of the adjacency matrix of network, provides a measure of nodal infectious risk according to the risk level of its neighbors (Bonacich, 1987; Borgatti, 2005) . Additionally, it has been proved that eigenvector centrality determines the impact of node removal on decreasing the largest eigenvalue of network adjacency matrix (Masuda, 2009; Restrepo et al., 2006) which is the inverse of epidemic threshold (Chakrabarti and Faloutsos, 2003; Chakrabarti et al., 2008; Masuda, 2009; Peng et al., 2010; Restrepo et al., 2006; Youssef and Scoglio, 2011) . Network epidemic threshold is a quantity which determines whether an infection dies out over Neighbor-degree immunization Random immunization Acquaintance immunization Hartvigsen et al. (2007) Degree immunization (DI) time or becomes an epidemic (Chakrabarti and Faloutsos, 2003; Chakrabarti et al., 2008) . Therefore, eigenvector immunizations (EI) that vaccinates nodes with high eigenvector centrality, reduces the probability of a contagious outbreak via increasing the network epidemic threshold. The PageRank immunization (PI), selects individuals based on their Google PageRank, which determines the probability of visiting a node in a random walk (Page et al., 1999; Ventresca and Aleman, 2013) . PageRank immunization is proposed based on the idea that nodes with high PageRank centrality are more likely to be infected or infect others along many paths. Additionally, since nodes with high PageRank centrality have many neighbors with low degree, PageRank immunization vaccinates influential nodes whose immunization strongly protects their neighbors (Miller and Hyman, 2007) . Recently, a group of immunization strategies has been introduced that aims to reduce worst-case expected epidemic size by fragmenting networks such that the size of largest connected component is minimized (Chen et al., 2008; Schneider et al., 2012 Schneider et al., , 2011 Shams and Khansari, 2013) . The basic assumption of these strategies is that an infected node can maximally infect nodes that are in its containing component. In other words, in the case of a single source of infection, epidemic spreading is suppressed within the connected component containing initial seeds of infection and is not transmitted to another component. Hence, the worst-case epidemic size is equal to the size of the largest connected component of the network. Stochastic hill-climbing immunization (SHCI) is the newest immunization strategy in this category which is designed to immunize networks with a certain amount of vaccination units (Shams and Khansari, 2013) . This algorithm employs the Stochastic hill-climbing method to find the specified size subset of nodes whose removal minimizes largest connected component (LCC) of the network. Random immunization (RI) is a simple vaccination strategy selecting a random subset of nodes for removal (Ferrari et al., 2006) . Random immunization does not require any information about the structure of the population. Additionally, it shows the advantage of minimum time complexity among all immunization algorithms. Therefore, it is important to study random immunization as a means of control to assess the relative performance of different immunization algorithms (Eames et al., 2009; Ferrari et al., 2006; Hartvigsen et al., 2007; House and Keeling, 2011) . The paper aims to investigate the impact of severity of epidemic diseases on the performance of immunization algorithms in networks with different structures. To achieve this goal, we simulate the SIR model with different transmission rates in various real and model immunized networks (see Table 2 ) and measure the number of infected individuals. The settings of SIR model and datasets are elaborated in the following subsections. To investigate the impact of immunization algorithms on epidemic dynamic, we first need to implement immunization strategies to select our target nodes for immunization. In case of equal priority for immunization, the next node is selected at random. Then, selected nodes are removed from the network since immunized nodes do not play any role in infection propagation. Now, epidemic simulation can start. Here, we consider the SIR epidemic model which is commonly used to model the infectious propagation (Chen et al., 2008; Christley et al., 2005; House and Keeling, 2011; Ma et al., 2013; Schneider et al., 2011; Youssef and Scoglio, 2011) . In this model, each node is in one of three states: Susceptible, Infected, or Recovered. Initially all nodes are susceptible. Then, a random node is infected to initiate epidemic. At each time step, each infected node might infect their susceptible neighbors with probability α. It has been shown that a susceptible node can be infected with probability of 1 − (1 − α) N i where N i is the number of infected neighbor nodes. Incidentally, an infected node recovers after T time steps where T is the infectivity time of the disease in which an infected individual can infect others. It should be noted that recovered nodes are immune to subsequent infection. The epidemic ends when there are no more infected nodes in the network (Christley et al., 2005) . To test the efficiency of immunization algorithm based on severity of disease, we simulate our SIR model at various infection rates (α = {0.2, 0.5, 0.8}) indicating different severity levels. The infection time (T ) is set to 3 which is suggested in Badham and Stocker (2010) . The parameter settings of SIR simulation are shown in Table 3 . We calculate the epidemic reproductive number, R 0 , indicating the average number of secondary cases generated by a primary infectious individual in a wholly susceptible population (Ames et al., 2011; Chowell et al., 2012; House and Keeling, 2011; Saramäki and Kaski, 2005) . To estimate R 0 , we run a series of 300 SIR simulation and average the number of individuals infected by the single primary infection seed. Note that the initial seed of infection is chosen randomly in each run. Various real and model networks are included in the experiments to evaluate the efficiency of immunization algorithms with regards to network structure and infection rate. HEP, AS, and Facebook-like (FBL) networks are used as real networks, whereas scale-free (SF), Erdös-Renyi (ER) and small-world (SW) networks are the model networks. The structural properties of networks are shown in Table 4 . It is worth mentioning that HEP ( (Shavitt and Shir, 2005) networks are popular in immunization literature (Chen et al., 2008; Gao et al., 2011; Hu and Tang, 2012; Masuda, 2009; Mirzasoleiman et al., 2012; Niu et al., 2009; Schneider et al., 2012) . HEP network represents citations among 27,770 papers on high energy physics theory derived from eprint Arxiv. Regardless of direction, HEP network contains 352,285 links. This network has been used in immunization literature as a relatively dense network (Chen et al., 2008; Masuda, 2009; Mirzasoleiman et al., 2012; Schneider et al., 2012) . Facebook-like network represents an online student community at the University of California, Irvine. It includes information of 13,838 messages on an online community of 1899 students at the University of California, Irvine (Opsahl and Panzarasa, 2009 ). AS network contains 25,367 nodes and 75,004 edges captures information of internet network at autonomous systems level on June 2012. The network is an important dataset to study virus spreading models through computer networks (Chen et al., 2008; Schneider et al., 2012) . Most of real networks involving social, biological, and technological networks can be represented as scale-free, Erdös-Renyi and small-world networks (Hu and Tang, 2012) . Erdös-Renyi is the first model network with the properties of emergence of a giant component and low clustering coefficient (Erdös and Renyi, 1959) . We use the Erdös-Renyi algorithm to generate Erdös-Renyi network containing 10,000 nodes and 20,000 edges. Scale-free networks are the symbols of real networks following a power-law degree distribution p(k) = k −γ (Barabási, 1999) . The scale-free network (SF) is generated by the algorithm disclosed in Cho et al. (2009), Chung and Lu (2002) and Goh et al. (2001) with the setting of 10,000 nodes, 20,000 edges and γ = 2.5. Small-World networks (SW) reflect high clustering coefficient and short average path length of real networks (Watts and Strogatz, 1998) . In this paper, we construct a Small-World network by exploiting the Watts-Strogatz algorithm (Watts and Strogatz, 1998) such that network size is 10,000, mean degree is 4 and switching probability is 0.01. The model networks are generated using the parameters of Ref. Chen et al. (2008) . To investigate the impact of epidemic severity on network immunization algorithms, we simulate the SIR model at various infection rates. Then, we measure the average number of infected individuals over 50 SIR trials on networks for deterministic immunization algorithms. For stochastic algorithms (SHCI and RI), we consider 50 SIR trials on five different immunized networks. Note that only simulations with a significant final epidemic size (i.e. least 2% of the population) are included in the calculation of the average (Salathé and Jones, 2010) . As shown in Figs. 1-3 , the variance of epidemic size is mostly less than 1% in each networkimmunization-disease interaction. The maximum variance is 6%, which occurs in the case of high infection rate in small-world network (see Fig. 3(f) ). We plot the average fraction of infected individuals with α = 0.2, S, versus vaccination coverage, q, in Fig. 1 . The performance results vary according to the network topology. Betweenness immunization exhibits the best performance in the Erdös-Renyi network, while, Effective degree immunization (EDI) and degree immunization (DI) are the most effective ones in scale-free networks. However, degree-based immunization algorithms are generally more effective than other algorithms, and are therefore among top-3 algorithms in all networks. On the other hand, other algorithms such as SHCI, which ignore network degree, fail to stop spreading of this type of epidemic. The result highlights the importance of network average degree in the suppression of low infection rate epidemics. The above conclusion is also confirmed by similar trends of algorithms in controlling weak epidemics and lowering the average degree (see Figs. 1 and A.1) . Another surprising result of a weak epidemic simulation (i.e. α = 0.2) is that it dies out in small-world networks (see Fig. 1 (f)) although its basic reproduction number is greater than one (i.e. R 0 > 1). The result can be explained through special characteristic of small-world networks (i.e. high modularity and clustering coefficient) where R 0 cannot solely determine epidemic dynamics (Saramäki and Kaski, 2005) . In other words, an epidemic with a low infection rate is commonly confined in the local community of the primary infectious individual (Badham and Stocker, 2010; Saramäki and Kaski, 2005) . Finally, it should be noted that all immunization algorithms obviously outperform random immunization in AS and scale-free networks with a low-power degree distribution. For instance, Effective-Degree immunization is up to 68% more effective than random immunization in AS network. We run SIR simulation at infection rate α = 0.5 as a representative of moderate epidemics. As depicted in Fig. 2 , Eigenvector immunization (EI) offers the worst immunization algorithm in all networks with a performance 60% worse than that of random immunization in Small-World network when immunization coverage is equal to 20%. Unlike the low-infection rate epidemics, their moderate counterparts are widely propagated through non-immunized small-world network (see Fig. 2 (f)) such that the whole population becomes infected. However, the majority of immunization algorithms can suppress epidemics by immunizing only 5% of the population. Betweenness immunization is still the most effective approach in the Erdös-Renyi network outperforming the next best algorithm (i.e. SHCI) by up to 11%. Comparing the performance of SHCI in the cases of low and medium infection rates indicates that it is more effective in suppressing the moderate one. For instance, Effective degree immunization (EDI) is highly superior to this scheme in the control of weak epidemics in scale-free network (Fig. 1(e) ), while, SHCI exhibits a similar performance concerning medium infection rate (Fig. 2(e) ). This increasing in relative performance of (a) HEP network. represents the average of maximally 50 simulation runs for targeted immunization algorithms and 50 runs on 5 different immunized networks for SHCI and random immunizations, (note that only simulations with a final size of at least 2% of the population were included in the calculation of averages). Fraction of infected individuals is measured considering the whole population (i.e. including immunized and non-immunized nodes). SHCI must rely on the fact that as infection rate increases, the contagion is more likely to infect all reachable nodes in the component of initial seed. Therefore, the number of infected individuals becomes equal to the size of the largest connected component of the network when the most severe epidemic occurs. Fig. 3 depicts the results of SIR simulations of high infection rate epidemics (α = 0.8). Our experimental results confirm the hypothesis of superiority of SHCI in the prevention and mitigation of severe epidemics in comparison to other algorithms. SHCI outperforms all strategies over all networks except Erdös-Renyi network where it is up to 14% less effective than betweenness immunization ( Fig. 3(d) ). SHCI algorithm displays a maximal improvement of 8% in Facebook-like and AS network, 4% in Small-world network, 40% in HEP, and 22% in Scale-Free, compared to the next best algorithm. The desired performance of SHCI justifies the claim that the size of the largest connected component of network is the most important factor in spreading of severe epidemics. This assumption is confirmed by trends of other algorithms. For instance, PageRank immunization offers the second best performance in modular and homogeneous networks such as Small-World since it is highly efficient in fragmenting small-world networks into small components by immunization of nodes connecting different clusters (Fig. A.2) . Moreover, Degree-based immunization algorithms are quite optimum over heterogeneous networks such as Scale-Free and AS networks, as it easily breaks them down via hub immunization. This paper investigates the interactive effects of network structure, epidemiological traits, and vaccination strategies. The investigation must deal with the following three aspects: Impact of epidemic severity on immunization algorithms, Impact of network structure on epidemic spreading, and, Impact of network structure on immunization algorithms, respectively. Our investigation on the epidemic severity signified the effectiveness of degree-based immunization algorithm for weak epidemics against high performance of stochastic hill-climbing under severe epidemic condition. Despite the superiority of degree-based immunization algorithms over most centralitybased schemes has been previously investigated (Hartvigsen et al., 2007) , the impact of epidemic severity was not pondered in previous literature. The experimental results indicated that the hypothesis (i.e. The superiority of degree-based immunization algorithms over most centrality-based schemes) is plausible only in the case of weak epidemics. From theoretical points, an epidemic with a low infection rate is not propagated to those nodes far from initial seed since the infection probability at far nodes converges to zero. Therefore, degree-based strategies, reducing local connectivity, are more efficient in cases of low infection rate epidemics. On the opposite side, when infection rate increases, the infection probability will converge to one for all nodes except immunized ones. Consequently, the contagion is propagated through the components unless it meets immunized nodes that isolate the infected component. The result is somewhat consistent with the previous finding in Chen et al. (2008 ), Schneider et al. (2012 and Shams and Khansari (2013) where network fragmentation was considered to be the answer to inoculation challenge. But, the point is that they had evaluated immunization algorithms based on severe epidemics and extended their result to all types of epidemics, whereas, it could not be an accurate assumption in the case of low-infection rate epidemic which are not widespread in the whole component. The investigation into the interaction of network structure and epidemic spreading reveals that the former has a great impact on the latter. For instance, a low infection rate epidemic dies out in small-world networks, while, it readily disseminates through the whole population in AS and HEP networks. This can be explained by the term of epidemic threshold defined by Chakrabarti and Faloutsos (2003) and Chakrabarti et al. (2008) . The epidemic threshold or the inverse of largest eigenvalue of the adjacency matrix, indicates whether an infection dies out over time or becomes an epidemic. Comparison of epidemic threshold of small-world network with AS and HEP network clearly indicates why weak epidemics die out in small-world network. Additionally, the higher number of infected individuals in a scale-free network is also justified by its power-law distribution which leads to fast propagation of a contagion through the whole network (Chakrabarti et al., 2008; Dezső and Barabási, 2002; Pastor-Satorras and Vespignani, 2002) . Finally, evaluation of immunization algorithms over various networks has found that degree-based immunization algorithms are more effective in power-law degree distribution networks. The effectiveness of degree-based immunization algorithms over heterogeneous networks relies on the fact that hub immunization easily fragments heterogeneous networks (Dezső and Barabási, 2002) . On the other hand, stochastic hill-climbing algorithm can be efficiently exploited to stop an epidemic in modular networks. Modular networks are networks that contain a number of communities with a high connectivity among the nodes within the same community, but low connectivity between nodes in different modules (Clauset et al., 2004) . In these networks, an infection is quickly propagated through the community of initial infection seeds. Then, the border nodes of the community transmit epidemic through the whole networks . Hence, immunization algorithms are required to isolate different communities such that an infection that starts in one community is not permitted to propagate through another one. That is the reason why immunization algorithms, immunizing intercommunal (i.e. border) nodes, are more desirable (e) Scale-free network. (f) Small-world network. Fig. 3 . Fraction of infected individuals under high infection rate (α = 0.8) , S, versus q, fraction of immunized nodes q for various vaccination strategies. Each of the points represents the average of maximally 50 simulation runs for targeted immunization algorithms and 50 runs on 5 different immunized networks for SHCI and random immunizations, (note that only simulations with a final size of at least 2% of the population were included in the calculation of averages). The fraction of infected individuals is measured considering the whole population (i.e. including immunized and non-immunized nodes). (c) Facebook-like network. (d) Erdös-Renyi network. (e) Scale-free network. (f) Small-world network. in modular networks (Hébert-Dufresne et al., 2013; Masuda, 2009; Salathé and Jones, 2010; Yoshida and Yamada, 2012) . As a final point, it should be noted that degree-based immunization algorithms are not able to effectively diminish epidemics in homogeneous networks. The reason is that degree-based immunization algorithms cannot differentiate the nodes' importance in these networks, and therefore, they behave similar to a random strategy. In homogeneous networks, the most effective strategy varies depending on the structural properties of network and epidemic severity. For instance, betweenness immunization is the favorite over the Erdös-Renyi network due to the importance of distance reduction. On the other hand, SHCI outperforms all other algorithms in small-world network because of its high modularity. Table 5 tabulates the ranking of immunization algorithms based on the network structure and epidemic severity. In this paper, we explored how the severity of diseases influences performance of several immunization algorithms over networks with dissimilar structures. The evaluation focused on seven popular vaccination strategies, including degree immunization, betweenness immunization, eigenvector immunization, PageRank immunization, effective degree immunization, stochastic hillclimbing immunization (SHCI) and random immunization (RI), which were applied to mitigate the number of infected individuals in low, medium, and high infection rate epidemics. Our experiment verified that epidemic severity affects performance of the algorithms and that, in general, depends on the ability of algorithms to fragment networks or reduce their density. In other words, any increase in infection rate fades the worth of lowering density, while, it weighs the importance of network fragmentation. Conversely, lowering density is much more essential than network fragmentation in preventing weak epidemics. To put it briefly, degree-based immunization algorithms are the favorite in the case of weak epidemics, whereas, SHCI is more superior in the case of high infection rate epidemics. The experimental results encourage the hypothesis that the scope of the epidemic spreading is a function of network properties such as density and largest connected component size as well as epidemic parameters (e.g. infection rate). Thus, this calls for new research whereby a combination of the above parameters can be exploited as a new metric to mathematically estimate the efficiency of vaccination strategies. Accordingly, new vaccination strategies can be developed to optimize the new metric. It should also be noted that we conducted our analysis based on the SIR model which is not extended to all epidemics. Hence, it is beneficial to examine the impact of severity of epidemics on immunization algorithms in controlling other epidemic model such as SIS in which infected nodes become susceptible again (i.e. are not immune to subsequent infection) and SEIR where there is a new state called exposed (E) to show infected individuals cannot infect others. Finally, it is worth investigating the performance of immunization algorithms regarding other epidemic parameters such as epidemic duration, extinction probability, timing and number of infected individuals at the peak of the epidemic. Using network properties to predict disease dynamics on human contact networks The impact of network clustering and assortativity on epidemic behaviour Emergence of scaling in random networks The architecture of complex weighted networks Power and centrality: A family of measures Centrality and network flow Effect of vaccination strategies on the dynamic behavior of epidemic spreading and vaccine coverage Epidemic spreading in real networks: an eigenvalue viewpoint Epidemic thresholds in real networks Finding a better immunization strategy Percolation transitions in scalefree networks under the achlioptas process Modeling rapidly disseminating infectious disease during mass gatherings Infection in social networks: using network analysis to identify high-risk individuals Connected components in random graphs with given expected degree sequences Finding community structure in very large networks Efficient immunization strategies for computer networks and populations Erratic flu vaccination emerges from short-sighted behavior in contact networks Halting viruses in scale-free networks Epidemic prediction and control in weighted networks On random graphs Modelling disease outbreaks in realistic urban social networks Planning for smallpox outbreaks Network frailty and the geometry of herd immunity Centrality in social networks conceptual clarification Improving immunization strategies Network immunization with distributed autonomy-oriented entities Overview of the 2003 KDD cup Universal behavior of load distribution in scalefree networks Immunization of real complex communication networks Equal graph partitioning on estimated infection network as an effective epidemic mitigation measure Network structure, and vaccination strategy and effort interact to affect the dynamics of influenza epidemics Global efficiency of local immunization on complex networks Epidemic prediction and control in clustered populations Immunization for complex network based on the effective degree of vertex Correlation models for childhood epidemics Community structure in social networks: applications for epidemiological modelling On the formulation of discrete-time epidemic models Graphs over time Epidemic network The importance of contact network topology for the success of vaccination strategies Immunization of networks with community structure Contact network epidemiology: Bond percolation applied to infectious disease prediction and control Effective vaccination strategies for realistic social networks Immunizing complex networks with limited budget Comparing two newly proposed immunization strategies in networks Clustering in weighted networks The PageRank citation ranking: bringing order to the web Immunization of complex networks Epidemic threshold and immunization on generalized networks Game theory of social distancing in response to an epidemic Characterizing the dynamical importance of network nodes and links Dynamics and control of diseases in networks with community structure Modelling development of epidemics with dynamic small-world networks Suppressing epidemics with a limited amount of immunization units Inverse targeting-an effective immunization strategy Immunization of complex networks using stochastic hill-climbing algorithm Using network properties to evaluate targeted immunization algorithms DIMES: Let the Internet measure itself Spotlight on measles 2010: measles elimination in Europe-a new commitment to meet the goal by 2015 Public health measures to control the spread of the severe acute respiratory syndrome during the outbreak in Toronto Evaluation of strategies to mitigate contagion spread using social network characteristics Finding and removing highly connected individuals using suboptimal vaccines Collective dynamics of ''small-world'' networks A comparative study of community structure based node scores for network immunization Dynamics and control of the transmission of gonorrhea Community structure based node scores for network immunization An individual-based approach to SIR epidemics in contact networks It has been proved that network structural properties are effective tools for assessing mitigation strategies. The most important among them are network density, path length, and connected component (Ames et al., 2011; Chen et al., 2008; Gallos et al., 2007; Hadidjojo and Cheong, 2011; Schneider et al., 2012 Schneider et al., , 2011 Ventresca and Aleman, 2013) . We investigate the importance of reducing network degree and largest connected component in order to gauge the response of algorithms with respect to severity of diseases. Path length is not considered here because of its high time complexity (Ventresca and Aleman, 2013) . In this section, we present experimental results for network average degree after applying immunization algorithms. (Fig. A.1) . As described in Section 4, network density and subsequently average degree play important roles in controlling epidemics (Ames et al., 2011; Hadidjojo and Cheong, 2011; Ventresca and Aleman, 2013 ) especially weak and slow diseases such as influenza. Here the results for the fraction of the largest connected component size are plotted for vaccination strategies (Fig. A.2) . The largest connected component is an influential deciding factor in the estimation worst-case epidemic size (Chen et al., 2008; Gallos et al., 2007; Schneider et al., 2012 Schneider et al., , 2011 Ventresca and Aleman, 2013) .