Abstract
Influence maximization is a classic and hot topic in social networks. In this paper, firstly we argue that in online social networks, due to the time sensitivity of popular topics, the assumption in IC or LT model that the influence propagates endlessly in the network, is not applicable. Based on this we consider influence transitivity and limited propagation distance in our new model. Secondly, under our model we propose Semidefinite based algorithms. While most existing algorithms rely on monotony and submodularity to obtain approximation ratio of \(1-1/e\), when no size limitation exists on the number of seeds, our algorithm achieves approximation ratio with \(0.857\), which is a great improvement. Moreover, when only a limited number of nodes can be chosen as seeds, based on computer-assisted proof, we claim our algorithm still keeps approximation ratio higher than \(1-1/e\) if the ratio of the seeds to the total number of nodes resides in a certain range. At last, we evaluate the effectiveness of our algorithms through extensive experiments on real world social networks.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Austrin P, Benabbas S, Georgiouy K (2013) Better balance by being biased: a 0.8776-approximation for max bisection. In: Proceedings of SODA
Chen W, Wang Y, Yang S (2009) Efficient influence maximization in social networks. In: Proceedings of the 15th ACM SIGKDD, Paris, France, pp 199–208
Chen W, Yuan Y, Zhang L (2010a) Scalable influence maximization in social networks under the linear threshold model. In: Proceedings of the 10th IEEE international conference on data mining
Chen W, Wang C, Wang Y (2010b) Scalable influence maximization for prevalent viral marketing in large scale social networks. In: KDD, pp 1029–1038
CVX Research, Inc (2012) CVX: Matlab software for disciplined convex programming. http://cvxr.com/cvx. Accessed September 2012
Domingos P, Richardson M (2001) Mining the network value of customers. In: KDD, pp 57–66
Feige U, Goemans M (1995) Approximating the value of two prover proof systems with applications to MAX 2SAT and MAX DICUT
Feige U, Lovasz L (1992) Two-prover one-round proof systems: their power and their problems. In: Proceedings of the 24th annual ACM symposium on the theory of computing, pp 733–744
Geomans M, Williamson D (1994) 879-Approximation algorithms for MAX CUT and MAX 2SAT. In: Proceedings of the twenty-sixth annual ACM symposium on theory of computing, pp 422–431
He X, Song G, Chen W, Jiang Q (2011) Influence blocking maximization in social networks under the competitive linear threshold model. Technical Report. CoRR, abs/1110.4723
Kempe D, Kleinberg JM, Tardos É (2003) Maximizing the spread of influence through a social network. In: KDD
Lasserre B (2002) An explicit equivalent positive semidefinite program for nonlinear 0-1 programs. SIAM J Optim 12(3):756–769
Richardson M, Domingos P (2002) Mining knowledge-sharing sites for viral marketing. In: KDD, pp 61–70
Wu C, Du D, Xu D (2013) An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems. In: COCOON
Acknowledgments
This work was supported in part by the U.S. National Science Foundation under Grant CNS-0831579, CNS-1016320, and CCF-0829993. It was also supported in part by the National Natural Science Foundation of China (11001242, 11071220).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhu, Y., Wu, W., Bi, Y. et al. Better approximation algorithms for influence maximization in online social networks. J Comb Optim 30, 97–108 (2015). https://doi.org/10.1007/s10878-013-9635-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-013-9635-7