Budget-Independent Influence Maximization in Nearly Linear Time
In the authors' words
Influence maximization asks for 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 approximation, but their worst-case running-time bounds grow linearly with the seed budget . We remove this multiplicative dependence: for the independent cascade model, our algorithm succeeds with probability at least in expected time. The result extends to triggering models with explicitly charged local sampling costs. We reserve 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 while preserving the approximation guarantee.
Appeared: Tuesday, September 22. arXiv. Preprint, not yet peer-reviewed.