Leveraging percolation theory to single out influential spreaders in networks

Abstract

Among the consequences of the disordered interaction topology underlying many social, techno- logical and biological systems, a particularly important one is that some nodes, just because of their position in the network, may have a disproportionate effect on dynamical processes mediated by the complex interaction pattern. For example, the early adoption by an opinion leader in a social network may change the fate of a commercial product, or just a few super-spreaders may determine the virality of a meme in social media. Despite many recent efforts, the formulation of an accurate method to optimally identify influential nodes in complex network topologies remains an unsolved challenge. Here, we present the exact solution of the problem for the specific, but highly relevant, case of the Susceptible-Infected-Removed (SIR) model for epidemic spreading at criticality. By exploiting the mapping between bond percolation and the static properties of SIR, we prove that the recently introduced Non-Backtracking centrality is the optimal criterion for the identification of influential spreaders in locally tree-like networks at criticality. By means of simulations on synthetic networks and on a very extensive set of real-world networks, we show that the Non-Backtracking centrality is a highly reliable metric to identify top influential spreaders also in generic graphs not embedded in space, and for noncritical spreading.

18 pages, 11 figure, 3 tables

References in corpus (13)

• Epidemic processes in complex networks
• Influence maximization in complex networks through optimal percolation
• Searching for superspreaders of information in real-world social media
• Localization and centrality in networks
• Percolation on sparse networks
• Ranking the spreading influence in complex networks
• Spreading dynamics in complex networks
• Percolation in real interdependent networks
• Predicting the size and probability of epidemics in a population with heterogeneous infectiousness and susceptibility
• Distinct types of eigenvector localization in networks
• Identifying influential spreaders and efficiently estimating infection numbers in epidemic models: a walk counting approach
• Breaking of the site-bond percolation universality in networks
• Tight lower bound for percolation threshold on a quasi-regular graph

Cited by in corpus (34)

• Fundamentals of spreading processes in single and multilayer complex networks
• Ranking in evolving complex networks
• Leveraging local h-index to identify and rank influential spreaders in networks
• Fast influencers in complex networks
• Efficient collective influence maximization in cascading processes with first-order transitions
• Identifying an influential spreader from a single seed in complex networks via a message-passing approach
• Accurate ranking of influential spreaders in networks based on dynamically asymmetric link-impact
• Hyper-cores promote localization and efficient seeding in higher-order processes
• Fundamental difference between superblockers and superspreaders in networks
• The localization of non-backtracking centrality in networks and its physical consequences
• Systematic comparison between methods for the detection of influential spreaders in complex networks
• Message-passing theory for cooperative epidemics
• Top influencers can be identified universally by combining classical centralities
• Topological structure and the H-index in complex networks
• Influential spreaders for recurrent epidemics on networks
• Influencers identification in complex networks through reaction-diffusion dynamics
• Message-Passing Methods for Complex Contagions
• Targeted influence maximization in complex networks
• The long-term impact of ranking algorithms in growing networks
• Dynamic range maximization in excitable networks
• Network-based ranking in social systems: three challenges
• Node Immunization with Non-backtracking Eigenvalues
• Effect of network clustering on mutually cooperative coinfections
• Influence maximization in noisy networks
• Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix
• Influence of individual nodes for continuous-time Susceptible-Infected-Susceptible dynamics on synthetic and real-world networks
• Localization of nonbacktracking centrality on dense subgraphs of sparse networks
• Identifying influential subpopulations in metapopulation epidemic models using message-passing theory
• How network properties and epidemic parameters influence stochastic SIR dynamics on scale-free random networks
• Maximizing spreading in complex networks with risk in node activation
• Identifying Influential Links for Event Propagation on Twitter: A Network of Networks Approach
• Identifying super-spreaders in information-epidemic coevolving dynamics on multiplex networks
• Complex non-backtracking matrix for directed graphs
• Approximating nonbacktracking centrality and localization phenomena in large networks