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

Research on Time Optimal Profit Maximization in Social Network

作　　者：刘勇[1] 谢胜男[1] 张巍 朱敬华[1] 王楠[1] 

机构地区：[1]黑龙江大学计算机科学技术学院,哈尔滨150080

出　　处：《计算机科学与探索》2017年第11期1723-1732,共10页Journal of Frontiers of Computer Science and Technology

基　　金：黑龙江省自然科学基金;No.F201430;哈尔滨科技创新人才研究专项资金项目;No.2017RAQXJ094;黑龙江省高校基本科研业务费黑龙江大学专项资金项目;No.HDJCCX-201608~~

摘　　要：影响最大化问题是在社会网上寻找最具影响力的种集。目前的研究工作忽略了影响传播最大化和利润最大化的区别,以及影响范围会随着时间的推移趋于平稳。考虑用户动作日志,提出了基于时间长度的影响力分配模型IVA-T(influence value allocation-T),在此基础上首次提出了时间最优的利润最大化问题(timeoptimal profit maximization,OTPM),并证明了该问题为NP-hard问题。为求解OTPM问题,提出了一个有效的近似算法Profit-Max,并证明了Profit-Max算法的近似比。多个真实数据集上的实验结果表明,该算法可以有效并高效地解决OTPM问题。Influence maximization is the problem of finding a small set of seed nodes in a social network. Existing works ignore the differences between influence spread maximization and profit maximization, and influence spread becomes stable when time passes by. This paper uses real action log and proposes a new propagation model with timespan which is called IVA-T(influence value allocation-T) propagation model, and firstly proposes time optimal profit maximization(OTPM) problem and proves that the problem is NP-hard. In order to solve the problem, this paper designs an effective approximation algorithm Profit-Max and analyzes the approximation ratio. The experimental results on several real datasets show that Profit-Max algorithm can solve OTPM problem effectively and efficiently.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]