Abstract
Influence maximization is one fundamental and important problem to identify a set of most influential individuals to develop effective viral marketing strategies in social network. Most existing studies mainly focus on designing efficient algorithms or heuristics to find Top-K influential individuals for static network. However, when the network is evolving over time, the static algorithms have to be re-executed which will incur tremendous execution time. In this paper, an incremental algorithm DIM is proposed which can efficiently identify the Top-K influential individuals in dynamic social network based on the previous information instead of calculating from scratch. DIM is designed for Linear Threshold Model and it consists of two phases: initial seeding and seeds updating. In order to further reduce the running time, two pruning strategies are designed for the seeds updating phase. We carried out extensive experiments on real dynamic social network and the experimental results demonstrate that our algorithms could achieve good performance in terms of influence spread and significantly outperform those traditional static algorithms with respect to running time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing. In: 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 61–70. ACM, Edmonton (2002)
Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146. ACM, Washington D.C. (2003)
Leskovec, J., Krause, A., Guestrin, C.: Cost-effective outbreak detection in networks. In: 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 420–429. ACM, San Jose (2007)
Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1029–1038. ACM, Washington D.C. (2010)
Kim, J., Kim, S.K., Yu, H.: Scalable and parallelizable processing of influence maximization for large-scale social networks? In: 29th International Conference on Data Engineering, pp. 266–277. IEEE Computer Society, Washington, D.C. (2013)
Yang, Y., Mao, X., Pei, J., et al.: Continuous influence maximization: what discounts should we offer to social network users? In: 26th International Conference on Management of Data, pp. 727–741. ACM, San Francisco (2016)
Chen, W., Wei, L., Zhang, N.: Time-critical influence maximization in social networks with time-delayed diffusion process. Chin. J. Eng. Des. 19(5), 340–344 (2015)
Zhuang, H., Sun, Y., Tang, J., et al.: Influence maximization in dynamic social networks. In: 13th International Conference on Data Mining, pp. 1313–1318. IEEE, Austin (2013)
You, Q., Hu, W., Wu, O.: Influence maximization in human-intervened social networks. In: 24th International Conference on Social Influence Analysis, pp. 9–14. IJCAI, Buenos Aires (2015)
Tong, G., Wu, W., Tang, S., et al.: Adaptive influence maximization in dynamic social networks. IEEE/ACM Trans. Netw. 99, 112–125 (2015)
Liu, X., Liao, X., Li, S., et al.: On the shoulders of giants: incremental influence maximization in evolving social networks. Comput. Sci. (2015)
Goyal, A., Wei, L., Lakshmanan, L.V.S.: SIMPATH: an efficient algorithm for influence maximization under the linear threshold model. In: 11th International Conference on Data Mining, pp. 211–220. IEEE Computer Society, Washington, D.C. (2011)
Lu, Z., Fan, L., Wu, W., et al.: Efficient influence spread estimation for influence maximization under the linear threshold model. Comput. Soc. Netw. 1(1), 1–19 (2014)
Acknowledgment
This work was supported in part by the National Science Foundation of China (61632010, 61100048, 61370222), the Natural Science Foundation of Heilongjiang Province (F2016034), the Education Department of Heilongjiang Province (12531498).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Wang, Y., Zhu, J., Ming, Q. (2017). Incremental Influence Maximization for Dynamic Social Networks. In: Zou, B., Han, Q., Sun, G., Jing, W., Peng, X., Lu, Z. (eds) Data Science. ICPCSEE 2017. Communications in Computer and Information Science, vol 728. Springer, Singapore. https://doi.org/10.1007/978-981-10-6388-6_2
Download citation
DOI: https://doi.org/10.1007/978-981-10-6388-6_2
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-6387-9
Online ISBN: 978-981-10-6388-6
eBook Packages: Computer ScienceComputer Science (R0)