arXiv preprint ·
Budget-Independent Influence Maximization in Nearly Linear Time
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Heating in human-HVAC interaction for smart homes: An interdisciplinary overview
Testing, not presuming, adequacy: calibrating generative social simulators against emergent network structure
Optimal and heuristic strategies for evaluating the influence of coordinated behavior in information cascades and retweet networks
Inferring the microscopic mechanisms of opinion dynamics using a kinetic Ising model
GitScholar: A Dataset for Predicting AI Research Impact from GitHub Engagement
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.