Paper Info
Title
Influence Maximization on Undirected Graphs: Towards Closing the (1-1/e) Gap
Abstract
We 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 called 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 which 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.
Year
DOI
Venue
2019
10.1145/3328526.3329650
Proceedings of the 2019 ACM Conference on Economics and Computation
Keywords
Field
DocType
independent cascade model, influence maximization, linear threshold model, pcp theorem
Discrete mathematics,Mathematical optimization,Heuristic,Computer science,Upper and lower bounds,Greedy algorithm,Heuristics,Expected value,Cascade,Threshold model,Maximization
Conference
ISBN
Citations 
PageRank 
978-1-4503-6792-9
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Grant Schoenebeck150939.48
Biaoshuai Tao2264.69