李小康　张　茜　孙　昊　孙广中

(安徽省高性能计算重点实验室(中国科学技术大学计算机学院)　合肥　230026)



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

李小康张茜孙昊孙广中

(安徽省高性能计算重点实验室(中国科学技术大学计算机学院)合肥230026)

(国防科学技术大学高性能计算协同创新中心长沙410073)

(lxk727@mail.ustc.edu.cn)

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

社交网络；影响最大化；多渠道；NP难；近似方法

近些年来，随着Facebook和微博等社交网络的流行，越来越多的用户喜欢在社交网络中分享自己的观点和其他信息，使得网络影响力传播的研究成为社交网络分析……