王思诚, 孔兵, 包崇明, 周丽华, 王崇云. 基于边际性价比的收益影响力最大化算法[J]. 云南大学学报(自然科学版), 2022, 44(2): 237-245. doi: 10.7540/j.ynu.P00055
引用本文: 王思诚, 孔兵, 包崇明, 周丽华, 王崇云. 基于边际性价比的收益影响力最大化算法[J]. 云南大学学报(自然科学版), 2022, 44(2): 237-245. doi: 10.7540/j.ynu.P00055
WANG Si-cheng, KONG Bing, BAO Chong-ming, ZHOU Li-hua, WANG Chong-yun. Algorithm for benefit influence maximizing based on marginal cost performance[J]. Journal of Yunnan University: Natural Sciences Edition, 2022, 44(2): 237-245. DOI: 10.7540/j.ynu.P00055
Citation: WANG Si-cheng, KONG Bing, BAO Chong-ming, ZHOU Li-hua, WANG Chong-yun. Algorithm for benefit influence maximizing based on marginal cost performance[J]. Journal of Yunnan University: Natural Sciences Edition, 2022, 44(2): 237-245. DOI: 10.7540/j.ynu.P00055

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

Algorithm for benefit influence maximizing based on marginal cost performance

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

     

    Abstract: The traditional influence maximization algorithm ignores the commercial income problem in the process of viral marketing. In real marketing, businesses pay more attention to how to use a fixed budget to select seed sets in a reasonable time to maximize marketing benefits. To solve this problem, an efficient heuristic algorithm is proposed. Firstly, define marginal cost performance to measure the importance of user nodes. Secondly, the node selection result of greedy algorithm is analyzed as a self-consistent sequence, and MCPR (Marginal Cost Performance Ranking) algorithm is proposed, which iteratively approximates an approximate self-consistent sort to pursue the effect of greedy algorithm. Finally, the cost-effective forward allocation strategy is used to estimate the marginal cost-effective of nodes and accelerate the algorithm iteration. A large number of experiments were carried out on three real social networks, and the results show that MCPR can achieve similar results with the greedy algorithm, but the algorithm efficiency is much higher than that of the greedy algorithm.

     

/

返回文章
返回