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

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on cybernetics 2021-12, Vol.51 (12), p.6091-6104
Main Authors: Hong, Wenjing, Qian, Chao, Tang, Ke
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Approximation algorithms
Competition
Competitive influence maximization (CIM)
Computational modeling
Computer simulation
Efficiency
Elections
Empirical analysis
Estimation
Greedy algorithms
Mathematical analysis
Maximization
Minimum cost
minimum cost seed selection
Models, Theoretical
Monte Carlo methods
Optimization
reverse influence sampling (RIS)
Sketches
Social networking (online)
Social networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2168-2267
2168-2275
DOI:10.1109/TCYB.2020.2966593