ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (8): 1709-1718.doi: 10.7544/issn1000-1239.2016.20160211

所属专题: 2016数据挖掘前沿技术专题

• 人工智能 • 上一篇    下一篇

社交网络中多渠道影响最大化方法

李小康,张茜,孙昊,孙广中   

  1. (安徽省高性能计算重点实验室(中国科学技术大学计算机学院) 合肥 230026) (国防科学技术大学高性能计算协同创新中心 长沙 410073) (lxk727@mail.ustc.edu.cn)
  • 出版日期: 2016-08-01
  • 基金资助: 
    国家自然科学基金项目(61303047)

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

摘要: 社交网络因为其流行性,近些年得到学术界的广泛关注,社交网络影响最大化是社交网络领域中最流行的问题之一.经典的影响最大化问题是从网络中选取k个初始用户,作为种子用户,让其在网络中传播影响,使得最终受影响的用户数最大化.以往的绝大部分工作针对于单个网络的传播,真实情况下信息是借助多个网络传播的.考虑到信息在多个网络中的传播,提出社交网络中多渠道影响最大化问题,从多个网络中选取k个种子用户,让其同时在多个网络中传播影响,使最终受种子用户影响的用户量最大化.将该问题规约为社交网络影响最大化问题,证明其在独立级联模型下是NP难的.根据问题的特性,提出3种有效的近似解决方法,并在4个真实的社交网络数据中进行实验.实验表明3种的方法能够有效地解决多渠道下的影响力最大化问题.

关键词: 社交网络, 影响最大化, 多渠道, NP难, 近似方法

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

中图分类号: