Abstract: 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.

Key words: social network, profit maximization, action log, timespan

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

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