key: cord-1022866-auy0h9wc
authors: Song, Zhichao; Ge, Yuanzheng; Luo, Lei; Duan, Hong; Qiu, Xiaogang
title: An effective immunization strategy for airborne epidemics in modular and hierarchical social contact network
date: 2015-12-01
journal: Physica A
DOI: 10.1016/j.physa.2015.07.034
sha: 547b2d49997e2fb0095b675cf6882351449dba62
doc_id: 1022866
cord_uid: auy0h9wc

Social contact between individuals is the chief factor for airborne epidemic transmission among the crowd. Social contact networks, which describe the contact relationships among individuals, always exhibit overlapping qualities of communities, hierarchical structure and spatial-correlated. We find that traditional global targeted immunization strategy would lose its superiority in controlling the epidemic propagation in the social contact networks with modular and hierarchical structure. Therefore, we propose a hierarchical targeted immunization strategy to settle this problem. In this novel strategy, importance of the hierarchical structure is considered. Transmission control experiments of influenza H1N1 are carried out based on a modular and hierarchical network model. Results obtained indicate that hierarchical structure of the network is more critical than the degrees of the immunized targets and the modular network layer is the most important for the epidemic propagation control. Finally, the efficacy and stability of this novel immunization strategy have been validated as well.

With the progressively frequent communication of population around the world, epidemics obtain more chances to lead to a global transmission. Especially for the airborne epidemics, droplets produced by an infected person during his talk, cough and sneeze can cause surrounding individuals to be infected. In recent years, these epidemics had broken out for several times and spread widely. For example, Severe Acute Respiratory Syndrome (SARS) that emerged in 2003 brought a great disaster to the economy and human lives in China. Influenza H1N1 hit many countries in 2009 and led at least 12 220 people to death until December 30th 2009. In addition, common seasonal influenza would always affect human health as well.

Development of the medicine science has accelerated the research and manufacture of vaccines. Uninfected persons can be protected by being inoculated when an epidemic breaks out. However, when a new epidemic prevails among the crowd, new vaccines invariably tend to be not enough at all and cannot satisfy the total needs. In this case, what kind of immunization strategy can furthest reduce the prevalence of an epidemic concerns many researchers and government.

Recently, researches on immunization strategy based on complex networks have been very popular [1] [2] [3] . Pastor-Satorras and Vespignani [1] studied the immunization strategy based on scale-free networks [4] , and the results indicated that protection of just a tiny fraction of the most connected individuals raises dramatically tolerance to infections of the whole population. Zanette and Kuperman [3] researched the propagation of epidemics based on the Watts-Strogatz (WS) smallworld network [5] under the action of immunization, and a similar conclusion that the most connected individuals should be protected preferentially was obtained. These two researches were both based on the unweighted networks with single hierarchical structure and the classic targeted immunization strategy was proposed in the researches. Targets in this traditional targeted immunization strategy are decided by evaluating their importance in the global network so we call it global targeted immunization strategy in this paper. However, social contact networks, on which epidemics spread among the crowd depends, always have overlapping qualities of clustering communities and hierarchical structure [6, 7] . For example, the social network in a school consists of several class social networks, and different class social networks still have many links with each other. Furthermore, we find that global targeted immunization strategy loses its superiority in controlling the epidemic propagation in the social contact networks with modular and hierarchical structure. Therefore, it is progressively necessary to study the immunization strategy based on the modular and hierarchical networks and find a more effective one.

In this paper, we propose one hierarchical targeted immunization strategy to control the epidemic spreading among the crowd with modular and hierarchical social contact network. In this strategy, importance of the hierarchical structure is considered. Experiments' results show that hierarchical structure of the network is more important than the degrees of the immunized targets in controlling the epidemic propagation. The novel immunization strategy has been proven effective and stable. The remaining part of this paper is organized as follows: In Section 2, an experiment is performed to explain our research motivation. In Section 3, the models involved in all the simulation experiments and the hierarchical targeted immunization strategy are introduced in detail. In Section 4, the experiments' results are introduced and discussed. Finally, our conclusions are given in Section 5.

