Efficient Minimum Cost Seed Selection With Theoretical Guarantees for Competitive Influence Maximization

Abstract

Minimum cost seed selection for competitive influence maximization, which selects a set of key users (called seed set) to spread its influence widely into the network at a minimum cost in a competitive social network, is a key algorithmic problem in social influence analysis. Due to its application potential in multiple fields, such as market expansion, election campaigns, and cultural competition, numerous studies have been emerging recently. Despite these efforts, this problem has not been satisfactorily solved since not only finding a (nearly) optimal solution for cost minimization but also evaluating a seed set is computationally complex. Existing works either trade approximation guarantees for practical efficiency using heuristics, or vice versa due to costly Monte Carlo simulations. In this article, a competitive reverse influence estimation-based greedy (CRIEG) algorithm, which provides bounded approximation guarantees, but offers significantly improved empirical efficiency under the competitive independent cascade model, is proposed. The core of the algorithm is a novel estimation method that improves the efficiency by constructing representative sketches to avoid heavy repeated simulations without compromising its performance guarantees. The experimental results on eight real-world networks with up to 1.13 million users show that compared with state-of-the-art algorithms, our algorithm is the most efficient while keeping the best performance, and can be orders of magnitude faster.