Budget-Independent Influence Maximization in Nearly Linear Time

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-ϵ)$ approximation, but their expected 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-\delta$ in $O((m+n){ϵ}^{-3}\log (2n/\delta ))$ expected time. The result extends to triggering models with explicitly charged local sampling costs. We reserve $O(\epsilon k)$ seed positions for cost-weighted random vertices, allowing reverse-reachable searches to terminate as soon as they encounter a reserved seed. An independent calibration procedure determines the sample count using a statistic that also controls the expected search cost. Matching these quantities eliminates the multiplicative dependence on $k$ while preserving the approximation guarantee.