Paper Info
Title
Influence Maximization on Undirected Graphs: Toward Closing the (1-1/e) Gap
Abstract
AbstractWe study the influence maximization problem in undirected networks, specifically focusing on the independent cascade and linear threshold models. We prove APX-hardness (NP-hardness of approximation within factor (1-τ) for some constant τ > 0) for both models, which improves the previous NP-hardness lower bound for the linear threshold model. No previous hardness result was known for the independent cascade model.As part of the hardness proof, we show some natural properties of these cascades on undirected graphs. For example, we show that the expected number of infections of a seed set S is upper bounded by the size of the edge cut of S in the linear threshold model and a special case of the independent cascade model, the weighted independent cascade model.Motivated by our upper bounds, we present a suite of highly scalable local greedy heuristics for the influence maximization problem on both the linear threshold model and the weighted independent cascade model on undirected graphs that, in practice, find seed sets that on average obtain 97.52% of the performance of the much slower greedy algorithm for the linear threshold model and 97.39% of the performance of the greedy algorithm for the weighted independent cascade model. Our heuristics also outperform other popular local heuristics, such as the degree discount heuristic by Chen et al. [7].
Year
DOI
Venue
2020
10.1145/3417748
ACM Transactions on Economics and Computation
Keywords
DocType
Volume
Influence maximization, independent cascade model, linear threshold model, local greedy heuristic
Journal
8
Issue
ISSN
Citations 
4
2167-8375
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Grant Schoenebeck150939.48
Biaoshuai Tao2264.69