In this section, we performed an experiment which proved that global targeted immunization strategy has its own disadvantages in controlling the epidemic propagation in the modular and hierarchical social contact networks. This phenomenon interested us and finally became the research motivation to do the work in this paper. The models involved in the experiment will be introduced in detail in Section 3.

Based on a modular and hierarchical network model [8] , we carried out an epidemic-transmission experiment to research the effects of the global targeted immunization strategy and the random immunization strategy. In the experiment, an individual was selected randomly to be the fixed initial infected one. Simulations at every immunized proportion were repeated for 1000 times. Same as the strategy used by Pastor-Satorras et al. [1] and Zanette et al. [3] , the global targeted immunization strategy we adopted also supposed that the best connected individuals should be vaccinated preferentially. To eliminate the randomness, the immunized targets in the random immunization would be selected again in every repeated experiment. The results are shown in Fig. 1 .

The results show that as the number of immunized individuals increases, effects of the two immunizations tend to be better. However, the targeted immunization works not much better than the random immunization. When the immunized proportion is less than 0.5, random immunization strategy always works better than targeted immunization.

It has been illuminated in the literature [8] that the modular and hierarchical network model is a ''small-world'' network. According to Zanette et al. [3] , targeted immunization has shown a substantial improvement in the disease control for the WS small-world networks. Therefore, the results shown in Fig. 1 indicate that modular and hierarchical structure of the network makes the targeted immunization lose its superiority in controlling the epidemic propagation. Furthermore, the fact that random immunization strategy works better reflects the existence of a better strategy to control the epidemic propagation in the modular and hierarchical network. In this paper, we mainly researched the impacts of the network's modular and hierarchical structure on immunization strategy to find a new strategy better to control the epidemic spreading in the modular and hierarchical networks.

To construct spatial-correlated social contact networks with both hierarchical structure and overlapping communities, we proposed a mixing pattern of modular and growing hierarchical structure in the literature [8] by using individual's geospatial distribution information. In the networks, individuals are abstracted as nodes, and contact relations are abstracted as edges.

Such as roommates in a dormitory or families in a household, local social network, which represents the most frequent contact relations, can be regarded as a module of the whole social network. Hence, the modular model is defined as a complete network with an only parameter node number n, in which individuals would own a rather high probability to contact with each other.

The hierarchical structure of the contact network, which depicts different types of relations among individuals, consists of multiple layers of networks. The layer number of a network is denoted by α. Each layer contains a number of independent networks, which represent the same type of social relation. These independent networks are all internally connected, and there is no edge between different independent networks. Individuals of an independent network in layer α come from several independent networks in layer α − 1 and connect with each other by a new-type relation.

In this paper, we reconstructed the contact network in one dormitory building of a university. According to real organization structure and dwelling spatial distribution, the dormitory building contact network was divided into 4 layers: dormitory, class, dormitory floor, and the whole building. The dormitory contact network is defined as the modular model (α = 0), which consists of 6 individuals. Each class (α = 1) has 21 dormitories. A dormitory floor (α = 2) has 2 classes and a dormitory building (α = 3) has 6 floors. The number of nodes in the whole contact network amounts to 1512.

The hierarchical network is generated based on the modular model, and it is a gradually growing process to connect nodes from modular models to a global hierarchal contact network. Each layer α of the hierarchical network is generated based on the layer α − 1, except the layer α = 0 which are composed of modular networks. The independent networks in the lower layer, which are used to construct a network in layer α, are called sub-networks of the high-layer network. Construction of a network in layer α follows two steps: First, the number of sub-networks (n s ) that compose a high-layer network is fixed. Suppose (v, e) represents a sub-network, and then all the fixed sub-networks to construct the high-layer network could be denoted by {(v i , e i )}, where v i and e i are respectively the node set and the edge set of a sub-network i.

Second, new edges are added between individuals in different sub-networks at a probability of p. Then the newly generated network G could be formalized as:

where e ′ stands for the newly added edges.

The probability p to add a new edge between a pair of individuals who are in different sub-networks is defined as:

where λ is a decline coefficient specifying the decreasing degree of p, d i represents the actual degree of an individual i, and max d i is the maximum degree of links that individual i might have in layer α − 1.

Social contact networks always belong to weighted networks [9, 10] , in which the weights are used to depict closeness of the relationships among people. We assume that relations in the modular model are the closest and are quantified by 1.

Then the decline coefficient λ actually reflects the closeness of two individuals who are in different sub-networks. As shown in Eq. (4), the weight w of an edge between two individuals is defined as the social distance, which is the inverse of λ.

Airborne epidemics transmit among the crowd by face-to-face contact and are determined by the following two elements [11] : the number of contacts N c and the actual transmission probability P for a contact between an infected individual and a susceptible one. N c and P are both designed according to the simulation step, which is defined as ''day''.

In the contact network, one individual has many links with others, but it is not reasonable to contact all of them in a day. Effective contacts for airborne epidemics in schools mainly include two patterns: conversation without physical contact and conversation with non-sexual physical contact. According to the literature [12] , the number of one individual's effective contacts N c with others on campus in a day obeys normal distribution with the mean around 26.05, and confidence interval (16.76, 35.34) under confidence degree 95%.

For the campus, contact network consists of five layers, which are namely dormitory layer, class layer, dormitory-floor layer, dormitory-building layer and campus layer. The number of one individual's effective contacts with others in each layer is in proportion to the decline coefficient λ. Moreover, the campus can also be described as layer α = 4. Thus, the number of contacts in each layer for an individual is:

The transmission probability P contains two parts. One is p i , which fluctuates in terms of different epidemics. The other one is p Γ (t), which is a coefficient to describe the transmission probability changes caused by the infectious duration t (day).

The expression is:

In this paper, we choose influenza H1N1 to research, which is a susceptible-infective-recovered (SIR) [13] style epidemic.

For this epidemic, p i = 0.042 and the infectivity coefficient p Γ (t) = exp(−t) · t 3 /6, t > 0 [8] . Since our research mainly focuses on the immunization strategy, we did not give a specific vaccine and assumed that people are immunized once they are inoculated in this paper.

In this paper, we propose that the targeted immunization should be adopted hierarchically to control the epidemic propagation in the networks with modular and hierarchical structure. We call this strategy ''hierarchical targeted immunization''. Before the hierarchical targeted immunization is introduced, we first analyze the reasons why the global targeted immunization does not bring a good performance in controlling the epidemic spreading in the modular and hierarchical network.

Though global targeted immunization has been validated in Barabási and Albert (BA) model [4] and Watts-Strogatz (WS) model [5] , epidemic propagation in these networks do not yet consider the heterogeneity of effective contacts between two individuals. In their researches, one infected individual transmits diseases to all individuals who have directly links with it at an equal probability. However, social networks only provide possible contact-objects. One individual would contact with different objects at different frequency and probability. Therefore, selection of immunized targets should consider the following two factors: One is the heterogeneity of links which can be measured by nodes' degrees. Because the more links an individual has, the more objects may be infected. The other one is the heterogeneity of effective contacts between two individuals, which is mainly caused by the modular and hierarchical structure. Because epidemic propagation totally depends on the effective contacts which happen between individuals.

According to the network model and the epidemic model, probability of effective contracts happening between one individual and others in different layers decreases as α increases. Furthermore, our research exhibits that the heterogeneity of effective contacts makes more contribution to control the epidemic propagation than the heterogeneity of links. Hence, the hierarchical targeted immunization strategy is that immunized targets should be the best connected individuals in the global network from each modular network. Specifically, following two steps can realize the strategy: First, according to the number of targets to be immunized, as many modular networks as possible need to be selected randomly. Second, the individuals who have more links in the global network in each selected modular network would be selected to be the immunized targets.

