Efficient Approximation Algorithms for Adaptive Minimum Cost Seed Selection via mRR-set Updates

Abstract

In a social network G with user costs c(•), the adaptive minimum cost seed selection (AMCS) problem aims to influence at least η users at minimum total cost, where seed users are selected iteratively based on observed diffusion. Prior work shows that truncating user influence by η is necessary for performance guarantees, and proposes multi-root reverse reachable sets (mRR-sets) to estimate truncated influence. However, to maintain estimation accuracy, all mRR-sets must be regenerated in each round to exclude influenced users, which limits scalability. Moreover, existing methods assume uniform user costs, inconsistent with practical scenarios. In this paper, we attempt to solve AMCS under general user costs with high efficiency. To this end, we propose the EMASS framework which achieves an approximation ratio of (ln η+1)2/[(1-1/e)2-ε], where ε is the estimation error of mRR-sets. To generate mRR-sets efficiently, we develop a series of algorithms to update mRR-sets across rounds, which support the generation, root insertion, and cleaning of mRR-sets. In this way, we eliminate the need to regenerate mRR-sets in each round and thus the computation overhead is reduced significantly. Further, we prove that the updated mRR-sets are equal to the regenerated ones. Finally, extensive experiments on real social networks demonstrate that EMASS is faster than state-of-the-art methods by over an order of magnitude, while the influence target η is always reached with the total user cost among the lowest.