Generalizing Influence Maximization Across Diffusion Models

135 concepts112 papers1 proposal

When modeling how information, behaviors, or viral memes spread through a social network, researchers rely on mathematical abstractions called diffusion models. The two most prominent paradigms are the Independent Cascade (IC) model and the Linear Threshold (LT) model.

In an IC network, influence spreads like a disease: each active node gets one independent opportunity to trigger its neighbors based on a fixed probability. In an LT network, influence is cumulative: a node only flips to an active state when the combined "weight" of its active neighbors surpasses a specific personal threshold.

For over a decade, the field of Influence Maximization (IM)—finding the optimal $k$ "seed" nodes to maximize the final cascade—has experienced a deep architectural schism. Most state-of-the-art algorithms, fairness frameworks, and learning heuristics are tightly coupled to a single diffusion model (usually IC). When these methods are deployed in environments governed by alternative propagation rules, their theoretical guarantees evaporate, and their empirical performance degrades.

The Core Intuition: Why Generalization Fails

To understand why an algorithm optimized for one diffusion model fails on another, we must look at how they calculate the spread of influence.

Algorithms designed for the IC model frequently exploit the fact that edge activations are independent. This independence allows researchers to use Reverse Influence Sampling (RIS), a technique that samples random subgraphs to find nodes that frequently appear in the "reachability path" of others. As Borgs et al. demonstrated, this approach yields near-optimal approximation guarantees in near-linear time.

However, this mathematical convenience does not translate to the LT model. Because LT dynamics depend on cumulative thresholds rather than isolated coin flips, establishing tight mathematical upper bounds is significantly harder. As Ko et al. noted when developing inductive influence estimators, adapting IC-based sampling methods to LT frameworks presents severe stability challenges because the underlying submodular properties operate under entirely different probabilistic rules.

When an algorithm assumes independent probabilities but encounters cumulative thresholds, it miscalculates node importance. Liu et al. confirmed this empirically, showing that heuristic-based seed selection strategies exhibit massive performance variability when forced to switch between IC and LT dynamics.

The Downstream Cost of Model Dependency

This cross-model generalization gap creates a bottleneck across several specialized subfields of network science:

1. Fairness and Online Learning

Modern IM frameworks do not just maximize reach; they must also ensure information spreads equitably across demographic groups. However, these fairness constraints are often built directly on top of IC assumptions. Wang et al. pointed out that it remains an open question whether fairness-aware online bandit strategies can generalize to LT models. Similarly, adversarial graph embedding techniques designed by Khajehnejad et al. and attribute-aware sampling algorithms by Lin face unresolved stability questions when evaluated outside of standard IC simulations.

2. Interactive and Adaptive Bandits

When network connection strengths are unknown, online algorithms must learn them through trial and error. Wu et al. introduced factorization bandits to learn node-level traits and predict unobserved influence, but their framework is structurally restricted to IC dynamics. When reinforcement learning is introduced to solve adaptive, real-time seeding—such as the framework proposed by Huang et al.—the models often rely on linearized versions of the IC model, leaving their performance on non-linear or threshold-based contagion patterns unverified.

3. Network Inference and Minimization

The dependency problem also affects the inverse problem: reconstructing a network's structure by observing its cascades. Zong et al. and Amin et al. both noted that inference frameworks optimized to map hidden links from IC snapshots lack the flexibility to handle LT dynamics or complex contagions.

Conversely, when the goal is influence minimization (e.g., blocking nodes to stop the spread of misinformation), the mathematical guarantees flip but remain isolated. For instance, Sun et al. provided scalable adversarial attack algorithms with provable bounds strictly constrained to the LT model, while node-blocking frameworks like the one designed by Qin are optimized exclusively for IC.

Bridging the Gap

To move toward model-agnostic network tools, researchers are pursuing two main strategies: mathematically mapping the relationships between different models, and designing algorithms that bypass simulation dependencies entirely.

Providing a rare theoretical bridge, Liu et al. conducted a rigorous comparison between IC and Susceptible-Infected-Recovered (SIR) epidemic models, proving that the IC model consistently produces a weakly larger influence spread when parameters are matched.

On the algorithmic side, the goal is to design frameworks that calculate influence using structural properties common to both paradigms rather than model-specific simulations. For example, Rossi et al. developed MATI (Matrix Influence), an algorithm that precalculates influence by analyzing local simple paths. By avoiding the standard reliance on model-specific Monte Carlo or RIS sampling, their framework successfully scales to large networks under both the Linear Threshold and Independent Cascade models, offering a blueprint for future cross-model generalization.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 118 papers
  2. Version 1 · 2026-10-04 · 145 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_diffusion_model_dependency_5962e41c,
  title = {diffusion model dependency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/diffusion-model-dependency/rdr_5962e41c7d2d4819b9250585125fd312},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_diffusion_model_dependency_5962e41c_v2,
  title = {diffusion model dependency},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/diffusion-model-dependency/rdr_5962e41c7d2d4819b9250585125fd312/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake