key: cord-0958389-tw5armh8
authors: Ma, Junling; van den Driessche, P.; Willeboordse, Frederick H.
title: The importance of contact network topology for the success of vaccination strategies
date: 2013-05-21
journal: J Theor Biol
DOI: 10.1016/j.jtbi.2013.01.006
sha: cfe4a7ac44f9c7fce218b3b428a4ecc40ebc0f8e
doc_id: 958389
cord_uid: tw5armh8

The effects of a number of vaccination strategies on the spread of an SIR type disease are numerically investigated for several common network topologies including random, scale-free, small world, and meta-random networks. These strategies, namely, prioritized, random, follow links and contact tracing, are compared across networks using extensive simulations with disease parameters relevant for viruses such as pandemic influenza H1N1/09. Two scenarios for a network SIR model are considered. First, a model with a given transmission rate is studied. Second, a model with a given initial growth rate is considered, because the initial growth rate is commonly used to impute the transmission rate from incidence curves and to predict the course of an epidemic. Since a vaccine may not be readily available for a new virus, the case of a delay in the start of vaccination is also considered in addition to the case of no delay. It is found that network topology can have a larger impact on the spread of the disease than the choice of vaccination strategy. Simulations also show that the network structure has a large effect on both the course of an epidemic and the determination of the transmission rate from the initial growth rate. The effect of delay in the vaccination start time varies tremendously with network topology. Results show that, without the knowledge of network topology, predictions on the peak and the final size of an epidemic cannot be made solely based on the initial exponential growth rate or transmission rate. This demonstrates the importance of understanding the topology of realistic contact networks when evaluating vaccination strategies.

The importance of contact network topology for the success of vaccination strategies

For many viral diseases, vaccination forms the cornerstone in managing their spread and the question naturally arises as to which vaccination strategy is, given practical constraints, the most effective in stopping the disease spread. For evaluating the effectiveness of a vaccination strategy, it is necessary to have as precise a model as possible for the disease dynamics.

The widely studied key reference models for infectious disease epidemics are the homogeneous mixing models where any member of the population can infect or be infected by any other member of the population; see, for example, Anderson and May (1991) and Brauer (2008) . The advantage of a homogeneous mixing model is that it lends itself relatively well to analysis and therefore is a good starting point. Due to the homogeneity assumption, these models predict that the fraction of the population that needs to be vaccinated to curtail an epidemic is equal to 1À1=R 0 , where R 0 is the basic reproduction number (the average number of secondary infections caused by a typical infectious individual in a fully susceptible population). However, the homogeneous mixing assumption poorly reflects the actual interactions within a population, since, for example, school children and office co-workers spend significant amounts of time in close proximity and therefore are much more likely to infect each other than an elderly person who mostly stays at home. Consequently, efforts have been made to incorporate the network structure into models, where individuals are represented by nodes and contacts are presented by edges. In the context of the severe acute respiratory syndrome (SARS), it was shown by Meyers et al. (2005) that the incorporation of contact networks may yield different epidemic outcomes even for the same basic reproduction number R 0 . For pandemic influenza H1N1/09, Pourbohloul et al. (2009) and Davoudi et al. (2012) used network theory to obtain a real time estimate for R 0 . Numerical simulations have shown that different networks can yield distinct disease spread patterns; see, for example, Bansal et al. (2007) , Miller et al. (2012) , and Section 7.6 in Keeling and Rohani (2008) . To illustrate this difference for the networks and parameters we use, the effect of different networks on disease dynamics is shown in Fig. 1 . Descriptions of these networks are given in Section 2 and Appendix B.

