确定阀值下社会影响力最大化模型研究  

Studyon Models of SocialInfluence Maximizationwith Deterministic Threshold

作　　者：翁克瑞[1] 刘卫 WENG Ker-rui;LUI Wei(School of Economics & Management, China University of Geosciences, Wuhan, Hubei 430074, China)

机构地区：[1]中国地质大学(武汉)经济管理学院,湖北武汉430074

出　　处：《运筹与管理》2021年第8期169-174,共6页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(71874163)。

摘　　要：确定阀值下社会影响力最大化问题:在社会网络中,如果用户来自邻居的影响力超过固定阀值,则该用户保持激活并影响其他的未激活邻居,当未有新的激活用户时停止扩散,如何选择最初的初始种子使得最终激活的用户数量最大化。该问题广泛存在于新产品扩散、技术推广、信息传播等营销活动。本文分别根据影响力扩散的扩散结果和扩散过程建立了两个整数规划模型。通过计算实验,我们发现基于扩散过程的模型更容易被商业优化软件(Gurobi)求解。同时,实验显示缩减扩散阶段只损失少量的激活数量,却可以节约大量的计算时间。最后,论文在求解模型的基础上,测试了贪婪算法的计算绩效。Social influence maximization with deterministic thresholds requires that the incoming influence of an activated agent should benoless than afixed threshold and active nodes spread influence to their out neighbors until nonew node is activated.The objective is to seek the optimal p seedt maximize the spread of influence.This problem has wide applications in the marketing activities of new products,technology penetration,and information dissemination.We presented two integer programming formulations which are based on diffusion results and diffusion processes respectively.The experiments solved by the Gurobi Optimizer show that the later formulation has a better performance and a smaller number of diffusion steps can save significant time while the solution quality is well preserved.Finally,based on optimal solution of the models,the computing performance of greedy algorithm is tested.

关 键 词：社会网络分析 影响力最大化问题 线性阀值模型 整数规划 

分 类 号：N94[自然科学总论—系统科学] O22[理学—运筹学与控制论]