# Maximizing Social Influence in Almost Linear Time

Preprint · Saeed Seddighin

- Archive id: arxiv:2609.36236
- Published: 2026-09-28
- arXiv: https://arxiv.org/abs/2609.36236
- Source URL: https://arxiv.org/abs/2609.36236
- PDF: https://arxiv.org/pdf/2609.36236
- Provenance: arxiv

## Abstract

Influence maximization is a central algorithmic challenge in network analysis, aiming to identify a set of $k$ seed nodes in a graph with $n$ nodes and $m$ edges that maximizes the expected cascade of information under standard diffusion models. The seminal work of Borgs, Brautbar, Chayes, and Lucier (SODA'14) yielded a fundamental breakthrough\\footnote{The conference version of their paper originally claimed a runtime of $\\tilde O\_ε(n+m)$, but this was subsequently corrected to a runtime of $\\tilde O\_ε((n+m)k)$ in an updated version of the paper that is available online. We validate the necessity of this additional factor $k$ in Section~\\ref{sec:lowerbound} by demonstrating that if their algorithm is restricted to a runtime budget of $\\tilde{O}\_ε(n+m)$, the approximation ratio deteriorates to $O(k^{-1/4})$.} for this problem by achieving an $\\tilde O\_ε((n+m)k)$ time algorithm for approximating the solution within a factor of $1-1/e-ε$. In the years since, numerous efforts have attempted to improve the runtime of this algorithm; however, these works have been successful in only shaving logarithmic factors or improving the dependence on $ε$, leaving the existence of an almost linear-time algorithm as an open question. In this work, we resolve this long-standing open question. We present a novel algorithm that approximates the influence maximization problem within a factor of $1-1/e-ε$ in time $\\tilde{O}\_ε(n+m)$, effectively removing the multiplicative dependence on $k$ from the time complexity.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.