Abstract：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.
翁克瑞, 沈卉, 侯俊东. 确定性社会影响力竞争扩散问题研究[J]. 复杂系统与复杂性科学, 2021, 18(4): 21-29.
WENG Kerui, SHEN Hui, HOU Jundong. On the Deterministic Competitive Diffusion of Social Influence. Complex Systems and Complexity Science, 2021, 18(4): 21-29.
[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.
