基于动作日志时间最优的利润最大化

摘要

影响最大化问题是在社会网上找一组具有重要影响力的用户,通过激活该组用户,期望被影响到的用户数量达到最大.然而,已有研究工作往往忽视了影响传播最大化和利润最大化的区别,以及被影响的用户总数随着时间的推移逐渐趋于平稳.本文基于用户动作日志,提出了一个基于时间长度的影响力分配模型IVA-T,根据该模型首次提出了时间最优的利润最大化问题(OTPM),并证明了该问题是NP-hard问题.为求解OTPM问题,提出了一个有效的近似算法Profit-Max,并证明了Profit-Max算法的近似比.在多个真实数据集上的实验结果表明:Profit-Max算法能有效并高效求解OTPM问题.