Influence maximization in complex networks through optimal percolation

By Flaviano Morone, Hernán A. Makse. Nature, 2015

1,158 citations recorded by the source corpus.

The whole frame of interconnections in complex networks hinges on a specific set of structural nodes, much smaller than the total size, which, if activated, would cause the spread of information to the whole network, or, if immunized, would prevent the diffusion of a large scale epidemic. Localizing this optimal, that is, minimal, set of structural nodes, called influencers, is one of the most important problems in network science. Despite the vast use of heuristic strategies to identify influential spreaders, the problem remains unsolved. Here we map the problem onto optimal percolation in random networks to identify the minimal set of influencers, which arises by minimizing the energy of a many-body system, where the form of the interactions is fixed by the non-backtracking matrix of the network. Big data analyses reveal that the set of optimal influencers is much smaller than the one predicted by previous heuristic centralities. Remarkably, a large number of previously neglected weakly connected nodes emerges among the optimal influencers. These are topologically tagged as low-degree nodes surrounded by hierarchical coronas of hubs, and are uncovered only through the optimal collective interplay of all the influencers in the network. The present theoretical framework may hold a larger degree of universality, being applicable to other hard optimization problems exhibiting a continuous transition from a known phase.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/9855e98fbfcc0aa81e554636bfd1fc74108f317b

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Identifying a set of influential spreaders in complex networks (2016, methodology): “Very recently, Morone and Makse presented an effective method to find a set of critical nodes by mapping the problem onto optimal percolation in random networks 36 .”
Statistical physics of inference: thresholds and algorithms (2015, methodology): “[175] Flaviano Morone and Hernán A Makse.”
Vital nodes identification in complex networks (2016, methodology): “Morone and Makse [188] argued that to find superspreaders in a spreading model or to effectively immunize a network against epidemics can be exactly mapped onto optimal percolation, where the influence maximization problem is to find the minimal set of nodes which, if removed, would break down the n”
Dynamics of information diffusion and its applications on complex networks (2016, background): “Unlike considering the influence of individuals, Morone and Makse [137] mapped the influence maximization problem onto optimal percolation to identify the set of optimal influencers.”
Random walks and diffusion on networks (2016, methodology): “including percolation [259, 260], network centralities [261], community detection [262–264], and efficient “immunization” algorithms [265].”