基于边际性价比的收益影响力最大化算法

摘要

传统的影响力最大化算法忽视了病毒式营销过程中的商业收益问题.现实营销中,商家更加关注如何使用一个固定预算,在合理的时间内选出种子集,最大化营销收益.为了解决这个问题,提出一种高效的启发式算法.首先,定义边际性价比衡量用户节点的重要性;其次,分析出贪心算法的节点选取结果为一个自洽序列,提出MCPR(Marginal Cost Performance Ranking)算法,迭代逼近一个近似自洽排序,以追求贪心算法的效果;最后,采用性价比向前分配策略估计节点边际性价比,加速算法迭代.在3个真实社会网络上进行大量实验,结果表明MCPR能够取得与贪心算法近似的结果,但算法效率远高于贪心算法.