Influence maximization algorithm runs in nearly linear time
Maximizing Social Influence in Almost Linear Time
Data Structures and AlgorithmsComputer Science and Game Theory
Summary
Influence maximization is about picking a few key people in a network to spread information widely. Previous methods took longer as more people were chosen, making them slower for big networks. The authors developed a new method that finds almost the same best set very quickly, even for large networks, removing the extra time cost of picking more people. This solves a problem that has been open for years about whether such an efficient method is possible.
What this means in practice
- •For social media platform engineers: Enable faster selection of key users to maximize information spread with efficient algorithms that scale to very large user networks.
- •For marketing data teams: Improve campaign strategies by quickly identifying influential customers in large social networks to enhance advertising effectiveness.
Authors
Saeed Seddighin
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.