In this section, we carried out four sets of experiments based on the dormitory-building social network with 4 layers we have constructed. The first two experiments explain the contributions of the heterogeneity of links and heterogeneity of effective contacts to control the epidemic propagation. The third one gives the performance comparison between global targeted immunization and hierarchical targeted immunization. The fourth one validates the stability of the hierarchical targeted immunization.

In the simulation, one individual was selected randomly to be the fixed initial infected one. Simulations under each condition were repeated for 1000 times. Since the initial infected individual is known in the simulation, the perfect immunization strategy is to vaccinate all individuals who directly link with the initial infected one. These individuals are called ''optimal targets''. If some of the optimal targets are not vaccinated, epidemics will spread among the whole crowd. The more important an optimal target is, the more individuals will be infected if it is not vaccinated. To distinguish the impacts of every layer, in each experiment, we selected 60% of the best connected individuals in the global network from a different layer to be the non-vaccinated optimal targets. Since the network model considers the spatial-topologies, different layer of the network actually stands for different probability of effective contacts which happen between individuals in this layer and the initial infected one. The fractions of non-vaccinated individuals that have been infected under these four conditions are shown in Fig. 2 .

Results of this experiment exhibit that the modular network layer is of the most importance among the four layers and the impacts of layers are decreasing as α increases. As shown in Table 1 , the initial infected individual has the least links in layer α = 0 and layer α = 2, so the number of non-vaccinated optimal targets is also the least when the same proportion of individuals in the two layers are selected to be the non-vaccinated ones. According to literature [1, 3] , the more individuals are vaccinated, the better the control effects of epidemic transmission will be. Whereas, when the same proportion of optimal targets in layer α = 0 were not vaccinated, the most individuals were infected. Therefore, we conclude that the modular network layer is strictly much more important than the other layers and layer α = 2 is strictly much more important than layer α = 3.

To analyze the impacts of degrees of the immunized targets, we changed the non-vaccinated optimal targets selecting strategy. In each experiment, we selected 60% of the worst connected individuals in the network from a different layer to be the non-vaccinated optimal targets. The numbers of individuals that have been infected under four conditions when the two selecting strategies are used are shown in Fig. 3 . The decimals on the top of the bars are the corresponding fractions of the non-vaccinated individuals that have been infected.

From the results, two conclusions can be made: The first one is that immunized targets with more links are still more important than the ones with less links. Selecting the best connected individuals in the network from any layer to be the nonvaccinated optimal targets brings more breakages to the perfect immunization strategy than selecting the worst connected ones from the same layer. The second one is that the hierarchical structure is a more critical factor than the degrees of the immunized targets in controlling the epidemic propagation. The ''worst connection strategy'' does not change the fractions of the non-vaccinated individuals that have been infected seriously. Individuals that have less links in the modular network layer are still more essential than the individuals in the other layers. According to the two experiments above, we have validated that the modular network layer is the most important of the four layers, individuals with more links are of greater importance than the ones with less links in the same layer, and hierarchical structure is a more critical factor than the degrees of the immunized targets in controlling the epidemic propagation. In the reality, we cannot foreknow who will be the initial infected individual, so when vaccines are limited we should distribute them to more modular networks.

In this experiment, we compared global targeted immunization with hierarchical targeted immunization by controlling the epidemic transmission in a dormitory building. The reconstruction of social network has been introduced in Section 3 and there are 1512 individuals. For the global targeted immunization, we separately selected 100, 200, 300, . . . , 1400, and 1500 best connected individuals in the network to be the vaccinated targets. Since in the dormitory-building social network, networks in dormitory layer are the modular models and there are totally 252 dormitories, we separately and uniformly selected 252, 504, 756, 1008, and 1260 best connected individuals in the whole network from each dormitory. These simulations under each condition were all repeated for 1000 times. Moreover, one randomly selected individual is the fixed initial infected one in all the simulations.

