Influence maximization independent of seed budget improves speed
Budget-Independent Influence Maximization in Nearly Linear Time
Data Structures and AlgorithmsSocial and Information Networks
Summary
Influence maximization helps find a small group of people in a network who can start a trend that reaches the most others. Existing methods get slower as the number of these starter people grows. The authors designed a new method that runs quickly no matter how many starters you pick by cleverly mixing random choices and measured sampling. This allows fast and reliable decisions about spreading information or ideas through networks.
What this means in practice
- •For social media marketers: Select influential users for viral campaigns quickly without slower computations as campaign scale grows.
- •For network security teams: Identify key nodes for efficient information spreading to counter misinformation or malware in large communication networks.
Authors
Zhijie Zhang
Abstract
Influence maximization asks for $k$ seed vertices that maximize the expected spread of a diffusion process in a network. Standard near-optimal-time algorithms based on reverse-reachable sampling achieve a $(1-1/e-\varepsilon)$ approximation, but their worst-case running-time bounds grow linearly with the seed budget $k$. We remove this multiplicative dependence: for the independent cascade model, our algorithm succeeds with probability at least $1-δ$ in $O((m+n)\varepsilon^{-3}\log(2n/δ))$ expected time. The result extends to triggering models with explicitly charged local sampling costs. We reserve $O(\varepsilon k)$ seed positions for cost-weighted random vertices, allowing reverse-reachable searches to stop as soon as they encounter a reserved seed. An independent sample-count estimation phase uses a statistic that also controls the expected search cost. Matching these quantities eliminates the multiplicative dependence on $k$ while preserving the approximation guarantee.