Research map / Graph learning / Graph algorithms and clustering
The Irrelevance of Influencers: Information Diffusion with Re-Activation and Immunity Lasts Exponentially Long on Social Network 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.
Theoretical analysis of the expected survival time of the SIRS epidemic process (with re-infection and temporary immunity) on graphs, showing exponential survival on expanders/social network models and polynomial survival on stars.
Problem
How long an information diffusion process with re-infection and short-term immunity (SIRS) survives on networks, and which graph structures make it survive long; prior rigorous results covered only SIS.
Approach
Rigorous analysis of SIRS survival time using potential functions adapted from Korobeinikov and Wake's Lyapunov function, plus a negative-drift theorem; shows a threshold at infection rate ~1/average degree for graphs containing large expander subgraphs, while stars yield only polynomial survival.
Key results
- On expander subgraphs with infection rate λ ≥ c/d (c>1), the expected SIRS survival time is 2^Ω(n); for λ ≤ (1-ε)/d it is O(log n).
- On star graphs with n leaves and constant deimmunization rate, the expected SIRS survival time is O(nϱ ln n) for any infection rate, i.e., polynomial.
- On hyperbolic random graphs with power-law exponent γ∈(2,3), for λ ≥ c·n^((γ-3)/2) the expected survival time is 2^Ω(n^((3-γ)/2)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a star graph as the host network for the SIRS process with constant deimmunization rate | SIRS process · Star graph | expected survival time: E[T] ≤ (ln(n) + 2)(4nϱ + 1) ∈ O(nϱ ln(n)) | Hurt |
| Use an expander subgraph with λ ≥ c/d, for constant c ∈ R>1 | SIRS process · Expander subgraph | expected survival time: E[T] = 2^Ω(n) | Helped |
| Lower the infection rate to λ ≤ (1 − ε)/d on an expander, for constant ε | SIRS process · Expander graph | expected survival time: at most logarithmic in n | Hurt |
| Use λ ≥ c/d, for constant c ∈ R>1, on an Erdős–Rényi graph with (n − 1)p ∈ ω(ln n) | SIRS process · Erdős–Rényi graph Gn,p | expected survival time: E[T] = 2^Ω(n) | Helped |
| Use λ ≤ c/d, for constant c ∈ (0, 1), on an Erdős–Rényi graph with (n − 1)p ∈ ω(ln n) | SIRS process · Erdős–Rényi graph Gn,p | expected survival time: E[T] ∈ O(log n) | Hurt |
| Use a hyperbolic random graph with power-law exponent γ ∈ (2, 3) and λ ≥ cn^(γ−3)/2 | SIRS process · Hyperbolic random graph | expected survival time: E[T] = 2^Ω(n^(3−γ)/2) | Helped |
| Add temporary immunity (the recovered state) to the SIS process on a star | SIRS process · Star graph | expected survival time: SIRS: O(nϱ ln(n)); SIS: super-polynomial | Hurt |
Surprising findings
- On stars, the SIRS process survives only polynomially long for any infection rate, unlike the SIS process where low infection rates already give super-polynomial survival.
- The starting configuration of infected vertices matters little: once above threshold, survival is exponential regardless of which vertices start infected.
Limitations
- Proofs are only sketched in the paper; full details are deferred to an unavailable full version.
- Threshold is tight only for Erdős–Rényi graphs; for other models the result gives a threshold only up to general bounds.
- Results assume constant deimmunization rate; dependence on graph-size-dependent rates is left open.
Experimental setup
Metrics: expected survival time
Baselines: SIS process
Builds on: SIS process analysis (Ganesh, Massoulié, and Towsley 2005) Korobeinikov and Wake Lyapunov function negative-drift theorem (Oliveto and Witt) expander mixing lemma (Chung 1997)
Closest papers by meaning
- A Thorough Comparison Between Independent Cascade and Susceptible-Infected-Recovered Models (AAAI 2025 · similarity 0.87)
- Maximizing Influence Spread through a Dynamic Social Network (Student Abstract) (AAAI 2023 · similarity 0.85)
- Learning Diffusions under Uncertainty (AAAI 2024 · similarity 0.85)
- Motif-oriented influence maximization for viral marketing in large-scale social networks (NeurIPS 2024 · similarity 0.84)
- Enhancing Multi-Scale Diffusion Prediction via Sequential Hypergraphs and Adversarial Learning (AAAI 2024 · similarity 0.83)
- Continuous-Time Graph Representation with Sequential Survival Process (AAAI 2024 · 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.