At the current stage, most theoretical network infectious disease models incorporate, from a real world perspective, idealized random network structures such as regular (all nodes have the same degree), Erd + os-Ré nyi or scale-free random networks where clustering and spatial structures are absent. For example, Volz (2008) used a generating function formalism (an alternate derivation with a simpler system of equations was recently found by Miller, 2011) , while we used the degree distribution in the effective degree model presented in Lindquist et al. (2011) . In these models, the degree distribution is the key network characteristic for disease dynamics. From recent efforts (Ma et al., 2013; Volz et al., 2011; Moreno et al., 2003; on incorporating degree correlation and clustering (such as households and offices) into epidemic models, it has been found that these may significantly affect the disease dynamics for networks with identical degree distributions. Fig. 2 shows disease dynamics on networks with identical degree distribution and disease parameters, but with different network topologies. Clearly, reliable predictions of the epidemic process that only use the degree distribution are not possible without knowledge of the network topology. Such predictions need to be checked by considering other topological properties of the network.

Network models allow more precise modeling of control measures that depend on the contact structure of the population, such as priority based vaccination and contact tracing. For example, Shaban et al. (2008) consider a random graph with a pre-specified degree distribution to investigate vaccination models using contact tracing. Kiss et al. (2006) compared the efficacy of contact tracing on random and scale-free networks and found that for transmission rates greater than a certain threshold, the final epidemic size is smaller on a scale-free network than on a corresponding random network, while they considered the effects of degree correlations in Kiss et al. (2008) . Cohen et al. (2003) (see also Madar et al., 2004) considered different vaccination strategies on scale-free networks and found that acquaintance immunization is remarkably effective. Miller and Hyman (2007) considered several vaccination strategies on a simulation of the population of Portland Oregon, USA, and found it to be most effective to vaccinate nodes with the most unvaccinated susceptible contacts, although they found that this strategy may not be practical because it requires considerable computational resources and information about the network. Bansal et al. (2006) took a contact network using data from Vancouver, BC, Canada, considered two vaccination strategies, namely mortality-and morbidity-based, and investigated the detrimental effect of vaccination delays. and found that, on realistic contact networks, vaccination strategies based on detailed network topology information generally outperform random vaccination.

However, in most cases, contact network topologies are not readily available. Thus, how different network topologies affect various vaccination strategies remains of considerable interest. To address this question, we explore two scenarios to compare percentage reduction by vaccination on the final size of epidemics across various network topologies. First, various network topologies are considered with the disease parameters constant, assuming that these have been independently estimated. Second, different network topologies are used to fit to the observed incidence curve (number of new infections in each day), so that their disease parameters are different yet they all line up to the same initial exponential growth phase of the epidemic.

Vaccines are likely lacking at the outbreak of an emerging infectious disease (as seen in the 2009 H1N1 pandemic, Conway et al., 2011) , and thus can only be given after the disease is already widespread. We investigate numerically whether network topologies affect the effectiveness of vaccination strategies started with a delay after the disease is widespread; for example, a 40 day delay as in the second wave of the 2009 influenza pandemic in British Columbia, Canada (Office of the Provincial Health Officer, 2010). Details of our numerical simulations are given in Appendix A.

This paper is structured as follows. In Section 2, a brief overview of the networks and vaccination strategies (more details are provided in Appendices B and C) is given. In Section 3, we investigate the scenario where the transmission rate is fixed, while in Section 4 we investigate the scenario where the growth rate of the incidence curve is fixed. To this end, we compute the incidence curves and reductions in final sizes (total number of infections during the course of the epidemic) due to vaccination. For the homogeneous mixing model, these scenarios are identical (Ma and Earn, 2006) , but as will be shown, when taking topology into account, they are completely different. We end with conclusions in Section 5. . On all networks, the average degree is 5, the population size is 200,000, the transmission rate is 0.06, the recovery rate is 0.2, and the initial number of infectious individuals is set to 100. Both graphs represent the same data but the left graph has a semi-log scale (highlighting the growth phase) while the right graph has a linear scale (highlighting the peak). (b)) on networks with identical disease parameters and degree distribution (as shown in (a)). The network topologies are the random, meta-random, and near neighbor networks. See Appendix B for details of the constructions of these networks.

Detailed network topologies for human populations are far from known. However, this detailed knowledge may not be required when the main objective is to assert the impact that topology has on the spread of a disease and on the effects of vaccination. It may be sufficient to consider a number of representative network topologies that, at least to some extent, can be found in the actual population. Here, we consider the four topologies listed in Table 1 , which we now briefly describe.

