ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2016, Vol. 53 ›› Issue (8): 1709-1718.doi: 10.7544/issn1000-1239.2016.20160211

Special Issue: 2016数据挖掘前沿技术专题

Previous Articles     Next Articles

Influence Maximization Across Multi-Channels in Social Network

Li Xiaokang, Zhang Xi, Sun Hao,Sun Guangzhong   

  1. (Anhui Province Key Laboratory of High Performance Computing (School of Computer Science, University of Science and Technology of China), Hefei 230026) (Collaborative Innovation Center of High Performance Computing, National University of Defense Technology, Changsha 410073)
  • Online:2016-08-01

Abstract: Social networks have widely attracted the interests of researchers in recent years because of their popularity. Influence maximization in social network is one of the most popular problems of social network fields. Influence maximization in social network is a problem to pick up k seed users from a social network, target them as seed users and propagate influence via the network, with the goal of maximizing the number of users influenced by seed nodes. The majority of previous work is based on a single channel. However, in real world, information is propagated via multiple channels. This paper takes information spread in multiple networks into consideration, proposes and formulates influence maximization problem across multi-channels in social network. The problem becomes to pick up k seed users from multiple networks and simultaneously propagate influence across multiple networks, maximizing the number of influenced users by seed set. We prove the problem is NP-hard under independent cascade model through reducing it into influence maximization in social network. According to the property of the problem, we put forward three efficient and effective approximation methods for it. Experiments show our proposed methods are effective on four real social networks.

Key words: social network, influence maximization, multi-channels, NP-hard, approximation methods

CLC Number: