在影响力最大化问题中寻找种子节点的替补节点

• 作者: 马军 马茜
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 影响力最大化 社会网络 独立级联模型 信息传播 社会计算 社会媒体 社交网络
• 年，卷（期）: 2017,（3）
• 所属期刊栏目: 社会媒体分析和挖掘
• 页码范围: 674-686
• 页数: 13页
• 分类号: TP399
• 字数: 13137字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2017.00674

摘要

在线社会网络的发展为市场营销提供了新的机遇和挑战.对于广告投放者来说,面临的问题是如何从一个有n个用户的社会网络中,选取k(0<k＜＜n)个有影响力的用户,称作种子节点,通过提供报酬、试用品等方式激活他们,让他们为产品做宣传,通过口口相传的方式使尽可能多的用户了解或者购买该产品.这个问题也被称作影响力最大化(Influence Maximization),简称IM问题.IM问题的相关工作往往会默认所选出的k个种子节点均可被激活.而在实际应用中,受各种因素的影响,t(0<t≤k)个种子节点很有可能无法激活.因此该文的研究问题是如何选取替补节点来代替不能被激活的种子节点,该文称该问题为在影响力最大化中寻找替补种子节点(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具有更好的鲁棒性,同时传播效果也十分接近GSG-CELF;AS与GSG-CELF这类有CELF优化的贪心算法相比,运行时间是GSG-CELF的10%~50%,且传播效果不受影响.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	马军	山东大学计算机科学与技术学院	74	980	15.0	29.0
2	马茜	山东大学计算机科学与技术学院	8	22	3.0	4.0