Influence Maximization (IM) is the task of identifying a small set of "seed" nodes in a social network that, when activated, trigger the largest possible cascade of information or adoption. While the problem is conceptually simple, it is computationally daunting: finding the optimal seed set is NP-hard, and the spreading process itself is stochastic.
Recent research has shifted from simple "greedy" approximations toward algorithms that are scalable to billions of edges, robust to network changes, and adaptable to different mathematical models of how influence actually spreads.
From Simulations to Global Rankings
The traditional approach to IM relies on "greedy" algorithms that pick nodes one by one, running thousands of Monte Carlo simulations at each step to estimate a node's potential reach. While accurate, this is prohibitively slow for modern social networks.
To break this bottleneck, Kyomin Jung and Wooram Heo developed IRIE, which replaces slow simulations with a message-passing framework. Instead of simulating individual cascades, IRIE uses a global iterative ranking system to estimate influence. This allows it to match the accuracy of greedy methods while running up to 100x faster, scaling to networks with tens of millions of edges.
Similarly, Edith Cohen and colleagues introduced SKIM (Sketch-based Influence Maximization). SKIM works by pre-computing "sketches"—compact summaries of reachability for every node. By operating on these summaries rather than traversing the raw graph repeatedly, SKIM can provide near-exact solutions even on billion-scale networks like Twitter.
The Geometry of Collective Influence
A common intuition is to pick "hubs"—nodes with the highest number of connections. However, research by Flaviano Morone and Hernán A. Makse shows that individual degree is a poor proxy for influence. They proposed the theory of Collective Influence (CI), which maps influencer identification to the physics of "optimal percolation."
The intuition behind CI is that the most influential nodes are those that, if removed, would most effectively dismantle the network's connectivity. By focusing on how nodes are positioned relative to each other rather than just their local connections, CI identifies a minimal set of spreaders that can trigger a massive outbreak or, conversely, block a contagion. This perspective is echoed in the Local Index Rank (LIR) algorithm by Dong Liu, which targets "local leaders" to avoid the redundant overlap that occurs when seeds are too close to one another.
The Model Generalization Gap
A recurring challenge across the field is that an algorithm optimized for one diffusion model may fail on another. Most existing methods are designed for the Independent Cascade (IC) model, where each edge has a fixed probability of spreading influence. However, real-world social dynamics often follow the Linear Threshold (LT) model, where a node only adopts an idea if a certain percentage of its neighbors have already done so.
As noted in IRIE and MATI, the activation logic of these models is fundamentally different. IC is probabilistic and independent, while LT is cumulative and threshold-based. Algorithms like HDD and DHHO are increasingly being tested against these diverse dynamics to ensure that "viral" strategies remain effective regardless of the underlying social mechanics.
Adaptive and Robust Maximization
In the real world, networks are not static, and marketers don't have to pick all their influencers at once. Sharan Vaswani and Laks V. S. Lakshmanan have championed Adaptive Influence Maximization, where seeds are selected in batches. By observing the results of the first batch before picking the second, marketers can drastically reduce the number of seeds needed to hit a target.
Furthermore, because network data is often noisy or evolving, Arkaprava Saha and Xiaokui Xiao developed RIME. RIME is the first framework to handle "Robust Influence Maximization," using multiplicative weight updates to maintain performance even when the network structure or spreading probabilities are uncertain.
Beyond Reach: Profit and Coverage
Finally, the field is moving beyond simply maximizing the number of "active" users. Jing Tang has introduced frameworks for Profit Maximization, which balance the revenue from influence against the costs of acquiring seeds. Other models, like Information Coverage Maximization (ICM), account for "informed" users—those who see a message but don't act on it—providing a more holistic view of a campaign's true impact.