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. shows the cumulative probability density
that a bridge node has a degree
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.
Cumulative distributions of the number of weak ties in five empirical networks.
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
are generated by randomly connecting communities, which are themselves random networks, following the algorithm in Ref. 
. 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. 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 
, 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 
, 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. 
. 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
are the transmission rate and the recovery probability, respectively. The extent of an epidemic is characterized by the final epidemic ratio
, the fraction of the population ever infected at the end of the epidemic, and the peak prevalence
, the highest density of infected nodes in the population at a time during the epidemic.
Structural Properties of the five empirical networks.
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
, i.e., fraction of immunized nodes, the final epidemic ratio
is obtained for each of the three strategies. The differences
would indicate the performance of ACQ and CBF relative to BHD. shows the differences for various combinations of the modularity
. The differences are positive over most of the
space, with BHD leading to about
) 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
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
[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 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.
Comparison of efficacy of immunization algorithms in simulated networks.
shows the results of
obtained for the empirical networks. In most cases, the final epidemic ratio is smaller for BHD than ACQ and CBF. For example,
is on average
) smaller than
for the Caltech network,
) smaller for the Princeton network, and
) smaller for the Georgetown University network. For the Oklahoma University network,
) smaller than
) when the immunization coverage is not too small, e.g.
) smaller than
) 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 , the degree assortativity
) for the Oklahoma (North Carolina) University network. For an immunization coverage of
, BHD performs better in all empirical networks than both ACQ and CBF, with a maximum in
near this coverage. When the coverage is higher (e.g.
), the differences in
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 .
Comparison of efficacy of immunization algorithms in empirical networks.
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 
denoting ACQ, CBF and BHD, be the size of the giant component of the resulting network using the algorithm
and an immunization coverage
be the size of the giant component of the network before applying an immunization algorithm. The relative difference
is a measure of how effective BHD breaks up a network relative to ACQ (and CBF). shows the results of
for the five empirical networks. The positive
values in almost all the cases indicate that BHD is more effective. The results show a similar trend as a function of
as in the differences in final epidemic ratio shown in . Percentage wise,
is smaller than
for the same values of
in the same empirical 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.
Comparison of giant components of different immunization algorithms in empirical networks.
The effectiveness of BHD is further illustrated in , 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 ) makes it difficult for both BHD and CBF to search for the bridge nodes.
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.
A more efficient algorithm is one that visits fewer nodes before identifying the targeted nodes for immunization. Let
be the numbers of nodes visited by the self-avoiding walks before getting at the targeted nodes. gives
for the five empirical networks. For small immunization coverage (
, indicating that BHD is a more efficient algorithm.
Comparison of number of nodes visited before identifying immunization nodes in CBF and BHD.
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 
. 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
, respectively. shows the results of
for different numbers of links added or removed, with a constant immunization coverage of
. 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
Robustness of BHD in networks with noise as modeled by random addition and removal of links.