A Thorough Comparison Between Independent Cascade and Susceptible-Infected-Recovered Models

Panfeng Liu, Guoliang Qiu, Biaoshuai Tao, Kuan YangAAAI 2025 · DOI

Introduction

In the study of social network analysis, predicting the spread of information, behaviors, or pathogens is a fundamental challenge. Researchers primarily rely on two stochastic models to simulate these processes: the Independent Cascade (IC) model and the Susceptible-Infected-Recovered (SIR) model. While the IC model has become the industry standard for influence maximization due to its mathematical simplicity, the SIR model is often considered more biologically and socially realistic because it accounts for node recovery—the point at which an individual ceases to spread the contagion.

Historically, these models were often treated as interchangeable or "close enough" in their outcomes. This paper provides the first rigorous theoretical comparison between the two, proving that the subtle differences in their underlying dynamics lead to significant differences in total influence spread. Furthermore, it introduces the first efficient, theoretically-guaranteed algorithms for maximizing influence specifically under SIR dynamics.

Model Dynamics: Independence vs. Correlation

The core distinction between the two models lies in how they handle the "infectious" period of a node.

In the Independent Cascade (IC) model, an infected node has a single, independent opportunity to infect each of its neighbors. If the probability of infection is $p$, the success or failure of infecting neighbor A has no bearing on the success or failure of infecting neighbor B.

In the Susceptible-Infected-Recovered (SIR) model, the process is more complex. An infected node remains contagious for a certain duration (recovery time) before moving to the "recovered" state. During this window, it can attempt to infect its neighbors. This introduces a positive correlation: if a node stays infected for a long time, it is more likely to infect all of its neighbors; if it recovers quickly, it may infect none.

While intuition might suggest that this positive correlation would boost the overall spread, this research proves the opposite: the independence inherent in the IC model actually facilitates a broader propagation effect.

The Dominance Theorem: Why Independence Outperforms Correlation

The authors establish a landmark Dominance Theorem, which states that given the same network and matched parameters, the expected number of infected nodes in the IC model is always greater than or equal to that in the SIR model ($\sigma_{IC}(S) \geq \sigma_{SIR}(S)$).

To prove this, the authors moved away from traditional "forward-looking" simulations and employed a "backward" perspective using Reverse-Reachable (RR) sets. By analyzing who could have infected a random target node rather than who a seed will infect, they demonstrated that the dependencies in the SIR model effectively "harm" the probability of a node being reached. They further show that in specific network structures, the gap between the influence spread of IC and SIR can be arbitrarily large, suggesting that using IC as a proxy for SIR can lead to significant overestimations.

Algorithmic Contributions

Beyond the theoretical comparison, the paper addresses the practical challenge of Influence Maximization (IM)—selecting a set of "seed" nodes to maximize the eventual spread. The authors confirm that the influence function in SIR remains submodular, meaning it exhibits diminishing returns, which allows for the use of greedy-style approximation algorithms.

They provide two major algorithmic contributions:

  1. SIR Influence Maximization: By adapting the Influence Maximization via Martingales (IMM) framework, they developed a $(1 - 1/e - \epsilon)$-approximation algorithm that runs in nearly linear time. This brings the efficiency of SIR optimization on par with the best existing IC algorithms.
  2. Truncated SIR (TSIR): In scenarios where the spread is limited to a specific timeframe ($T$), the authors designed an algorithm utilizing a reverse shortest-path tree (Dijkstra-based) to manage time-dependency while maintaining the same approximation ratio.

Conclusion

This research clarifies the relationship between two pillars of diffusion modeling. By proving that the IC model consistently produces a "weakly larger" spread than the SIR model, the authors provide a critical bound for researchers and practitioners. The introduction of efficient, guaranteed algorithms for SIR and TSIR ensures that when recovery dynamics are a necessary component of a simulation, practitioners no longer need to rely on IC-based approximations that may be mathematically sub-optimal.

Summary updated

BibTeX
@inproceedings{liu2025thorough,
  author = {Panfeng Liu and Guoliang Qiu and Biaoshuai Tao and Kuan Yang},
  title = {{A Thorough Comparison Between Independent Cascade and Susceptible-Infected-Recovered Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i1.32028},
}
Figure