Abstract
Identifying the most influential individuals can provide invaluable help in developing and deploying effective viral marketing strategies. Previous studies mainly focus on designing efficient algorithms or heuristics to find top-K influential nodes on a given static social network. While, as a matter of fact, real-world social networks keep evolving over time and a recalculation upon the changed network inevitably leads to a long running time, significantly affecting the efficiency. In this paper, we observe from real-world traces that the evolution of social network follows the preferential attachment rule and the influential nodes are mainly selected from high-degree nodes. Such observations shed light on the design of IncInf, an incremental approach that can efficiently locate the top-K influential individuals in evolving social networks based on previous information instead of calculation from scratch. In particular, IncInf quantitatively analyzes the influence spread changes of nodes by localizing the impact of topology evolution to only local regions, and a pruning strategy is further proposed to effectively narrow the search space into nodes experiencing major increases or with high degrees. We carried out extensive experiments on real-world dynamic social networks including Facebook, NetHEPT, and Flickr. Experimental results demonstrate that, compared with the state-of-the-art static heuristic, IncInf achieves as much as 21\(\times \) speedup in execution time while maintaining matching performance in terms of influence spread.
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
Aggarwal, C., Lin, S., Yu, P.: On influential node discovery in dynamic social networks. In: SDM, pp. 636–647. SIAM, California, USA (2012)
ArXiv NetHEPT dataset (2003). http://www.cs.cornell.edu/projects/kddcup/datasets.html. Accessed 18 June 2013
Barabasi, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999)
Chen, W., Lu, W., Zhang, N.: Time-critical influence maximization in social networks with time-delayed diffusion process. In: AAAI, Toronto, Canada (2012)
Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: SIGKDD, pp. 199–208. ACM, Paris, France (2009)
Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large-scale social networks. In: SIGKDD, pp. 1029–1038. USA (2010)
Domingos, P., Richardson, M.: Mining the network value of customers. In: SIGKDD, pp. 57–66. ACM, San Francisco, CA, USA (2001)
Easley, D., Kleinberg, J.: Power laws and rich-get-richer phenomena. In: Networks, Crowds, and Markets: Reasoning about a Highly Connected World (2010)
Gomez-Rodriguez, M., Scholkopf, B.: Influence maximization in continuous time diffusion networks. In: ICML. IEEE, Edinburgh (2012)
Habiba, T.B.W., Berger-Wolf, T.Y.: Maximizing the extent of spread in a dynamic network. DIMACS TR: 2007–20 (2007)
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: SIGKDD, pp. 137–146. ACM, Washington, D.C., USA (2003)
Liu, X., Li, S., Liao, X., Wang, L., Wu, Q.: In-time estimation for influence maximization in large-scale social networks. In: SNS, pp. 1–6, Switzerland (2012)
Liu, X., Li, M., Li, S., Peng, S., Liao, X., Lu, X.: IMGPU: GPU-accelerated influence maximization in large-scale social networks. In: TPDS, pp. 136–145 (2014)
Mislove, A., Koppula, H.S., Gummadi, K.P., Druschel, P., Bhattacharjee, B.: Growth of the Flickr social network. In: SNS, pp. 25–30, USA (2008)
Viswanath, B., Mislove, A., Cha, M., Gummadi, K.P.: On the evolution of user interaction in Facebook. In: SNS, pp. 37–42, Spain (2009)
Acknowledgments
This research was supported by NSFC under grant NO. 61402511. The authors would like to thank the anonymous reviewers for their helpful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Liu, X., Liao, X., Li, S., Lin, B. (2016). Towards Efficient Influence Maximization for Evolving Social Networks. In: Li, F., Shim, K., Zheng, K., Liu, G. (eds) Web Technologies and Applications. APWeb 2016. Lecture Notes in Computer Science(), vol 9931. Springer, Cham. https://doi.org/10.1007/978-3-319-45814-4_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-45814-4_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-45813-7
Online ISBN: 978-3-319-45814-4
eBook Packages: Computer ScienceComputer Science (R0)