Adaptive Influence Maximization in Social Networks

50 concepts28 papers1 proposal

Imagine you are tasked with spreading an important piece of information—such as a public health warning or a targeted marketing campaign—across a massive social network. You have a limited budget to incentivize a handful of initial "seed" users to kickstart a viral cascade.

In traditional static influence maximization, you must select your entire batch of seeds simultaneously before the campaign begins. This open-loop planning forces you to guess which paths the cascade will take. If your early seeds successfully trigger massive organic word-of-mouth propagation, your remaining pre-selected seeds might land in communities that are already saturated, resulting in wasted resources.

Adaptive influence maximization shifts this paradigm from open-loop planning to closed-loop sequential decision-making. Instead of picking all seeds upfront, an adaptive strategy selects seeds one by one or in small batches, observes how the cascade unfolds in real-time, and dynamically optimizes subsequent choices based on the network's current state.

Why Adaptivity Works: Eliminating Redundancy

The fundamental intuition behind adaptive seeding is the reduction of redundancy. In a standard independent cascade model, influence propagates probabilistically. As shown by Huang et al. (2022), static batch selection frequently over-allocates resources to tightly-knit communities because it cannot foresee which specific edges will successfully transmit influence.

By waiting for a seed's influence to propagate before choosing the next, as formalized by Tang et al. (2017), the decision-maker gains a full realization of the active network state. This feedback loop allows the algorithm to identify nodes that have already been reached organically, bypassing them to target unactivated sectors of the network. This mechanism is highly effective across various objectives:

  • Seed Minimization: Tang et al. (2019) demonstrated that updating the residual network graph based on real-world propagation can reduce the number of initial seeds required to hit a specific audience threshold by up to 40%.
  • Profit and Revenue Maximization: When seeding incurs costs, adaptive strategies prevent over-investment in saturated areas, significantly boosting net profits compared to static baselines (Tang et al. 2019; Tang et al. 2024).

The Adaptivity Gap: Quantifying the Value of Information

How much better is an adaptive strategy than a static one? This is measured by the adaptivity gap—the ratio of the expected influence spread of an optimal adaptive policy to that of an optimal static policy.

The value of information depends heavily on what the decision-maker can observe. Peng et al. (2019) analyzed myopic feedback, where the controller can only observe the immediate neighbors of activated seeds. They proved that under myopic feedback, the adaptivity gap is bounded by a factor of 4, meaning static greedy strategies remain reasonably competitive.

However, in more general submodular models or when full cascade feedback is available, Peng et al. (2020) showed that the advantage of adaptive feedback can be infinitely large. To capture these gains without falling into local optimization traps, the authors proposed a hybrid mechanism that follows a static greedy ordering but skips nodes already reached by previous cascades. For practical, large-scale deployments, Huang et al. (2020) introduced batch-sequential frameworks like ADAPTGREEDY, which select seeds in rounds and leverage feedback from previous batches to maintain strong worst-case approximation guarantees.

Bridging Theory and Real-World Volatility

While early theoretical models assumed perfect, instantaneous feedback, real-world networks introduce latency and execution failures. Yuan et al. (2017) addressed this by introducing a partial-feedback model, showing that even limited mid-cascade observations can yield a 20% improvement over zero-feedback methods, allowing for faster decision-making without waiting for cascades to completely terminate.

Furthermore, adaptive seeding provides crucial robustness against human behavioral uncertainty. In public health interventions, such as spreading HIV prevention information among homeless youth, selected "peer leaders" may fail to attend training sessions or engage with the campaign. Wilder et al. (2018) and Wilder et al. (2021) demonstrated through real-world clinical trials that an adaptive, sequential recruitment strategy can dynamically re-optimize subsequent choices when early participants fail to engage, vastly outperforming static planning in volatile environments. Similarly, in the context of fighting misinformation, Hashemi et al. (2022) emphasized that adaptive strategies allow real-time allocation of "truth seeds" to counter fast-spreading fake news as it unfolds.

Learning the Network Dynamics

Most classical influence maximization algorithms assume that the underlying network structure and edge transmission probabilities are perfectly known. In reality, these parameters must be learned from data.

To solve this joint learning-and-optimization challenge, researchers model adaptive influence maximization as an online learning problem. Wei Chen et al. (2013) formulated this via the Combinatorial Multi-Armed Bandit (CMAB) framework, where playing a "super arm" (a set of seeds) allows the agent to simultaneously maximize reward and learn network transmission probabilities.

More recently, researchers have transitioned to modeling social diffusion as a Markov Decision Process (MDP). Huang et al. (2022) developed reinforcement learning algorithms that achieve provably sublinear regret by treating the network state sequentially. By leveraging deep reinforcement learning and graph neural networks, as explored by Liu et al. (2023) and surveyed by Panagopoulos (2021), these models learn to capture complex, non-linear cascade dynamics and scale to networks with millions of nodes, moving past the limitations of static offline models (Bonchi et al. 2016; Panagopoulos et al. 2024).

Key Foundational Work

Scalable Methods for Adaptively Seeding a Social Network (2015) — contributed 2 concept elements to this direction.
Characterizing Strategic Cascades on Networks (2013) — contributed 2 concept elements to this direction.
Scheduling a Cascade with Opposing Influences (2013) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_adaptive_influence_maximization_cf80bb5d,
  title = {adaptive influence maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-influence-maximization/rdr_cf80bb5d85b84aeda7933c02d9ed77f3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_adaptive_influence_maximization_cf80bb5d_v1,
  title = {adaptive influence maximization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-influence-maximization/rdr_cf80bb5d85b84aeda7933c02d9ed77f3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake