社会网中时间最优的利润最大化算法研究

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

作者：刘勇，谢胜男，张巍，朱敬华，王楠

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

摘要：影响最大化问题是在社会网上寻找最具影响力的种集。目前的研究工作忽略了影响传播最大化和利润最大化的区别，以及影响范围会随着时间的推移趋于平稳。考虑用户动作日志，提出了基于时间长度的影响力分配模型IVA-T（influence value allocation-T），在此基础上首次提出了时间最优的利润最大化问题（time optimal profit maximization，OTPM），并证明了该问题为NP-hard问题。为求解OTPM问题，提出了一个有效的近似算法Profit-Max，并证明了Profit-Max算法的近似比。多个真实数据集上的实验结果表明，该算法可以有效并高效地解决OTPM问题。

关键词：社会网,利润最大化,动作日志,时间长度