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

doi:10.12005/orms.2021.0262

摘要/Abstract

摘要： 确定阀值下社会影响力最大化问题:在社会网络中,如果用户来自邻居的影响力超过固定阀值,则该用户保持激活并影响其他的未激活邻居,当未有新的激活用户时停止扩散,如何选择最初的初始种子使得最终激活的用户数量最大化。该问题广泛存在于新产品扩散、技术推广、信息传播等营销活动。本文分别根据影响力扩散的扩散结果和扩散过程建立了两个整数规划模型。通过计算实验,我们发现基于扩散过程的模型更容易被商业优化软件(Gurobi)求解。同时,实验显示缩减扩散阶段只损失少量的激活数量,却可以节约大量的计算时间。最后,论文在求解模型的基础上,测试了贪婪算法的计算绩效。

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

Abstract: Social influence maximization with deterministic thresholds requires that the incoming influenceof 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.

Key words: socialnetworkanalysis, influencemaximization, linearthresholdmodel, integerprogramming

中图分类号:

翁克瑞, 刘卫. 确定阀值下社会影响力最大化模型研究[J]. 运筹与管理, 2021, 30(8): 169-174.

WENG Ker-rui, LUI Wei. Studyon Models of SocialInfluence Maximizationwith Deterministic Threshold[J]. Operations Research and Management Science, 2021, 30(8): 169-174.

参考文献

[1] Kempe D, Kleinberg J, Tardos E V. Maximizing the spread of influence through a social network[C]. New York: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, 2003. 137-146.
[2] Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks[C]. New York: Proceed-ings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, 2007. 420-429.
[3] Goyal A, Lu W, Lakshmanan L V S. Celf⁺⁺: optimizing the greedy algorithm for influence maximization in social networks[C]. New York: Proceedings of the 20th interna-tional conference companion on World wide web, 2011. 47-48.
[4] Kimura M, Saito K. Tractable models for information diffusion in social networks[C]. Berlin: European confe-rence on principles of data mining and knowledge dis-covery, 2006. 259-271.
[5] Chen W, Yuan Y, Zhang L. Scalable influence maximi-zation in social networks under the linear threshold mod-el[C]. Sydney: IEEE international conference on data mining, 2010. 88-97.
[6] Wang C, Chen W, Wang Y. Scalable influence maximi-zation for independent cascade model in large-scale social networks[J]. Data Mining and Knowledge Discovery. 2012, 25(3): 545-576.
[7] Goyal A, Lu W, Lakshmanan L V S. Simpath: an efficient algorithm for influence maximization under the linear threshold model[C]. Sydney: IEEE 11th international conference on data mining, 2011. 211-220.
[8] Chen W, Wang Y, Yang S. Efficient influence maximiza-tion in social networks[C]. New York: Proceedings of the 15th ACM SIGKDD international conference on Know-ledge discovery and data mining, 2009. 199-208.
[9] Daliri Khomami M M, Rezvanian A, Bagherpour N, et al. Minimum positive influence dominating set and its ap-plication in influence maximization: a learning automata approach[J]. Applied Intelligence, 2018, 48(3): 570-593.
[10] Bozorgi A, Haghighi H, Zahedi M S, et al. INCIM: A community-based algorithm for influence maximization problem under the linear threshold model[J]. INFOR-MATION PROCESSING＼& MANAGEMENT. 2016, 52(6): 1188-1199.
[11] Shang J, Zhou S, Li X, et al. CoFIM: A community-based framework for influence maximization on large-scale networks[J]. Knowledge-Based Systems. 2017, 117: 88-100.
[12] Cui L, Hu H, Yu S, et al. DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks[J]. JOURNAL OF NETWORK AND COMPUTER APPLICATIONS. 2018, 103: 119-130.
[13] Gong M, Yan J, Shen B, et al. Influence maximization in social networks based on discrete particle swarm optimi-zation[J]. Information Sciences. 2016, 367: 600-614.
[14] Borgs C, Brautbar M, Chayes J, et al. Maximizing social influence in nearly optimal time[C]. Catalunya: Proceed-ings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, Society for Industrial and Applied Mathematics, 2014. 946-957.
[15] Wu W, Du H. On general threshold and general cascade models of social influence[J]. Journal of Combinatorial Optimization. 2018, 35(1): 209-215.
[16] Wu H H, Küçükyavuz S. A two-stage stochastic pro-gramming approach for influence maximization in social networks[J]. Computational Optimization & Applications, 2018, 69(1): 1-33.
[17] Kempe D, Kleinberg J, Tardos E V. Maximizing the spread of influence through a social network[J]. Theory of Computing, 2015, 11(4): 105-147.
[18] Chen W, Lakshmanan L V, Castillo C. Information and influence propagation in social networks[J]. Synthesis Lectures on Data Management, 2013, 5(4): 1-177.
[19] Ackerman E, Ben-Zwi O, Wolfovitz G. Combinatorial model and bounds for target set selection[J]. Theoretical Computer Science, 2010, 411(44): 4017-4022.
[20] Albert R, Barabasi A L. Statistical mechanics of complex networks[J]. Review of Modern Physics, 2001, 74(1): 47.