Research map / Learning theory and algorithms / Sample complexity
Nonbacktracking Bounds on the Influence in Independent Cascade Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use nonbacktracking walks in the upper-bound computation | Influence estimation on Erdos-Renyi and random 3-regular networks · Erdos-Renyi and random 3-regular networks | upper-bound relative gap | Helped |
| Use nonbacktracking walks in the upper-bound computation | Influence estimation on scale-free networks · Scale-free networks | upper-bound relative gap | No clear effect |
| Use the NB-LB procedure instead of a probabilistic MC lower bound | Influence estimation · Erdos-Renyi, scale-free, and random regular networks when p<0.4 | lower-bound tightness | Helped |
| Avoid backtracking walks in both bounds | Influence estimation on tree networks · Random tree networks | influence-bound tightness | Helped |
| Use NB-UB instead of the spectral upper bound | Influence estimation · 3-regular network at relatively small transmission probabilities | upper-bound tightness | Helped |
| Use NB-UB instead of the probabilistic MC upper bound | Influence estimation · 3-regular network at relatively small transmission probabilities | upper-bound tightness | Helped |
| Use NB-LB instead of probabilistic MC lower bounds with small sample sizes | Influence estimation · Scale-free network | lower-bound tightness | Helped |
| Increase t to compute more exact paths before applying NB-UB (ablation) | tNB-UB · 3-regular network, p in (0.4,0.5) | upper-bound tightness | Helped |
| Increase t to compute exact infection probabilities on a larger initial subnetwork (ablation) | tNB-LB · Scale-free network | lower-bound tightness | Helped |
Closest papers by meaning
- Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback (AAAI 2021 · similarity 0.89)
- Computing and maximizing influence in linear threshold and triggering models (NeurIPS 2016 · similarity 0.87)
- Robust Influence Maximization for Hyperparametric Models (ICML 2019 · similarity 0.87)
- A Thorough Comparison Between Independent Cascade and Susceptible-Infected-Recovered Models (AAAI 2025 · similarity 0.87)
- Hyperparametric Robust and Dynamic Influence Maximization (AAAI 2025 · similarity 0.84)
- DiffIM: Differentiable Influence Minimization with Surrogate Modeling and Continuous Relaxation (AAAI 2025 · similarity 0.83)
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.