针对存在于社交网络中多种产品的对抗营销及多种信息竞争传播等场景,考虑竞争与确定性因素,研究确定性社会影响力竞争扩散问题,构建了该问题的整数规划模型,并设计了大规模求解算法。实验结果表明基于扩散信息的边际影响力纠正算法展现了良好的可扩展性与稳定性,求解质量领先度数下降等算法20%以上,求解时间只占贪婪算法、商业软件时间成本极小比例。为企业在竞争扩散中的实际应用提供了可行的优化方案。
In view of the competitive marketing of various products and the competitive dissemination of various information in social networks, the deterministic social influence maximization problem was studied considering the competitive and deterministic factors, and the integer programming model of the problem was constructed, and the large-scale approaching algorithm was designed. The experimental results showed that the marginal influence correction algorithm based on diffusion information showed good scalability and stability, and the reduction of the leading degree of solving quality was more than 20%. The solving time only accounted for a small proportion of the time cost of greedy algorithm and commercial software. It provides a feasible optimization scheme for the practical application of enterprises in the diffusion of competition.
[1]Domingos P, Richardson M. Mining the network value of customers[C].Proceeding of the seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA,2001: 57-66.
[2]Richardson M, Domingos P. Mining knowledge-sharing sites for viral marketing[C].Proceeding of the eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA,2002: 61-70.
[3]Kempe D,Kleinberg J, Tardos E. Maximizing the spread of influence through a social network[C].Proceeding of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, 2003: 137-146.
[4]Leskovec J, Krause A, Guestrin C, et al. Cost-effective outbreak detection in networks[C].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, 2007: 420-429.
[5]Goyal A, Lu W, Lakshmanan L V. Celf++: optimizing the greedy algorithm for influence maximization in social networks[C].Proceedings of the 20th International Conference Companion on World Wide Web. New York, USA,2011: 47-48.
[6]Kimura M, Saito K. Tractable Models for Information Diffusion in Social Networks[M]. Germany: Springer, 2006: 59-271.
[7]Chen W, Yuan Y, Zhang L. Scalable influence maximization in social networks under the linear threshold model[C].2010 IEEE 10th International Conference on Data Mining.Sydney,Australia, 2010: 88-97.
[8]Wang C, Chen W, Wang Y. Scalable influence maximization for independent cascade model in large-scale social networks[J]. Data Mining and Knowledge Discovery, 2012, 25(3): 545-576.
[9]Goyal A, Lu W, Lakshmanan L V. Simpath: an efficient algorithm for influence maximization under the linear threshold model[C].2011 IEEE 11th International Conference on Data Mining.Vancouver, BC, Canada, 2011: 211-220.
[10] Chen W, Wang Y, Yang S. Efficient influence maximization in social networks[C].Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA,2009: 199-208.
[11] Daliri Khomami M M, Rezvanian A, Bagherpour N, et al. Minimum positive influence dominating set and its application in influence maximization: a learning automata approach[J]. Applied Intelligence, 2018, 48(3): 570-593.
[12] Bozorgi A, Haghighi H, Zahedi M S, et al. INCIM: a community-based algorithm for influence maximization problem under the linear threshold model[J]. Information Processing and Management, 2016, 52(6): 1188-1199.
[13] Shang J, Zhou S, Li X, et al. CoFIM: a community-based framework for influence maximization on large-scale networks[J].Knowledge-Based Systems, 2016, 117(FEB): 88-100.
[14] 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(FEB): 119-130.
[15] Gong M, Yan J, Shen B, et al. Influence maximization in social networks based on discrete particle swarm optimization[J]. Information Sciences, 2016, 367-368: 600-614.
[16] Borgs C, Brautbar M, Chayes J, et al. Maximizing social influence in nearly optimal time[C]. Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, USA,2014: 946-957.
[17] Lu W, Chen W, Lakshmanan L V S. From competition to complementarity: comparative influence diffusion and maximization[C].Proceedings of the VLDB Endowment Kohala Coast,Hawaii,2015: 60-71.
[18] Ou H, Chou C, Chen M. Influence maximization for complementary goods: why parties fail to cooperate?[C].Proceeding of the 25th ACM International Conference on Information and Knowledge Management.New York, USA,2016: 1713-1722.
[19] Borodin A. Threshold models for competitive influence in social networks[C].Internet and Network Economics. Berlin, Heidelberg, 2010: 539-550.
[20] Lu W, Bonchi F, Goyal A, et al. The bang for the buck: fair competitive viral marketing from the host perspective[C].Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA, 2013: 928-936.
[21] Bozorgi A, Samet S, Kwisthout J, et al. Community-based influence maximization in social networks under a competitive linear threshold model[J]. Knowledge-Based Systems, 2017, 134: 149-158.
[22] Swaminathan A. An algorithm for influence maximization and target set selection for the deterministic linear threshold model[J]. Current Opinion in Immunology, 2014,12(1):59.
[23] Albert R, Barab A. Statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 47.
