Fundamental difference between superblockers and superspreaders in networks

Abstract

Two very 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.

arXiv comment6 pages, 4 figures + Supplemental Material. Final published version

References in corpus (18)

• Epidemic processes in complex networks
• The spread of epidemic disease on networks
• Identification of influential spreaders in complex networks
• Influence maximization in complex networks through optimal percolation
• Vital nodes identification in complex networks
• Network dismantling
• Identifying optimal targets of network attack by belief propagation
• Explosive Percolation: Novel critical and supercritical phenomena
• Identify influential spreaders in complex networks, the role of neighborhood
• Fast and simple decycling and dismantling of networks
• Immunization and targeted destruction of networks using explosive percolation
• Collective influence in evolutionary social dilemmas
• Leveraging percolation theory to single out influential spreaders in networks
• Optimizing spread dynamics on graphs by message passing
• Large deviations of cascade processes on graphs
• On the numerical study of percolation and epidemic critical properties in networks
• Effective information spreading based on local information in correlated networks
• Optimizing Spread of Influence in Weighted Social Networks via Partial Incentives

Cited by in corpus (16)

• Robustness and resilience of complex networks
• Fast influencers in complex networks
• Identifying an influential spreader from a single seed in complex networks via a message-passing approach
• Three faces of node importance in network epidemiology: Exact results for small graphs
• The web of federal crimes in Brazil: topology, weaknesses, and control
• Systematic comparison between methods for the detection of influential spreaders in complex networks
• Beyond ranking nodes: Predicting epidemic outbreak sizes by network centralities
• Relevance of temporal cores for epidemic spread in temporal networks
• Infection patterns in simple and complex contagion processes on networks
• Consensus ranking for multi-objective interventions in multiplex networks
• Ranking influential spreaders is an ill-defined problem
• Rapid decay in the relative efficiency of quarantine to halt epidemics in networks
• Understanding the temporal pattern of spreading in heterogeneous networks: Theory of the mean infection time
• Influence maximization in noisy networks
• Group centrality in optimal and suboptimal vaccination for epidemic models in contact networks
• Identifying super-spreaders in information-epidemic coevolving dynamics on multiplex networks