Fundamental difference between superblockers and superspreaders in networks

Two important problems regarding spreading phenomena in complex topologies are the optimal selection of node sets either to minimize or maximize the extent of outbreaks. Both problems are nontrivial when a small fraction of the nodes in the network can be used to achieve the desired goal. The minimization problem is equivalent to a structural optimization. The “superblockers,” i.e., the nodes that should be removed from the network to minimize the size of outbreaks, are those nodes that make connected components as small as possible. “Superspreaders” are instead the nodes such that, if chosen as initiators, they maximize the average size of outbreaks. The identity of superspreaders is expected to depend not just on the topology, but also on the specific dynamics considered. Recently, it has been conjectured that the two optimization problems might be equivalent, in the sense that superblockers act also as superspreaders. In spite of its potential groundbreaking importance, no empirical study has been performed to validate this conjecture. In this paper, we perform an extensive analysis over a large set of real-world networks to test the similarity between sets of superblockers and of superspreaders. We show that the two optimization problems are not equivalent: superblockers do not act as optimal spreaders.

Figure 1

Jaccard similarity $J^{\left(x\right)}$ between sets of superblockers and of superspreaders as a function of the fraction $\rho$ of nodes in the sets. Thin gray lines denote results for each of the 51 real-world networks considered in the analysis. Thick blue lines represent average values of $J^{\left(x\right)}\left(\rho \right)$ across all networks. Average lines are calculated dividing the range of possible values of $\rho$ into 50 equally spaced bins in the logarithm scale, and computing the average value of $J^{\left(x\right)}$ across all networks within each of those bins. The set of top $\rho N$ spreaders was identified using the method by Chen et al. for the critical value of the spreading probability $p=p_c$. Superblockers were ranked using (a) collective influence, (b) Clusella et al., and (c) degree.

Figure 2

(a) Plot of the Jaccard similarity $J^{\left(x\right)}$ [see Eq. (1)] for $\rho ={\rho }_c^{\left(x\right)}$. We consider here collective influence. Each point represents a single network. (b) Same as in panel (a), but for the algorithm by Clusella et al. (c) Ratio $R^{\left(x\right)}/R^{\left(C\right)}$ computed at $\rho ={\rho }_c^{\left(x\right)}$ for the collective influence algorithm (black squares). As a term of comparison, we consider also results of the same quantity calculated with a random placement of the same number of seeds (red circles). (d) Same as in panel (c), but for the algorithm by Clusella et al.

Figure 3

Ratio $R^{\left(x\right)}/R^{\left(C\right)}$ between the spreading power $R^{\left(x\right)}$ of the top $\rho N$ superblockers identified by criterion $x$ and the spreading power $R^{\left(C\right)}$ of the top $\rho N$ superspreaders identified by the algorithm by Chen et al. The ratio $R^{\left(x\right)}/R^{\left(C\right)}$ is plotted as a function of $\rho$. Thin gray lines denote results for each of the 51 real-world networks considered in our analysis. Thick solid blue lines represent instead average values of $R^{\left(x\right)}/R^{\left(C\right)}$ across all networks. The dashed solid purple lines quantify the probability that the actual value of $R^{\left(x\right)}$ is better than the one obtained by placing the same number of seeds at random. Thick solid blue and think dashed purple lines are calculated dividing the range of possible values of $\rho$ into 50 equally spaced bins in the logarithm scale, and computing within each of those bins the average value of $J^{\left(x\right)}$ across all networks (thick solid blue lines) or the frequency of networks for which $R^{\left(x\right)}\le R^{\left(\mathrm{random}\right)}$ (thick dashed purple lines). Superblockers were identified using (a) collective influence, (b) Clusella et al., and (c) degree.

Figure 4

Jaccard similarity index as a function of the fraction $\rho$ of nodes. (a) Comparison between best spreaders for $p=0.5p_c$ and $p=p_c$; (b) comparison between best spreaders for $p=2p_c$ and $p=p_c$; (c) comparison between best spreaders for $p=2p_c$ and $p=0.5p_c$. Thin gray lines denote results for each of the 51 real-world networks considered in the analysis. Thick blue lines represent average values of $J\left(\rho \right)$ across all networks. Average lines are calculated dividing the range of possible values of $\rho$ into 50 equally spaced bins in the logarithm scale, and computing the average value of $J$ across all networks within each of those bins.