In the random network, nodes are connected with equal probability yielding a Poisson degree distribution. In a scale-free network, small number of nodes have a very large number of links and large number of nodes have a small number of links such that the degree distribution follows a power law. Small world (SW) networks are constructed by adding links between randomly chosen nodes on networks in which nodes are connected to the nearest neighbors. The last network considered is what we term a meta-random network where random networks of various sizes are connected with a small number of interlinks. All networks are undirected with no self loops or multiple links. The histograms of the networks are shown in Table 2 , and the details of their construction are given in Appendix B.

The vaccination strategies considered are summarized in Table 3 . In the random strategy, an eligible node is randomly chosen and vaccinated. In the prioritized strategy, nodes with the highest degrees are vaccinated first, while in the follow links strategy, inspired by notions from social networks, a randomly chosen susceptible node is vaccinated and then all its neighbors and then its neighbor's neighbors and so on. Finally, in contact tracing, the neighbors of infectious nodes are vaccinated.

For all the strategies, vaccination is voluntary and quantity limited. That is, only susceptibles who do not refuse vaccination are vaccinated and each day only a certain number of doses is available. In the case of (relatively) new viral diseases, the supply of vaccines will almost certainly be constrained, as was the case for the pandemic influenza H1N1/09 virus. Also in the case of mass vaccinations, there will be resource limitations with regard to how many doses can be administered per day.

The report (Office of the Provincial Health Officer, 2010) states that the vaccination program was prioritized and it took 3 weeks before the general population had access to vaccination. Thus we assume that a vaccination program can be completed in 4-6 weeks or about 40 days, this means that for a population of 200,000, a maximum of 5000 doses a day can be used. For each strategy for each time unit, first a group of eligible nodes is identified and then up to the maximum number of doses is dispensed among the eligible nodes according to the strategy chosen. More details of the vaccination strategies and their motivations are given in Appendix C.

To study the effect of delayed availability of vaccines during an emerging infectious disease, we compare the effect of vaccination programs starting on the first day of the epidemic with those vaccination programs starting on different days. These range from 5 to 150 days after the start of the epidemic, with an emphasis on a 40 day delay that occurred in British Columbia, Canada, during the influenza H1N1/2009 pandemic.

When a node is vaccinated, the vaccination is considered to be ineffective in 30% of the cases (Bansal et al., 2006) . In such cases, the vaccine provides no immunity at all. For the 70% of the nodes for which the vaccine will be effective, a two week span to reach full immunity is assumed (Clark et al., 2009) . During the two weeks, we assume that the immunity increases linearly starting with 0 at the time of vaccination reaching 100% after 14 days.

