In the study of social networks, the "influence maximization" problem asks a simple question: which small set of initial users (seeds) should we target to trigger the largest cascade of information, behavior, or product adoption? In their seminal paper, Maximizing the spread of influence through a social network, David Kempe 0001 et al. proved that for standard diffusion models, a simple greedy algorithm provides a provable $(1 - 1/e)$ approximation guarantee. This guarantee relies on the property of submodularity—the mathematical equivalent of diminishing returns—which was further formalized by Elchanan Mossel et al. in On the Submodularity of Influence in Social Networks.
However, this elegant theoretical guarantee hides a massive computational trap: to select each seed, the greedy algorithm must calculate the exact expected spread of candidate sets. The authors proved that calculating this spread is #P-hard, making direct optimization computationally intractable for real-world networks.
Why Exact Estimation is Intractable
To understand why estimating influence is so difficult, consider how a cascade unfolds under a stochastic model like the Independent Cascade Model. Every edge in the network has a certain probability of transmitting information. If a network has $E$ edges, there are $2^E$ possible configurations of "live" (active) and "dead" (inactive) edges. To compute the exact expected reach of a seed set, an algorithm must theoretically calculate the reach across every single one of these exponentially many subgraphs.
As Justin Khim demonstrates in Computing and maximizing influence in linear threshold and triggering models, this combinatorial explosion makes exact calculation impossible for large-scale systems. The same intractability applies when trying to compute the full probability distribution of cascade sizes rather than just the mean, a challenge explored by Rebekka Burkholz et al. in Cascade Size Distributions: Why They Matter and How to Compute Them Efficiently. As Jun Pang notes in Learning graph representations for influence maximization, this #P-hard bottleneck forces a hard choice between theoretical accuracy and practical scalability.
The Monte Carlo Simulation Bottleneck
To bypass this combinatorial explosion, early practical implementations turned to Monte Carlo simulations. Instead of evaluating all $2^E$ subgraphs, they sample a few thousand random graph realizations, simulate the cascade forward from the seed nodes, and average the results.
While conceptually straightforward, this approach introduces a severe computational bottleneck. Suppose we want to find a seed set of size $k$ in a network with $N$ nodes. A standard greedy algorithm evaluates the marginal gain of all remaining nodes over $k$ sequential rounds. If each evaluation requires $M$ Monte Carlo simulations, the algorithm must run $O(k \cdot N \cdot M)$ full-scale cascade simulations. On modern social graphs with millions or billions of edges, this process becomes prohibitively slow.
Furthermore, stochastic simulations suffer from high variance and statistical noise. In Trends Prediction Using Social Diffusion Models, Yaniv Altshuler et al. observe that simulation-based approaches are highly sensitive to noise in real-world social interactions, leading to unreliable forecasts. Worse yet, Suqi Cheng et al. show in StaticGreedy: solving the scalability-accuracy dilemma in influence maximization that the inherent noise in Monte Carlo sampling can actually break the submodularity guarantees of the greedy selection process, causing a severe "scalability-accuracy dilemma."
Bypassing Simulations via Advanced Sampling and Sketching
To break this bottleneck, a major line of research focuses on replacing expensive forward simulations with clever structural sampling techniques. Instead of simulating cascades forward from every potential seed, modern algorithms often trace paths backward from randomly chosen target nodes to find which seeds could have influenced them—a concept known as Reverse Reachable (RR) sets.
Building on this paradigm, Jing Tang et al. developed 2-hop+ Sampling: Efficient and Effective Influence Estimation, which combines analytical shortcuts with optimized sampling to drastically reduce the time needed to estimate cascades on billion-scale graphs. To further optimize this process, Canh V. Pham et al. introduced an importance sampling framework in Importance Sample-Based Approximation Algorithm for Cost-Aware Targeted Viral Marketing. By filtering out low-value data points, their approach reduces the required sample size by over 100x while maintaining strict theoretical guarantees.
Analytical Proxies and Deterministic Models
An alternative way to escape the simulation bottleneck is to develop deterministic mathematical proxies that bound or approximate the spread without any random sampling.
For example, Emmanuel Abbe et al. introduced a structural approach in Nonbacktracking Bounds on the Influence in Independent Cascade Models. By analyzing the network's nonbacktracking matrix, they derive rigorous upper and lower bounds on the total expected spread, bypassing the need for thousands of simulation iterations. Similarly, Maria-Evgenia G. Rossi et al. developed the MATI framework in MATI: An efficient algorithm for influence maximization in social networks, which precalculates influence using local simple paths within a node's immediate neighborhood.
Taking a completely different mathematical route, Salvatore Cuomo et al. reframed the problem entirely in Kernel-based models for influence maximization on graphs based on Gaussian process variance minimization. Instead of modeling stochastic cascades, they treat influence maximization as a deterministic Gaussian Process variance minimization task, using an uncertainty-based selection strategy that operates at a fraction of the computational cost of traditional models.
The Rise of Learning-Based Estimation
The most recent paradigm shift leverages machine learning and deep learning to replace simulations with a single forward model pass. By training neural networks to understand graph topology, these methods can estimate influence or select seeds almost instantaneously.
In Social Influence Maximization for Public Health Campaigns, Qianyi Zhan et al. introduced a framework that embeds social network structures and user attributes into low-dimensional spaces, identifying high-influence nodes without iterative simulation. Similarly, George Panagopoulos et al. proposed the CELFIE algorithm in Influence Maximization Using Influence and Susceptibility Embeddings, which learns specialized influence and susceptibility embeddings directly from historical cascade logs, bypassing traditional diffusion models entirely.
Finally, Philip S. Yu demonstrated the power of inductive learning in Transferring influence: Supervised learning for efficient influence maximization across networks, showing that a supervised learning model can learn the underlying selection logic of expensive greedy algorithms and successfully transfer it to entirely unseen networks with massive speedups.
Key Foundational Work
Maximizing the spread of influence through a social network (2003) — contributed 2 concept elements to this direction.
On the Submodularity of Influence in Social Networks (2006) — contributed 1 concept elements to this direction.