In Fig. 4 , the x-axis is marked by the number of immunization individuals and y-axis is marked by the fraction of the non-vaccinated individuals that have been infected. From the results, we are clearly informed that hierarchical targeted immunization produces a further improvement than global targeted immunization in controlling the epidemic transmission. When the numbers of vaccinated individuals are the same, hierarchical targeted immunization performs better than global targeted immunization. Moreover, as the immunized individuals increase, this predominance tends to be much more obvious.

So far in this paper, all experiments were executed under an assumption that one individual was randomly selected to be the initial infected one. Whereas, the number of initial infected individuals would also affect the speed of epidemic propagation [14, 15] . Here, we assumed that there are only half of the 1512 individuals can be vaccinated. Then we randomly selected 1, 3, 5, 10, and 15 individuals to be the initial infected ones and executed the simulations respectively under global targeted immunization and hierarchical targeted immunization. All simulations were also repeated for 1000 times. The ratios of r g (fraction of the non-vaccinated individuals that have been infected when global targeted immunization is used) to r h (fraction of the non-vaccinated individuals that have been infected when hierarchical targeted immunization is used) for different numbers of initial infected individuals are shown in Fig. 5 .

It is clearly inferred that as the initial infected individuals increase, hierarchical targeted immunization and global targeted immunization are both flagging in controlling the epidemic transmission ( Table 2) . Aggravation of the epidemic transmission obviously weakened the control effects of the hierarchical targeted immunization more. However, r g /r h still stays above 1 and this trend is generally steady as the number of initial infected individuals increases (Fig. 5) . Therefore, it has been validated that hierarchical targeted immunization has better effects than global targeted immunization and this ascendency is stable.

In this paper, we presented a novel strategy named hierarchical targeted immunization to control epidemic propagation in the modular and hierarchical networks. It shows a better effect than global targeted immunization. Though the gain is modest, this strategy can provide more protection for the crowds with modular and hierarchical social contact network structures. The network model used in this paper integrates individual geospatial locations and does widely exist, so the hierarchical targeted immunization strategy, which is proposed based on it, can be adopted widely in the real cases. Considering the similarity between rumors and epidemics, this work is feasible to be used to control the face-to-face transmitted rumors diffusion in crowds as well.

Besides, the hierarchical structure of the social network was further studied. We have proved that the hierarchical structure is a more critical factor than the degrees of the immunized targets in controlling the epidemic propagation. Furthermore, according to the design and definition for the hierarchical structure, the modular network layer is always the most important, and importance of the layers is decreasing as α increases.

As for future work, first, we will adopt this strategy and analyze the effects in a larger-scale network with more complex hierarchical structure. Second, effects that the hierarchical structure brings to epidemic dynamics will be explored further, such as research on susceptible-infective-susceptible (SIS) [15] style epidemic control and relationship between the hierarchical structure and individual's degree. Third, identifying transmission paths in the network might be also a promising direction. Since vaccination belongs to a static method to control the epidemic propagation, it still cannot supply a sufficient protection when vaccines are limited. Thus, when one epidemic is spreading in crowds, other measures such as insulating the infected or potential infected individuals should be taken as well and transmission paths identification will be a key factor to them.

Immunization of complex networks

Efficient immunization strategies for computer networks and populations

Effects of immunization in small-world epidemics

Emergence of scaling in random networks

Collective dynamics of 'small-world' networks

High-resolution measurements of face-to-face contact patterns in a primary school

Social contacts and mixing patterns relevant to the spread of infectious diseases

Modular and hierarchical structure of social contact networks

Analysis of a large-scale weighted network of one-to-one human communication

World-trade web: Topological properties, dynamics, and evolution

Complex networks augmenting the framework for the study of complex systems

Mixing patterns and the spread of close-contact infectious diseases

Mathematical Epidemiology of Infectious Diseases: Model Building, Analysis and Interpretation

The research of influenza H1N1's transmission based on artificial society

Email virus propagation modeling and analysis

The authors would like to thank the National Natural Science Foundation of China under Grant Nos. 91024030 and 91224008.