An Efficient Immunization Strategy for Community Networks

An efficient algorithm that can properly identify the targets to immunize or quarantine for preventing an epidemic in a population without knowing the global structural information is of obvious importance. Typically, a population is characterized by its community structure and the heterogeneity in the weak ties among nodes bridging over communities. We propose and study an effective algorithm that searches for bridge hubs, which are bridge nodes with a larger number of weak ties, as immunizing targets based on the idea of referencing to an expanding friendship circle as a self-avoiding walk proceeds. Applying the algorithm to simulated networks and empirical networks constructed from social network data of five US universities, we show that the algorithm is more effective than other existing local algorithms for a given immunization coverage, with a reduced final epidemic ratio, lower peak prevalence and fewer nodes that need to be visited before identifying the target nodes. The effectiveness stems from the breaking up of community networks by successful searches on target nodes with more weak ties. The effectiveness remains robust even when errors exist in the structure of the networks.


Introduction
Epidemics could lead to a serious loss in life and have a huge impact on the economy, as we witnessed during the outbreaks of SARS (severe acute respiratory syndromes) in 2003 and H1N1 Influenza A virus in 2009 [1][2][3]. The problem of preventing an epidemic in time is of great importance and it has attracted much attention from researchers across different fields [4][5][6][7][8][9][10][11][12]. While immunization and quarantine are the two basic measures [13][14][15], finding an efficient way of identifying the targets to be immunized or quarantined so as to suppress an infection effectively remains a pressing issue [16].
The hubs, individuals with high centrality, in complex networks are commonly believed to be the most influential nodes as they could affect their many neighboring nodes [17]. Kitsak et al. pointed out that the nodes with a high k-shell are more influential spreaders in some real networks [18]. Undoubtedly, it is important to identify such influential nodes, but an effective method would require global information about the network structure. In these global strategies, the influential hubs can be identified by centrality measures, such as the degree centrality [19,20], eigenvector centrality [21], and betweenness centrality [22,23]. Such global strategies, however, become impractical for large-scale networks. Another type of method requires only local information. The acquaintance immunization strategy (henceforth labeled as ACQ) [24] in which random acquaintances of randomly chosen nodes are immunized is an example of local search algorithms. ACQ was shown to be an efficient algorithm for large-scale networks with broad-degree distributions [24]. Community structure at the mesoscale level is ubiquitous in a variety of real complex systems [25,26] such as Facebook [27,28] and Twitter [29], which plays an important role in the dynamics of epidemics [30][31][32][33][34][35]. In the presence of communities, the weak ties connecting a pair of nodes belonging to different communities, called the bridge nodes [36][37][38], provide the pathways for information and diseases to propagate from one community to another. These bridge nodes were found to be more important than the hubs in diffusing information through community networks [39][40][41]. Therefore, identifying the bridge nodes in community networks are crucial in preventing epidemic outbreaks [42][43][44]. Deterministic and stochastic algorithms have been designed to search for the bridge nodes [45]. Chen et al. [46] proposed an immunization strategy based on an equal graph partitioning algorithm to identify the minimum group that separates a network into several clusters of approximately equal size. The role of the minimum separator group is similar to that of the bridge nodes connecting different communities. The algorithm is effective in that only a small immunization ratio is needed, which is the fraction of immunized nodes. However, the algorithm requires the structural information of the whole network. Similar to other global strategies, it becomes impractical due to the high computing cost and, more fundamentally, the lack the complete information in large networks. Salathe and Jones [45] proposed the community bridge finder (CBF), which is a stochastic algorithm to search for the bridge nodes based only on local structural information, and found that the method is more efficient than immunization strategies targeting different kinds of hubs.
Community networks typically exhibit a heterogeneous distribution in the number of weak ties originating from a bridge node [36,47]. In the worldwide air traffic network, for example, bridge nodes can be divided into four classes: nonhub connector nodes, nonhub kinless nodes, connector hubs, and kinless hubs [48]. It was found that immunizing bridge hubs that connect a community to many other communities could protect a network efficiently against epidemics [49]. Identifying the bridge hubs with a larger number of weak ties, however, is quite challenging as the mesoscopic-scale community structure is difficult to resolve for large-scale networks [50]. It is against this backdrop that we propose an immunization strategy that identifies the bridge hubs by random walks in an expanding friendship circle. The strategy, which we call bright-hub detector (BHD) relies only on local structural information. We compare results obtained by BHD with ACQ and CBF strategies and find that it performs better in simulated networks and empirical community networks generated from real data. Simulation results also show that our strategy has the merit of being robust against noise.

