# Influence maximization in complex networks through optimal percolation

arXiv: https://arxiv.org/abs/1506.08326 · HTML: https://mlsanity.com/paper/1506.08326/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2015.

## Built on by (most cited first, 21 of 21)

- [Fairness Amidst Non-IID Graph Data: A Literature Review](https://mlsanity.com/paper/2202.07170/) (2022)
- [Machine learning dismantling and early-warning signals of disintegration in complex systems](https://mlsanity.com/paper/2101.02453/) (2021)
- [Detecting Vulnerable Nodes in Urban Infrastructure Interdependent Network](https://mlsanity.com/paper/2307.09866/) (2023)
- [Price graphs: Utilizing the structural information of financial time series for stock prediction](https://mlsanity.com/paper/2106.02522/) (2021)
- [Scalable Continuous-time Diffusion Framework for Network Inference and Influence Estimation](https://mlsanity.com/paper/2403.02867/) (2024)
- [Cascade-based Randomization for Inferring Causal Effects under Diffusion Interference](https://mlsanity.com/paper/2405.12340/) (2024)
- [Hypernetwork Dismantling via Deep Reinforcement Learning](https://mlsanity.com/paper/2104.14332/) (2021)
- [Transmission Neural Networks: From Virus Spread Models to Neural Networks](https://mlsanity.com/paper/2208.03616/) (2022)
- [A Network Science perspective of Graph Convolutional Networks: A survey](https://mlsanity.com/paper/2301.04824/) (2023)
- [Comprehensive Analysis of Network Robustness Evaluation Based on Convolutional Neural Networks with Spatial Pyramid Pooling](https://mlsanity.com/paper/2308.08012/) (2023)
- [Advancing network resilience theories with symbolized reinforcement learning](https://mlsanity.com/paper/2507.08827/) (2025)
- [Stratified Graph Spectra](https://mlsanity.com/paper/2201.03696/) (2022)
- [Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks](https://mlsanity.com/paper/2201.06877/) (2022)
- [Mastering Percolation-like Games with Deep Learning](https://mlsanity.com/paper/2305.07687/) (2023)
- [Cooperative Network Learning for Large-Scale and Decentralized Graphs](https://mlsanity.com/paper/2311.02117/) (2023)
- [A Quick Framework for Evaluating Worst Robustness of Complex Networks](https://mlsanity.com/paper/2403.00027/) (2024)
- [Learning Network Dismantling Without Handcrafted Inputs](https://mlsanity.com/paper/2508.00706/) (2025)
- [Structure-Aware Cooperative Ensemble Evolutionary Optimization on Combinatorial Problems with Multimodal Large Language Models](https://mlsanity.com/paper/2510.21906/) (2025)
- [PACIFIER: Pacing Opinion Depolarization via a Unified Graph Learning Framework](https://mlsanity.com/paper/2602.23390/) (2026)
- [Network World Models as Environments for Algorithm Design on Complex Systems](https://mlsanity.com/paper/2610.01048/) (2026)
- [Testing Central Structure for Complex Networks](https://mlsanity.com/paper/2610.15659/) (2026)

## Abstract (arXiv)

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 [1]; or, if immunized, would prevent the diffusion of a large scale epidemic [2,3]. Localizing this optimal, i.e. minimal, set of structural nodes, called influencers, is one of the most important problems in network science [4,5]. Despite the vast use of heuristic strategies to identify influential spreaders [6-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 matrix [15] 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. Eventually, 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 [16].