Influence maximization in complex networks through optimal percolation

A rigorous method to determine the most influential superspreaders in complex networks is presented—involving the mapping of the problem onto optimal percolation along with a scalable algorithm for big-data social networks—showing, unexpectedly, that many weak nodes can be powerful influencers. In complex networks, some nodes are more important than others. The most important nodes are those whose elimination induces the network's collapse, and identifying them is crucial in many circumstances, for example, if searching for the most effective way to stop a disease from spreading. But this is a hard task, and most methods available for the purpose are essentially based on trial-and-error. Here, Flaviano Morone and Hernán Makse devise a rigorous method to determine the most influential nodes in random networks by mapping the problem onto optimal percolation and solving the optimization problem with an algorithm that the authors call 'collective influence'. They find that the number of optimal influencers is much smaller, and that low-degree nodes can play a much more important role in the network than previously thought. 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 network1, or, if immunized, would prevent the diffusion of a large scale epidemic2,3. Localizing this optimal, that is, minimal, set of structural nodes, called influencers, is one of the most important problems in network science4,5. Despite the vast use of heuristic strategies to identify influential spreaders6,7,8,9,10,11,12,13,14, 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 matrix15 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 phase16.