The effect of vaccination strategies has been studied (see, for example, Conway et al., 2011) using disease parameter values estimated in the literature. However, network topologies were not the focus of these studies. In Section 3, the effect of vaccination strategies on various network topologies is compared with a fixed per link transmission rate. The per link transmission rate b is difficult to obtain directly and is usually derived as a secondary quantity. To determine b, we pick the basic reproduction number R 0 ¼ 1:5 and the recovery rate g ¼ 0:2, which are close to that of the influenza A H1N1/09 virus; see, for example, Pourbohloul et al. (2009 ), Tuite et al. (2010 . In the case of the homogeneous mixing SIR model, the basic reproduction number is given by R 0 ¼ t=g, where t is the per-node transmission rate. Our Table 1 Illustration of the different types of networks used in this paper.

Scale-free Small world Meta-random Table 2 Degree histograms of the networks in Table 1 with 200,000 nodes.

Scale-free Small world Meta-random parameter values yield t ¼ 0:3. For networks, t ¼ b/kS. With the assumption that the average degree /kS ¼ 5, the above gives the per-link transmission rate b ¼ 0:06. The key parameters are summarized in Table 4 . In Section 3, we use this transmission rate to compare the incidence curves for the networks in Table 1 with the vaccination strategies in Table 3 . Some of the most readily available data in an epidemic are the number of reported new cases per day. These cases generally display exponential growth in the initial phase of an epidemic and a suitable model therefore needs to match this initial growth pattern. The exponential growth rates are commonly used to estimate disease parameters (Chowell et al., 2007; Lipsitch et al., 2003) . In Section 4, we consider the effects of various network topologies on the effectiveness of vaccination strategies for epidemics with a fixed exponential growth rate. The basic reproduction number R 0 ¼ 1:5 and the recovery rate g ¼ 0:2 yield an exponential growth rate l ¼ tÀg ¼ 0:1 for the homogeneous mixing SIR model. We tune the transmission rate for each network topology to give this initial growth rate.

In this section, the effectiveness of vaccination strategies on various network topologies is investigated for a given set of parameters, which are identical for all the simulations. The values of the disease parameters are chosen based on what is known from influenza H1N1/09. Qualitatively, these chosen parameters should provide substantial insight into the effects topology has on the spread of a disease. Unless indicated otherwise the parameter values listed in Table 4 are used.

The effects of the vaccination strategies summarized in Table 3 when applied without delay are shown in Fig. 3 . For reference, Fig. 1 shows the incidence curves with no vaccination. Since the disease dies out in the small world network (see Fig. 1 ), vaccination is not needed in this network for the parameter values taken. Especially in the cases of the random and meta-random networks, the effects of vaccination are drastic while for the scale-free network they are still considerable. What is particularly notable is that when comparing the various outcomes, topology has as great if not a greater impact on the epidemic than the vaccination strategy.

Besides the incidence curves, the final sizes of epidemics and the effect vaccination has on these are also of great importance. Table 5 shows the final sizes and the reductions in the final sizes for the various networks on which the disease can survive (for the chosen parameter values) with vaccination strategies for the cases where there is no delay in the vaccination. Fig. 4 and Table 6 show the incidence curves and the reductions in final sizes for the same parameters as used in Fig. 3 and Table 5 but with a delay of 40 days in the vaccination.

As can be expected for the given parameters, a delay has the biggest effect for the scale-free network. In that case, the epidemic is already past its peak and vaccinations only have a minor effect. For the random and meta-random networks, the Table 3 Illustration of vaccination strategies. Susceptible nodes are depicted by triangles, infectious nodes by squares, and the vaccinated nodes by circles. The average degree in these illustrations has been reduced to aid clarity. The starting point for contact tracing is labeled as A while the starting point for the follow links strategy is labeled as B. The number of doses dispensed in this illustration is 3.

Random Follow links Contact tracing Table 3 for the network topologies in Table 1 given a fixed transmission rate b. There is no delay in the vaccination and parameters are equal to those used in Fig. 1 . To further investigate the effects of delay in the case of random vaccination, we compute reductions in final sizes for delays of 5, 10, 15,y,150 days, in random, scale-free, and meta-random networks. Fig. 5 shows that, not surprisingly, these reductions diminish with longer delays. However, the reductions are strongly network dependent. On a scale-free network, the reduction becomes negligible as the delay approaches the epidemic peak time, while on random and meta-random networks, the reduction is about 40% with the delay at the epidemic peak time.

This section clearly shows that given a certain transmission rate b, the effectiveness of a vaccination strategy is impossible to predict without having reliable data on the network topology of the population. Next, we consider the case where instead of the transmission rate, the initial growth rate is given.

We line up incidence curves on various network topologies to a growth rate l predicted by a homogeneous mixing SIR model with the basic reproduction number R 0 ¼ 1:5 and recovery rate g ¼ 0:2 (in this case with exponential, l ¼ ðR 0 À1Þg ¼ 0:1). Table 7 summarizes the transmission rates that yield this exponential growth rate on the corresponding network topologies. The initial number of infectious individuals for models on each network topology needs to be adjusted as well so that the curves line up along the homogeneous mixing SIR incidence curve for 25 days. As can be seen from the table, the variations in the parameters are indeed very large, with the transmission rate for the small world network being nearly 8 times the value of the transmission rate for the scale-free network.

The incidence curves corresponding to the parameters in Table 7 are shown in Fig. 6 . As can clearly be seen, for these parameters, the curves overlap very well for the first 25 days, thus showing indeed the desired identical initial growth rates. However, it is also clear that the curves diverge strongly later on, with the epidemic on the small world network being the most severe. These results show that the spread of an epidemic cannot be predicted on the basis of having a good estimate of the growth rate alone. In addition, comparing Figs. 1 and 6, a higher transmission rate yields a much larger final size and a longer epidemic on the meta-random network.

The effects of the various vaccination strategies for the case of a given growth rate are shown in Fig. 7 . Given the large differences in the transmission rates, it may be expected that the final sizes show significant differences as well. This is indeed the case as can be seen in Table 8 , which shows the percentage reduction in final sizes for the various vaccination strategies. With no vaccination, the final size of the small world network is more than 3 times that of the scale-free network, but for all except the follow links vaccination strategy the percentage reduction on the small world network is greater. The effects of a 40-day delay in the start of the vaccination are shown in Fig. 8 and Table 9 . Besides the delay, all the parameters are identical to those in Fig. 7 and Table 8 . The delay has the largest effect on the final sizes of the small world network, increasing it by a factor of 20-30 except in the follow links case. On a scale-free network, the delay renders all vaccination strategies nearly ineffective.

These results also confirm the importance of network topology in disease spread even when the incidence curves have identical initial growth. The initial stages of an epidemic are insufficient to estimate the effectiveness of a vaccination strategy on reducing the peak or final size of an epidemic.

The relative importance of network topology on the predictability of incidence curves was investigated. This was done by considering whether the effectiveness of several vaccination strategies is impacted by topology, and whether the growth in the daily incidences has a network topology independent relation with the disease transmission rate. It was found that without a fairly detailed knowledge of the network topology, initial data cannot predict epidemic progression. This is so for both a given transmission rate b and a given growth rate l.

For a fixed transmission rate and thus a fixed per link transmission probability, given that a disease spreads on a network with a fixed average degree, the disease spreads fastest on scale-free networks because high degree nodes have a very high probability to be infected as soon as the epidemic progresses. In turn, once a high degree node is infected, on average it passes on the infection to a large number of neighbors. The random and meta-random networks show identical initial growth rates because they have the same local network topology. On different Table 1 without vaccination for the case where the initial growth rate is given. The transmission rates and initial number of infections for the various network topologies are given in Table 7 , while the remaining parameters are the same as in Fig. 1 Meta-random network Fig. 7 . The effects of the vaccination strategies for different topologies when the initial growth rate is given. The transmission rates b are as indicated in Table 7 , while the remaining parameters are identical to those in Fig. 6 . network topologies, diseases respond differently to parameter changes. For example, on the random network, a higher transmission rate yields a much shorter epidemic, whereas on the metarandom network, it yields a longer one with a more drastic increase in final size. These differences are caused by the spatial structures in the meta-random network. Considering that a metarandom network is a random network of random networks, it is likely that the meta-random network represents a general population better than a random network. For a fixed exponential growth rate, the transmission rate needed on the scale-free network to yield the given initial growth rate is the smallest, being about half that of the random and the meta-random networks. Hence, the per-link transmission probability is the lowest on the scale-free network, which in turn yields a small epidemic final size.

For different network topologies, we quantified the effect of delay in the start of vaccination. We found that the effectiveness of vaccination strategies decreases with delay with a rate strongly dependent on network topology. This emphasizes the importance of the knowledge of the topology, in order to formulate a practical vaccination schedule.

With respect to policy, the results presented seem to warrant a significant effort to obtain a better understanding of how the members of a population are actually linked together in a social network. Consequently, policy advice based on the rough estimates of the network structure should be viewed with caution.

This work is partially supported by NSERC Discovery Grants (JM, PvdD) and Mprime (PvdD). We thank the anonymous reviewers for their constructive comments.

The nodes in the network are labeled by their infectious status, i.e. susceptible, infectious, vaccinated, immune, refusing vaccination (but susceptible), and vaccinated but susceptible (the vaccine is not working), respectively.

The stochastic simulation is initialized by first labeling all the nodes as susceptible and then randomly labeling I 0 nodes as infectious. Then, before the simulation starts, 50% of susceptible nodes are labeled as refusing vaccination but susceptible. During the simulation, when a node is vaccinated, the vaccine has a probability of 30% to be ineffective. If it is not effective, the node remains fully susceptible, but will not be vaccinated again. If it is effective, then the immunity is built up linearly over a certain period of time, taken as 2 weeks.

We assume that infected persons generally recover in about 5 days, giving a recovery rate g ¼ 0:2. The initial number of infectious individuals I 0 is set to 100 unless otherwise stated, to reduce the number of runs where the disease dies out due to statistical fluctuations. All simulation results presented in Sections 4 and 5 are averages of 100 runs, each with a new randomly generated network of the chosen topology. The parameters in the simulations are shown in Table 4 .

The population size N was chosen to be sufficiently large to be representative of a medium size town and set to N ¼ 200,000, while the degree average is taken as /kS ¼ 5 with a maximum degree M¼ 100 (having a maximum degree only affects the scalefree network since the probability of a node having degree M is practically zero for the other network types). When considering a large group of people, a good first approximation is that the links between these people are random. Although it is clear that this cannot accurately represent the population since it lacks, for example, clustering and spatial aggregation (found in such common contexts as schools and work places), it may be possible that if the population is big enough, most if not all nonrandom effects average out. Furthermore, random networks lend themselves relatively well to analysis so that a number of interesting (and testable) properties can be derived. As is usually the case, the random network employed here originates from the concepts first presented rigorously by Erd + os and Ré nyi (1959). Our random networks are generated as follows:

(1) We begin by creating N unlinked nodes.

(2) In order to avoid orphaned nodes, without loss of generality, first every node is linked to another uniformly randomly chosen node that is not a neighbor.

(3) Two nodes that are not neighbors and not already linked are uniformly randomly selected. If the degree d of both the nodes is less than the maximum degree M, a link is established. If one of the nodes has maximum degree M, a new pair of nodes is uniformly randomly selected. (4) Step 3 is repeated N Â /kSÀN times.

When considering certain activities in a population, such as the publishing of scientific work or sexual contact, it has been found that the links are often well described by a scale-free network structure where the relationship between the degree and the number of nodes that have this degree follows a negative power law; see, for example, the review paper by Albert and Barabá si (2002) . Scale-free networks can easily be constructed with the help of a preferential attachment. That is to say, the network is built up step by step and new nodes attach to existing nodes with a probability that is proportional to the degree of the existing nodes. Our network is constructed with the help of preferential attachment, but two modifications are made in order to render the scale-free network more comparable with the other networks investigated here. First, the maximum degree is limited to M not by restricting the degree from the outset but by first creating a scale-free network and then pruning all the nodes with a degree larger than M. Second, the number of links attached to each new node is either two or three dependent on a certain probability that is set such that after pruning the average degree is very close to that of the random network (i.e. /kS ¼ 5).

Our scale-free network is generated as follows:

(1) Start with three fully connected nodes and set the total number of links L¼3.

(2) Create a new node. With a probability of 0.3, add 2 links.

Otherwise add 3 links. For each of these additional links to be added find a node to link to as outlined in step 3. (3) Loop through the list of nodes and create a link with probability d=ð2LÞ, where d is the degree of the currently considered target node. (4) Increase L by 2 or 3 depending on the choice in step 2. (5) Repeat NÀ3 times steps 2 and 3. (6) Prune nodes with a degree 4 M.

Small world networks are characterized by the combination of a relatively large number of local links with a small number of non-local links. Consequently, there is in principle a very large number of possible small world networks. One of the simplest ways to create a small world network is to first place nodes sequentially on a circle and couple them to their neighbors, similar to the way many coupled map lattices are constructed (Willeboordse, 2006) , and to then create some random short cuts. This is basically also the way the small world network used here is generated. The only modification is that the coupling range (i.e. the number of neighbors linked to) is randomly varied between 2 and 3 in order to obtain an average degree equal to that of the random network (i.e. /kS ¼ 5). We also use periodic boundary conditions, which as such is not necessary for a small world network but is commonly done.

The motivation for studying small world networks is that small groups of people in a population are often (almost) fully linked (such as family members or co-workers) with some connections to other groups of people.

Our small world network is generated as follows:

(1) Create N new unlinked nodes with index i ¼ 1 . . . N.

(2) With a probability of 0.55, link to neighboring and second neighboring nodes (i.e. create links i2iÀ1, i2iþ 1, i2iÀ2, i2iþ 2). Otherwise, also link up to the third neighboring nodes (i.e. create links i2iÀ1, i2i þ1, i2iÀ2, i2i þ2, i2iÀ3, i2i þ3). Periodic boundary conditions are used (i.e. the left nearest neighbor of node 1 is node N while the right nearest neighbor of node N is node 1). (3) Create the 'large world' network by repeating step 2 for each node. (4) With a probability of 0.05 add a link to a uniformly randomly chosen node excluding self and nodes already linked to. (5) Create the small world network by carrying out step 4 for each node.

In the random network, the probability for an arbitrary node to be linked to any other arbitrary node is constant and there is no clear notion of locality. In the small world network on the other hand, tightly integrated local connections are supplemented by links to other parts of the network. To model a situation in between where randomly linked local populations (such as the populations of villages in a region) are randomly linked to each other (for example, some members of the population of one village are linked to some members of some other villages), we consider a meta-random network. When increasing the number of shortcuts, a meta-random network transitions to a random network. It can be argued that among the networks investigated here, a meta-random network is the most representative of the population in a state, province or country.

Our meta-random network is generated as follows:

(1) Create N new unlinked nodes with index i ¼ 1 . . . N.

(2) Group the nodes into 100 randomly sized clusters with a minimum size of 20 nodes (the minimum size was chosen such that it is larger than /kS, which equals five throughout, to exclude fully linked graphs). This is done by randomly choosing 99 values in the range from 1 to N to serve as cluster boundaries with the restriction that a cluster cannot be smaller than the minimum size.

(3) For each cluster, create an Erd + os-Ré nyi type random network. (4) For each node, with a probability 0.01, create a link to a uniformly randomly chosen node of a uniformly randomly chosen cluster excluding its own cluster.

The network described in this subsection is a near neighbor network and therefore mostly local. Nevertheless, there are some shortcuts but shortcuts to very distant parts of the network are not very likely. It could therefore be called a medium world network (situated between small and large world networks). The key feature of this network is that despite being mostly local its degree distribution is identical to that of the random network.

Our near neighbor network is generated as follows:

(1) Create N new unlinked nodes with index i ¼ 1 . . . N.

(2) For each node, set a target degree by randomly choosing a degree with a probability equal to that for the degree distribution of the random network.

(3) If the node has reached its target degree, continue with the next node. If not continue with step 4. (4) With a probability of 0.5, create a link to a node with a smaller index, otherwise create a link to a node with a larger index (using periodic boundary conditions). (5) Starting at the nearest neighbor by index and continuing by decreasing (smaller indices) or increasing (larger indices) the index one by one while skipping nodes already linked to, search for the nearest node that has not reached its target degree yet and create a link with this node. (6) Create the network by repeating steps 3-5 for each node.

For all the strategies, vaccination is voluntary and quantity limited. That is to say only susceptibles who do not refuse vaccination are vaccinated and each day only a certain number of doses is available. For each strategy for each time unit, first a group of eligible nodes is identified and then up to the maximum number of doses is dispensed among the eligible nodes according to the strategy chosen.

In this strategy, nodes with the highest degrees are vaccinated first. The motivation for this strategy is that high degree nodes on average can be assumed to transmit a disease more often than low degree nodes.

Numerically, the prioritized vaccination strategy is implemented as follows:

(1) For each time unit, start at the highest degree (i.e. consider nodes with degree d¼M) and repeat the steps below until either the number of doses per time step or the total number of available doses is reached.

(2) Count the number of susceptible nodes for degree d.

(3) If the number of susceptible nodes with degree d is zero, set d ¼ dÀ1 and return to step 2. (4) If the number of susceptible nodes with degree d is smaller than or equal to the number of available doses, vaccinate all the nodes, then set d ¼ dÀ1 and continue with step 2. Otherwise continue with step 5.

(5) If the number of susceptible nodes with degree d is greater than the number of currently available doses, randomly choose nodes with degree d to vaccinate until the available number of doses is used up. (6) When all the doses are used up, end the vaccination for the current time unit and continue when the next time unit arrives.

In practice prioritizing on the basis of certain target groups such as health care workers or people at high risk of complications can be difficult. Prioritizing on the basis of the number of links is even more difficult. How would such individuals be identified? One of the easiest vaccination strategies to implement is random vaccination.

Numerically, the random vaccination strategy is implemented as follows:

(1) For each time unit, count the total number of susceptible nodes.

(2) If the total number of susceptible nodes is smaller than or equal to the number of doses per unit time, vaccinate all the susceptible nodes. Otherwise do step 3. (3) If the total number of susceptible nodes is larger than the number of doses per unit time, randomly vaccinate susceptible nodes until all the available doses are used up.

One way to reduce the spread of a disease is by splitting the population into many isolated groups. This could be done by vaccinating nodes with links to different groups. However given the network types studied here, breaking links between groups is not really feasible since besides the random cluster network, there is no clear group structure in the other networks. Another approach is the follow links strategy, inspired by notions from social networks, where an attempt is made to split the population by vaccinating the neighbors and the neighbor's neighbors and so on of a randomly chosen susceptible node.

Numerically, the follow links strategy is implemented as follows:

(1) Count the total number of susceptible nodes.

(2) If the total number of susceptible nodes is smaller than or equal to the number of doses per unit time, vaccinate all the susceptible nodes. (3) If the total number of susceptible nodes is greater than the number of available doses per unit time, first randomly choose a susceptible node, label it as the current node, and vaccinate it. (4) Vaccinate all the susceptible neighbors of the current node. (5) Randomly choose one of the neighbors of the current node. (6) Set the current node to the node chosen in step 5. (7) Continue with steps 4-6 until all the doses are used up or no available susceptible neighbor can be found. (8) If no available susceptible neighbor can be found in step 7, randomly choose a susceptible node from the population and continue with step 4.

Contact tracing was successfully used in combating the SARS virus. In that case, everyone who had been in contact with an infectious individual was isolated to prevent a further spread of the disease. De facto, this kind of isolation boils down to removing links rendering the infectious node degree 0, a scenario not considered here. Here contact tracing tries to isolate an infectious node by vaccinating all its susceptible neighbors.

Numerically, the contact tracing strategy is implemented as follows:

(1) Count the total number of susceptible nodes.

(2) If the total number of susceptible nodes is smaller than or equal to the number of doses per unit time, vaccinate all the susceptible nodes.

(3) Count only those susceptible nodes that have an infectious neighbor. (4) If the number of susceptible nodes neighboring an infectious node is smaller than or equal to the number of doses per unit time, vaccinate all these nodes. (5) If the number of susceptible nodes neighboring an infectious node is greater than the number of available doses repeat step 6 until all the doses are used up. (6) Randomly choose an infectious node that has susceptible neighbors and vaccinate its neighbors until all the doses are used up.

Statistical mechanics of complex networks

Infectious Diseases of Humans

A comparative analysis of influenza vaccination programs

When individual behaviour matters: homogeneous and network models in epidemiology

Compartmental models in epidemiology

Comparative estimation of the reproduction number for pandemic influenza from daily case notification data

Trial of 2009 influenza A (H1N1) monovalent MF59-adjuvanted vaccine

Efficient immunization strategies for computer networks and populations

Vaccination against 2009 pandemic H1N1 in a population dynamical model of Vancouver, Canada: timing is everything

Early real-time estimation of the basic reproduction number of emerging infectious diseases. Phys. Rev. X 2, 031005. Erd + os

Modeling Infectious Diseases in Humans and Animals

Infectious disease control using contact tracing in random and scale-free networks

The effect of network mixing patterns on epidemic dynamics and the efficacy of disease contact tracing

Effective degree network disease models

Transmission dynamics and control of severe acute respiratory syndrome

Generality of the final size formula for an epidemic of a newly invading infectious disease

Effective degree household network disease models

Immunization and epidemic dynamics in complex networks

Network theory and SARS: predicting outbreak diversity

A note on a paper by Erik Volz: SIR dynamics in random networks

Effective vaccination strategies for realistic social networks

Edge based compartmental modelling for infectious disease spread

Epidemic incidence in correlated complex networks

Office of the Provincial Health Officer, 2010. B.C.s Response to the H1N1 Pandemic

Initial human transmission dynamics of the pandemic (H1N1) 2009 virus in North America

Dynamics and control of diseases in networks with community structure

A high-resolution human contact network for infectious disease transmission

Networks, epidemics and vaccination through contact tracing

Estimated epidemiologic parameters and morbidity associated with pandemic H1N1 influenza

SIR dynamics in random networks with heterogeneous connectivity

Effects of heterogeneous and clustered contact patterns on infectious disease dynamics

Dynamical advantages of scale-free networks