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

Studyon Models of SocialInfluence Maximizationwith Deterministic Threshold

确定阀值下社会影响力最大化问题:在社会网络中,如果用户来自邻居的影响力超过固定阀值,则该用户保持激活并影响其他的未激活邻居,当未有新的激活用户时停止扩散,如何选择最初的初始种子使得最终激活的用户数量最大化。该问题广泛存在于新产品扩散、技术推广、信息传播等营销活动。本文分别根据影响力扩散的扩散结果和扩散过程建立了两个整数规划模型。通过计算实验,我们发现基于扩散过程的模型更容易被商业优化软件(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.