Research map / Learning theory and algorithms / Submodular and game algorithms
A Thorough Comparison Between Independent Cascade and Susceptible-Infected-Recovered Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Compares the independent cascade (IC) and SIR diffusion models, proving IC's expected spread weakly dominates SIR's under matched edge probabilities, and adapts reverse-reachable-set influence maximization to SIR.
Problem
Whether the out-going-edge dependency introduced when mapping the SIR epidemic model onto the IC model (node recovery) changes influence spread and optimal seed selection, and how to do influence maximization under SIR.
Approach
Shows SIR is an outgoing-edge-correlated IC model with matched marginal edge probabilities; proves via a reverse-reachable-set coupling that IC spread weakly dominates SIR spread, constructs instances where the gap is arbitrarily large, and adapts RR-set algorithms (IMM-style) to SIR influence maximization.
Key results
- Proves that for any seed set the expected spread under IC is weakly larger than under SIR when edge marginals match (Theorem on IC dominating SIR).
- Constructs an instance where the ratio sigma_SIR/sigma_IC tends to 0 as b grows (e.g., n_0=b^2), showing the gap can be arbitrarily large.
- Shows IC and SIR can have different optimal seeds on some graphs, motivating SIR-specific InfMax algorithms.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the IC model instead of the SIR model, matching edge infection probabilities | IC and SIR cascades with the same graph and seed set · General directed graphs | expected number of infected nodes | Helped |
| Use the IC model instead of the SIR model, matching edge infection probabilities | IC and SIR cascades with the same graph and seed set · Constructed network instance | expected number of infected nodes | Mixed |
| Use model-specific seed selection instead of transferring the optimal seed choice between IC and SIR | Influence maximization under IC and SIR · Constructed network with two candidate seeds | expected influence spread | Mixed |
Surprising findings
- Matching marginal edge probabilities does not make SIR spread equal to IC; positive correlation among outgoing edges makes SIR strictly weaker in some instances, by an arbitrarily large factor.
Limitations
- Empirical evaluation details are not present in the provided text
- Dominance result requires matched marginal edge probabilities between the two models
Experimental setup
Metrics: expected influence spread
Baselines: IMM greedy Monte-Carlo CELF DegDis VoteRank++
Builds on: independent cascade model live-edge graph formulation IMM
Closest papers by meaning
- Computing and maximizing influence in linear threshold and triggering models (NeurIPS 2016 · similarity 0.88)
- Cascade Size Distributions: Why They Matter and How to Compute Them Efficiently (AAAI 2021 · similarity 0.88)
- Efficient Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback (ICML 2026 · similarity 0.88)
- Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback (AAAI 2021 · similarity 0.87)
- The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network Models (AAAI 2024 · similarity 0.87)
- Nonbacktracking Bounds on the Influence in Independent Cascade Models (NeurIPS 2017 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.