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

Algorithm for benefit influence maximizing based on marginal cost performance

作　　者：王思诚 孔兵[1] 包崇明[2] 周丽华[1] 王崇云[3] WANG Si-cheng;KONG Bing;BAO Chong-ming;ZHOU Li-hua;WANG Chong-yun(School of Information Science&Engineering,Yunnan University,Kunming 650500,Yunnan,China;School of Software,Yunnan University,Kunming 650500,Yunnan,China;School of Ecology and Enviromental Science,Yunnan University,Kunming 650500,Yunnan,China)

机构地区：[1]云南大学信息学院,云南昆明650500 [2]云南大学软件学院,云南昆明650500 [3]云南大学生态与环境学院,云南昆明650500

出　　处：《云南大学学报（自然科学版）》2022年第2期237-245,共9页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学基金(61762090,62062066,31760152)。

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

关 键 词：社交网络 病毒式营销 影响力最大化 自洽序列 边际性价比 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]