Results
To illustrate the community structure in real-world networks and the necessity of an algorithm that focuses on identifying the bridge hubs, we have analyzed the heterogeneity of bridge nodes in the networks of students in five universities in the US using Facebook data. Details on constructing the networks from data are given in the Materials and Methods section. Figure 1 shows the cumulative probability density P(k w ) that a bridge node has a degree k w or higher in the students' Facebook networks of Caltech, Princeton, Georgetown, Oklahoma, and North Carolina. The distributions indicate that it is important to identify the bridge nodes with more weak ties, in addition to identifying only the bridge nodes as in CBF.
We present results of three different strategies (ACQ, CBF and BHD) on choosing immunizing nodes in simulated and empirical community networks within the susceptible-infected-recovered (SIR) epidemiological model. Briefly, simulated networks of different modularity Q are generated by randomly connecting communities, which are themselves random networks, following the algorithm in Ref. [45]. Empirical networks are constructed from Facebook data of students in each of five US universities, with a link defined by two students being online friends and belonging to the same dormitory or the same major in the same year of study. Table 1 lists the properties of these empirical networks. Details about network construction, the three strategies, and SIR dynamics are given in the Materials and Methods section. The ACQ, CBF and BHD strategies rely only on local structural information. In ACQ [24], a node is randomly picked and then a neighbor of the chosen node is randomly selected for immunization. The algorithm has a higher chance to immunize the hubs. In CBF [45], a step forward in a self-avoiding walk is checked for a bridge between communities by examining the existence of links or paths from the neighbors of the last node back to the nodes visited in the trail of the self-avoiding walk. The node before crossing the bridge is then identified as the bridge node and immunized. In addition, the supplementary rule of immunizing a node that has been visited twice by self-avoiding walks would pick up some hubs. Here, we implemented CBF as given in Ref. [45]. The bridge-hub detector (BHD) that we proposed in this paper extends the self-avoiding searching scheme to examining the overlap and the existence of links from all the neighbors of the last node back to the union of the friendship circles of all the nodes in the trail of the walk. A pair of nodes, a bridge node and a bridge hub, are searched for immunization via a self-avoiding walk (Readers are referred to the Materials and Methods section for more information). In the SIR model, the parameters b and m are the transmission rate and the recovery probability, respectively. The extent of an epidemic is characterized by the final epidemic ratio R, the fraction of the population ever infected at the end of the epidemic, and the peak prevalence I m , the highest density of infected nodes in the population at a time during the epidemic.
To compare the performances of ACQ and CBF with that of BHD, we have carried out the SIR dynamics on simulated networks with different modularity. For a given immunization coverage f , i.e., fraction of immunized nodes, the final epidemic ratio R is obtained for each of the three strategies. The differences R ACQ {R BHD and R CBF {R BHD would indicate the performance of ACQ and CBF relative to BHD. Figure 2 shows the differences for various combinations of the modularity Q and coverage f . The differences are positive over most of the Q-f space, with BHD leading to about 6:1% (2:8%) of fewer nodes being infected than ACQ (CBF). The results indicate that BHD is, in general, more effective in suppressing an epidemic. There are patches in the Q-f space that BHD is out-performed by ACQ and CBF. This is particularly apparent for networks with a strong community structure characterized by a high modularity. For example, both ACQ and CBF perform better in networks with Q[[0.95,0.97]. In these cases, an epidemic outbreak is mostly restricted in a local community and thus the better strategies are those that could For every network, the community structure is detected by the method proposed by Newman and Girvan [55]. Weak ties and bridge nodes are then identified. The number of weak ties emanating from each bridge node is recorded to give the cumulative distribution. Results are shown for students' networks for Caltech (red squares), Princeton (green circles), Georgetown (blue up triangles), Oklahoma (cyan down triangles) and North Carolina (magenta diamonds). doi:10.1371/journal.pone.0083489.g001 confine and suppress an epidemic to within the community that the outbreak starts. Immunizing the hubs with large degrees as in ACQ and CBF can prevent epidemic spreading within a community more efficiently. BHD spends some of the immunization coverage on removing nodes that belong to neighboring communities rather than the community of the outbreak itself and this becomes less effective in saving the nodes within the outbreak community from infection than ACQ and CBF. Figure 3 shows the results of R ACQ {R BHD and R CBF {R BHD obtained for the empirical networks. In most cases, the final epidemic ratio is smaller for BHD than ACQ and CBF. For example, R BHD is on average 8:5% (6:0%) smaller than R ACQ (R CBF ) for the Caltech network, 4:3% (2:3%) smaller for the Princeton network, and 3:2% (2:2%) smaller for the Georgetown University network. For the Oklahoma University network, R BHD is about 3:0% (1:4%) smaller than R ACQ (R CBF ) when the immunization coverage is not too small, e.g. f~20% (f~22%). Similarly, R BHD is about 2:9% (1:0%) smaller than R ACQ (R CBF ) at f~20% (f~26%) for the North Carolina University network. In the Oklahoma and North Carolina networks, BHD is out-performed by CBF when the immunization coverage is low. The ability of CBF to immunize the bridge nodes and some hubs makes it more effective in networks with a high assortativity and heterogeneity. As shown in Table 1, the degree assortativity r and heterogeneity H are &0:327 (&0:217) and &8:240 (&6:941) for the Oklahoma (North Carolina) University network. For an immunization coverage of f &20%, BHD performs better in all empirical networks than both ACQ and CBF, with a maximum in R ACQ {R BHD near this coverage. When the coverage is higher (e.g. f w20%), the differences in R for the three algorithms diminish, as the many immunized nodes would tend to be effective in breaking up a community and suppress an epidemic regardless of the algorithm. The results for the differences in peak prevalence are given in Figure S1 and the features are essentially the same as those in Figure 3.
Whether an algorithm is effective in preventing an epidemic is closely related to its effectiveness in breaking up the network after immunizing or removing a certain fraction of nodes [51]. Let G a (f ), with a denoting ACQ, CBF and BHD, be the size of the giant component of the resulting network using the algorithm a and an immunization coverage f , and G(0) be the size of the giant Structural properties including the network size (N), number of edges (E), the community number (M), modularity (Q) [55], degree assortativity (r) [56], degree heterogeneity (H = Sk 2 T/SkT 2 )), clustering coefficient(C), average shortest path length (SdT) and average degree (SkT) are tabulated for each of the five empirical networks. doi:10.1371/journal.pone.0083489.t001   network. It is a result of the removal of some bridge hubs (bridge nodes with more weak links to other communities), by BHD, which would result in a network that has a smaller mean degree. This is indeed the case, as shown in Figure S2. The geometry of the resulting network also affects the duration of an epidemic. In particular, resulting networks with smaller mean degree lead to a longer duration, as the disease can only spread by infecting one node after another. BHD is therefore expected to have a longer epidemic duration, despite a smaller final epidemic ratio and prevalence. Figure S3 shows that the epidemic duration is slightly longer for BHD, as compared with those with ACQ and CBF. The effectiveness of BHD is further illustrated in Figure 5, which compares the number of weak ties of the bridge hubs and bridge nodes identified for immunization using BHD with that of the bridge nodes identified by CBF. The results show that BHD indeed can identify the nodes with more weak links for removal. In addition, the bridge nodes identified by BHD carry more weak ties than those identified by CBF, further improving the effectiveness. In the Princeton University network, however, the large mean community size (see Table 1) makes it difficult for both BHD and CBF to search for the bridge nodes.
A more efficient algorithm is one that visits fewer nodes before identifying the targeted nodes for immunization. Let S CBF and S BHD be the numbers of nodes visited by the self-avoiding walks before getting at the targeted nodes. Figure 6 gives S CBF =S BHD for the five empirical networks. For small immunization coverage (f ƒ20%), S CBF =S BHD &1:5, indicating that BHD is a more efficient algorithm.
Another aspect of an effective algorithm is the robustness to errors or noise in network information. Such errors are common in social networks due to, for example, the inconsistency for two individuals to express their relationship [52]. Using an empirical network, we have tested the robustness of BHD by adding or removing a number of links from the network. SIR dynamics is then studied on the modified network without and with the BHD algorithm. The resulting final epidemic ratios are denoted by R 0 and R BHD , respectively. Figure 7 shows the results of R_BHD~(R 0 {R BHD )=R 0 for different numbers of links added or removed, with a constant immunization coverage of 5%. The results show that BHD performs well even when the networks are modified randomly. More results corresponding to other values of immunization coverage are shown in Figure S4.

Summary and Discussion
The heterogeneous distribution of weak ties in real-world community networks points to the importance of the bridge hubs in the control of transmission of information or diseases but these nodes are difficult to identify. We have proposed and studied the effectiveness of a bridge-hub detector strategy. It is a local strategy searching for bridge nodes and bridge hubs based on the idea of referencing to an expanding friendship circle as a self-avoiding walk proceeds. We applied BHD to simulated networks and empirical networks among students in five US universities constructed by using social network data. In general, BHD is more effective in preventing an epidemic when compared with Figure 5. Comparison of average number of weak ties among immunized bridge hubs identified by BHD, bridge nodes identified by BHD and bridge nodes identified by CBF. BHD identifies a pair of nodes for immunization via a self-avoiding walk algorithm. One node is a bridge hub and another a bridge node.
The average number of weak ties among these two types of immunized nodes [red squares (BHD hubs) and gray diamonds (BHD nodes)] are shown for different values of immunization coverage f , together with the results from immunized bridge nodes identified by CBF (blue circles). Results are obtained by averaging over 10 4 realizations for each value of f . For comparison, the results based on the method proposed by Newman and Girvan [55] are shown as the green dashed lines. doi:10.1371/journal.pone.0083489.g005 other local immunization strategies such as ACQ and CBF, for a practical range of immunization coverage. It gives a smaller final epidemic ratio and peak prevalence. Its effectiveness can be attributed to better identification of immunized nodes that carry more weak ties than those picked up by ACQ and CBF. BHD thus breaks up the community networks more effectively and suppresses an epidemic. Although BHD and CBF are both based on selfavoiding walks, BHD is more efficient in that it identifies the immunization nodes after visiting fewer nodes. The good performance of BHD remains robust even when errors exist in the structure of the underlying network.
In general, BHD is capable of identifying bridge nodes with more weak ties and it is particularly useful in dealing with community networks with a broad distribution in the number of weak ties among the bridge nodes. It can be readily generalized to other tasks. For example, mistakenly chosen nodes could be reduced by requiring that a node must have been identified twice or more times before it is immunized. The algorithm can also be applied to overlapping [50] and time-varying [53] community networks.

Materials and Methods
We have studied the effectiveness of our local immunization strategy in simulated and empirical community networks using the susceptible-infected-recovered (SIR) epidemiological model. Here, we give the details with respect to the following issues: communitynetwork construction, bridge-hub detector algorithm, and SIR dynamics.

Simulated and empirical community networks
The simulated community networks of different modularity Q are generated by the algorithm given in Ref. [45]. There are m independent random communities. In each community, n nodes are randomly connected so that the mean degree is Sk in T. These communities are then connected randomly by E out links. The simulated community network thus has a total of mn nodes and mnSk in TzE out undirected links. We used the same set of parameters as in Ref. [45], namely m~50, n~40, Sk in T~8, and E out~2 000. After generating the network, the modularity Q can be evaluated according to the definition given in Ref. [25]. The modularity Q can be varied by rewiring some intercommunity links into intra-community links, following the rewiring procedures given in Ref. [45]. While the modularity increases with rewiring, the degree heterogeneity remains nearly unchanged.
Empirical community networks are constructed using the collegiate social network data from Facebook (www.facebook. com) studied in Ref. [27]. The data of five universities in the US are studied (Available: https://code.google.com/p/ socialnetworksimulation/). They include data of students from the California Institute of Technology (Caltech), Princeton University, Georgetown University, University of Oklahoma, and University of North Carolina. The data provide information on the dormitory, majoring subject and year of class of the members. Based on the data, a community network is constructed [45] by linking up two members when (i) they are online friends of each other, and (ii) they belong to the same dormitory or the same major in the same year of study. The largest connected component of the network is then retained for carrying out our study. Basic statistical properties of the five empirical networks are given in Table 1. These networks exhibit the small-world character with a high clustering coefficient and a short average path length. The high modularity indicates a strong community feature.

Local Immunization Strategies and Bridge-Hub Detector
The present paper compares results based on our bridge-hub detector algorithm (BHD) with those obtained by other local strategies based on acquaintance immunization (ACQ) and the community bridge finder (CBF). Before discussing the BHD algorithm, we outline the ideas behind ACQ and CBF.
The ACQ algorithm immunizes randomly chosen acquaintances of randomly chosen nodes [24]. In ACQ, a node is picked randomly and then a neighbor of the chosen node is picked randomly for immunization. The procedure is then repeated until the desired immunization coverage is achieved. Therefore, a node that is a neighbor of many other nodes, i.e., a hub, will have a higher chance to be chosen for immunization. The algorithm does not require any information about the degree of the nodes. It is efficient for large networks with a broad degree distribution. A similar algorithm that requires a node to be chosen two times according to the ACQ random-pick processes (ACQ2) before it is immunized has also been studied [24]. Comparing with ACQ, ACQ2 has a higher probability of immunizing the hubs.
Bridge nodes are important for transmission through community networks, but ACQ does not aim at the bridge nodes. In contrast, CBF is designed to search for bridge nodes [45]. It is an algorithm based on self-avoiding walks. To identify a bridge and its associated bridge node for immunization, a self-avoiding walk is executed starting from a randomly chosen node v 0 . The following procedure is taken after every step when the walk has visited three or more nodes (see Figure 8). For a walk after t steps (t §2), the set of all nodes visited in the t steps so far is denoted by fv t 0 g for all t 0~0 ,1, . . . ,t. Thus, v t is the node that the walk currently locates after step t and v t{1 is the node visited at step t{1. The first check is to examine whether the node v t has a link or several links to the nodes in the set fv t 0 g other than the link between v t and v t{1 . If it is the case, the self-avoiding walk continues to step tz1. If not, then v t{1 is considered a possible target of a bridge node. To determine whether the node v t{1 is a bridge node, two nodes are randomly chosen among all the possible nodes that the walk could go in step tz1, i.e., two neighbors of the node v t are randomly chosen from all the neighbors (except the node v t{1 due to the selfavoiding restriction of the walk). In the case that there is only one neighbor to choose from, the only neighbor will be considered. If there exists a path from any of the two chosen nodes back to any node in the set fv t 0 g, then the node v t{1 will not be regarded as a bridge node and the walk moves on from v t to some node v tz1 . If there exists no path back to the set fv t 0 g from both of the chosen nodes, v t{1 is regarded as a bridge node that connects two communities and it will be immunized. A new self-avoiding walk will start again at another randomly chosen node and the procedure is repeated until the desired immunization ratio is achieved. The idea behind CBF is that a community is formed by a circle of close friends, and thus when the two randomly chosen neighbors of v t cannot be traced back to the community that v t{1 belongs to, the link between v t{1 and v t is likely to be a bridge between two communities and so the node v t{1 is a bridge node. In practice, two additional checks are implemented to shorten the computing time [45]. Firstly, the number of nodes registered in a running path is kept at the length of ten, using the latest ten nodes visited. Secondly, the number of visits by any random walk for each node is recorded. When the number k of visits equals a certain number (k~2 in Ref. [45]), the node is immunized. We have implemented CBF following the algorithm in Ref. [45], where it has been shown that, without prior knowledge of the community structure, CBF is more efficient than ACQ and other immunization strategies that target at the different kinds of hubs. In its design, CBF does not aim at identifying the bridge hubs. In real-world community networks such as those in Facebook [47], worldwide air traffic network [48], and the five collegiate community networks studied here, the heterogeneous distribution in the number of weak ties among bridge nodes indicates the importance of bridge hubs. Figure 9 shows an example of a bridge hub through a visualization of the students' network in Caltech. We propose a bridge-hub detector (BHD) for more effective immunization in community networks. It is a local algorithm based on an expanding friendship circle and it does not rely on prior knowledge of the community structure. As in CBF, the algorithm starts with a self-avoiding walk at a randomly chosen node. The following procedure is taken after every step when the walk has visited three or more sites (see Figure 8). Let v t be the node that the walker locates after step t and f t be the set of all neighbors of the node v t . For a walk up to t steps (t §2), the following steps are carried out between the set f t and the set F t{1 :f 0 |f 1 |f 2 | . . . |f t{1 . The set F t{1 is the union of all the friendship circles of all the nodes visited by the walker up to the step t{1 and it expands as the self-avoiding walk proceeds. Apparently, we have v t{1 [f t . If every other node in f t either already belongs to the set F t{1 or has at least a link to the nodes within F t{1 , v t will not be taken as the target of immunization and F t will be updated to F t~ft |F t{1 . The self-avoiding walk then moves on from v t . Otherwise, there must be at least a node in f t that is not a member in F t{1 and is not connected to the nodes in F t{1 . The node v t is then targeted for immunization. In addition, among the nodes in f t that do not belong to F t{1 and cannot be linked back to F t{1 , one node (call it v H ) is randomly chosen for immunization. A pair of nodes, v t and v H , are immunized and the self-avoiding walk stops. A new walk is initiated at another randomly chosen node again. The procedure is repeated until the desired immunization ratio is achieved. Similar to the idea in ACQ, the immunized node v H in every self-avoiding walk is likely to be a bridge hub in the presence of heterogeneous distribution of weak ties among the bridge nodes, while v t is a bridge node. The algorithm is illustrated schematically in Figure 8. Practically, we terminate a walk when it fails to identify immunization nodes after 20 steps. As in CBF, BHD is effective when the search for immunization nodes begins after t §2 steps. Figure S5 in Supporting Information gives results when the search begins after different numbers of steps. Through computational complexity analysis (see Text S1 in Supporting Information for more details), the algorithms ACQ, CBF and BHD take on the worst-case run times that go as O(fN), O(fN 3 ) and O(f SkTN 3 ), respectively. For the different algorithms working on systems with the same parameters (the same network size N and immunization ratio f etc.), ACQ is the fastest, followed by CBF and BHD is the slowest. On a sparse network with small SkT, BHD will have almost the same computational complexity as CBF.

Epidemic Dynamics
The susceptible-infected-recovered (SIR) epidemiological model [54] is used to test the performance of different immunization strategies on community networks. In the model, each node in the network represents an individual that can be in one of three states: susceptible (S), infected (I), or refractory/recovered (R); and each link represents a connection that could spread a disease. When an immunization strategy is executed, a percentage of nodes are first removed from the network by implementing ACQ, CBF or BHD. The remaining nodes are set to the susceptible state. To initiate an infection, a node is randomly chosen and turned into the I state. In a time step, a susceptible node will be infected with a probability Figure 8. Schematic illustration of CBF strategy and BHD strategy. The CBF strategy: (a) A self-avoiding walk starts at a randomly chosen node v 0 . (b)-(c) The walk visited fv 0 ,v 1 ,v 2 g after two steps. The node v 2 does not have any other links back to v 0 and v 1 other than the link that took the walk from v 1 to v 2 . The node v 1 is a potential candidate of a bridge node. Two neighbors of v 2 , namely v 3 and v F2 , are randomly picked and each is examined for connections to the visited set of nodes. As v 3 has links with v 0 and v 1 , the target node v 1 is dismissed as a bridge node and the walk continues. (d) The walk moves to v 3 after three steps. The node v 3 has links to previously visited nodes v 0 and v 1 , and thus the walk continues. (e) The walk moves to v 4 after four steps. The node v 4 does not have any other links back to previously visited nodes other than the link that took the walk from v 3 to v 4 . The node v 3 is a potential target of a bridge node. Two neighbors of v 4 are randomly chosen. (f) If v R2 and v H are chosen, these nodes do not connect back to the previously visited nodes and v 3 is identified as a bridge node and immunized. The BHD strategy: (a) A self-avoiding walk starts at a randomly chosen node v 0 . (b)-(c) The walk visited v 0 , v 1 and v 2 after two steps. The set F 2 is the union of all the neighboring nodes or friendship circles of v 0 , v 1 and v 2 , as shaded in (c). (d) The walk moves to v 3 after three steps. The friendship circle f 3 of node v 3 consists of v 0 , v 1 , v 2 , and v 4 . As all the nodes in f 3 either belong to F 2 or have a link to at least a node in F 2 , the node v 3 is not a potential target for immunization. (e) The union of friendship circles is updated to F 3~f3 |F 2 as shaded. The walk continues and reaches node v 4 after four steps. The friendship circle R2 and v H , among them v R2 and v H do not belong to F 3 and do not have a link to nodes in F 3 . The node v 4 is then identified as a bridge node for immunization. In addition, among those nodes in f 4 that cannot be linked back to F 3 , one node, e.g., v H , is randomly chosen and identified as a bridge hub for immunization. doi:10.1371/journal.pone.0083489.g008 1{e ({bÃi) , where i is the number of infected nodes among the connected neighbors of the node. Here, b is a parameter characterizing the transmission rate. Meanwhile, an infected node has a recovery probability m to turn into the R state. Once an individual is in the R state, there will be no further change. In the simulations, the parameters are taken to be b~0:08 and m~0:2 to ensure an outbreak and the state of every node is updated synchronously in every time step. The dynamics ends when all infected nodes have recovered. The resulting population contains nodes only in the S state and R state. We record the final epidemic ratio R corresponding to the density of R nodes at the end of the epidemic, the peak prevalence I m corresponding to the highest density of infected nodes in the network during the epidemic, and the duration of epidemic before the dynamics ends, and compare these quantities for ACQ, CBF and BHD.  Figure S4 Robustness of BHD in networks with noise as modeled by addition and removal of links for 20% immunization coverage. As in Figure 7, the quantity DR BHD~( R 0 {R BHD )=R 0 is shown as a function of the number of links randomly added to or removed from an empirical network. Results are shown for each of the five empirical networks as labeled. The immunization coverage is f~20%. The SIR Figure 9. Visualizing the community structure and a bridge hub in the Caltech network. The Caltech network can be divided into 13 communities based on the method of Newman and Girvan [55], as illustrated by the different colors. Also illustrated is a bridge hub H that carries the largest number of weak ties and connects with other bridge nodes labeled as n 1 to n 13 . The number on a weak tie shows the difference in the numbers of weak ties originated from the node H and the bridge node at the other end of the weak tie. doi:10.1371/journal.pone.0083489.g009 parameters are b~0:08 and m~0:2. Results are obtained by averaging over 10 4 realizations for each value of added and removed links. (EPS) Figure S5 Effects of starting the search for immunization nodes from different number of steps on the final epidemic ratio. Results in the main text and figures are obtained by starting the search for immunization nodes two steps after a self-avoiding walk began. Here, results for starting the search after 1, 2, 3, 4, 5 steps are shown for each of the five empirical networks.