摘要
在线社会网络的发展为市场营销提供了新的机遇和挑战.对于广告投放者来说,面临的问题是如何从一个有n个用户的社会网络中,选取k(0<kn)个有影响力的用户,称作种子节点,通过提供报酬、试用品等方式激活他们,让他们为产品做宣传,通过口口相传的方式使尽可能多的用户了解或者购买该产品.这个问题也被称作影响力最大化(Influence Maximization),简称IM问题.IM问题的相关工作往往会默认所选出的k个种子节点均可被激活.而在实际应用中,受各种因素的影响,t(0<tk)个种子节点很有可能无法激活.因此该文的研究问题是如何选取替补节点来代替不能被激活的种子节点,该文称该问题为在影响力最大化中寻找替补种子节点(Substitutes Discovery in Influence Maximization),简称SDIM问题.SDIM问题的提出有利于解决营销中面临的实际问题,帮助广告投放者更顺利地完成营销目标.为此,该文首先给出了SDIM问题的形式化定义,并提出对该问题求解的优化函数.在证明了该问题属于NP难的基础上,说明了基于该文提出的优化函数得到的贪心算法具有精度保证.该文首先利用社会网络的无尺度特性,给出了保留网络中度较大的节点作为初始候选节点集的策略,在此基础上,分别提出了3个求解SDIM问题的算法:(1)找出恰好t个替补节点的全局静态贪心算法GSG;(2)在选择种子节点的同时选取t′(t′t)个替补节点的预选式贪心算法GIA,可防止新选的t个替补节点中仍存在不能被激活的节点;(3)可以改善GSG算法执行时间且不影响精度的全静态算法AS.由于GSG运行时间过长,我们对其进行了CELF优化,在实验中我们称其为GSG-CELF.实验结果表明:根据节点度减少候选节点数量的方法不会影响各算法的效果,却可以有效地减少运行时间;GSG-CELF选出的替补节点的影响力很接近原始种子节点集的效果;GIA具有更好的鲁�
The development of online social networks provides new opportunities and challenges for viral marketing. For a social network with n user-nodes, the advertisers face an important problem, i. e. , how to select k （0〈k〈〈n） influential nodes called seeds, once they become active because of the rewards or free samples, probably the number of the users who know or buy their products is the maximum at the end of diffusion through the word-of-mouth effects. This problem is also called Influence Maximization, or IM for short. Currently in the study of IM problem it is usually assumed that the k selected seeds can be activated. However, maybe there are t（0〈t≤k） seeds that cannot be activated for various reasons in practice. In this situation a new research issue is how to reselect t substitutes to replace the inactive seeds. In this paper, we name this problem as Substitutes Discovery problem in Influence Maximization, or SDIM for short. The problem of SDIM is beneficial to solve the practical problems in marketing, and help advertisers to complete the marketing target more smoothly. For this purpose, we first give a formal definition on SDIM, and propose an optimization function for the problem solving. We prove that SDIM is NP-Hard, and show that our proposed function is of approximation guarantee in developing greedy algorithms for SDIM. In the approach on SDIM, we first filter the nodes according to the scale-free property of social networks and reserve nodes with high degree as candidates. Then we propose three algorithms for SDIM respectively, i. e. , （1） the Global Static Greedy （GSG） algorithm which iust selects t substitutes; （2） the Greedy In Advance （GIA） algorithm which selects t＇（t＇≥t） substitutes in case of there are still inactivated seeds in the substitutes and （3） All Static （AS） algorithm which can improve the efficiency of GSG. As the running time of GSG is unacceptable, we optimize it with the CELF strategy and we call it GSG-CELF in the experiments.
出处
《计算机学报》
EI
CSCD
北大核心
2017年第3期674-686,共13页
Chinese Journal of Computers
基金
国家自然科学基金(61272240
61103151)资助~~
关键词
影响力最大化
社会网络
独立级联模型
信息传播
社会计算
社会媒体
社交网络
influence maximization
social network
independent cascade model
informationdiffusion
social computing
social media
social networks
