TY - JOUR
T1 - A two-stage stochastic programming approach for influence maximization in social networks
AU - Wu, Hao-Hsiang
AU - Küçükyavuz, Simge
N1 - Publisher Copyright:
© 2017, Springer Science+Business Media, LLC.
PY - 2018/4/1
Y1 - 2018/4/1
N2 - We consider stochastic influence maximization problems arising in social networks. In contrast to existing studies that involve greedy approximation algorithms with a 63% performance guarantee, our work focuses on solving the problem optimally. To this end, we introduce a new class of problems that we refer to as two-stage stochastic submodular optimization models. We propose a delayed constraint generation algorithm to find the optimal solution to this class of problems with a finite number of samples. The influence maximization problems of interest are special cases of this general problem class. We show that the submodularity of the influence function can be exploited to develop strong optimality cuts that are more effective than the standard optimality cuts available in the literature. Finally, we report our computational experiments with large-scale real-world datasets for two fundamental influence maximization problems, independent cascade and linear threshold, and show that our proposed algorithm outperforms the basic greedy algorithm of Kempe et al. (Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining, KDD’03, New York, NY, USA, ACM, pp 137–146, 2003).
AB - We consider stochastic influence maximization problems arising in social networks. In contrast to existing studies that involve greedy approximation algorithms with a 63% performance guarantee, our work focuses on solving the problem optimally. To this end, we introduce a new class of problems that we refer to as two-stage stochastic submodular optimization models. We propose a delayed constraint generation algorithm to find the optimal solution to this class of problems with a finite number of samples. The influence maximization problems of interest are special cases of this general problem class. We show that the submodularity of the influence function can be exploited to develop strong optimality cuts that are more effective than the standard optimality cuts available in the literature. Finally, we report our computational experiments with large-scale real-world datasets for two fundamental influence maximization problems, independent cascade and linear threshold, and show that our proposed algorithm outperforms the basic greedy algorithm of Kempe et al. (Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining, KDD’03, New York, NY, USA, ACM, pp 137–146, 2003).
KW - Independent cascade
KW - Influence maximization
KW - Linear threshold
KW - Social networks
KW - Stochastic programming
KW - Submodularity
UR - http://www.scopus.com/inward/record.url?scp=85031917986&partnerID=8YFLogxK
U2 - 10.1007/s10589-017-9958-x
DO - 10.1007/s10589-017-9958-x
M3 - Article
AN - SCOPUS:85031917986
SN - 0926-6003
VL - 69
SP - 563
EP - 595
JO - Computational Optimization and Applications
JF - Computational Optimization and Applications
IS - 3
ER -