不同营销模式中基于时间的影响传播方法研究

来源：计算机科学与探索杂志2016年第3期北京时间：

作者：刘勇，曲思桐，王楠，郭龙江

单位：黑龙江大学 计算机科学技术学院，哈尔滨 150080

摘要：影响最大化问题是在社交网络上找到一组有影响力的用户，使得期望的影响范围最大化。然而，已有的研究工作没有考虑用户之间有效的传播时间区间，而且忽略了营销时间对于选取初始用户的影响。基于真实用户动作日志，确定了用户之间有效的传播时间区间，并提出了一个基于时间的影响力分配模型（influence power allocating model based on time，IPAT）。根据该模型，提出了基于真实时间的影响力最大化问题（influence maximization problem based on time，IMPT）和饥饿营销模式中种集最小化问题（seed set minimization problem in hungry marketing，SMPHM），并证明了这两个问题都是NP-hard问题。为求解IMPT问题和 SMPHM问题，分别提出了有效的近似算法A-IMPT（algorithm for IMPT）和A-SMPHM（algorithm for SMPHM），并证明了算法A-IMPT和A-SMPHM的近似比。多个真实社交网络数据集上的实验验证了算法A-IMPT和A-SMPHM的有效性和高效率。

关键词：社会网,影响传播,传播时间区间,营销时间,饥饿营销