基于反向可达集的影响力最大化算法

doi:10.19678/j.issn.1000-3428.0060210

摘要/Abstract

摘要： 现有影响力最大化算法多数因时间复杂度较高或影响力传播范围有限，不适用于大规模社交网络。基于独立级联模型，结合反向可达集采样提出一种改进的影响力最大化算法D-RIS。在影响力传播函数满足单调性和子模性的前提下，通过自动调试确定反向可达集生成数量的临界值。在Slashdot和Epinions真实数据集上的实验结果表明，D-RIS算法在影响力传播范围上接近CELF算法且优于RIS、HighDegree、LIR和pBmH启发式算法，同时在运行时间上相比CELF算法减少近百倍，具有更好的通用性与稳定性，适用于拓扑结构变化和规模较大的社交网络。

关键词: 社交网络, 影响力最大化, 信息传播模型, 反向可达集, 子模性

Abstract: Most of the existing influence maximization algorithms are not suitable for large-scale social networks due to their high time complexity or limited influence propagation range.Therefore, an improved influence maximization algorithm named D-RIS is proposed based on the Independed Cascade(IC) model and Reverse Reachable(RR) set sampling.Under the premise that the influence propagation function satisfies monotonicity and sub-modularity, the D-RIS algorithm uses the automatic debugging method to determine the threshold of the number of RR sets.Experimental results on Slashdot and Epinions show that the proposed D-RIS algorithm provides a propagation range that is close to the CELF algorithm and higher than the RIS algorithm, HighDegree algorithm, LIR algorithm and pBmH algorithm.At the same time, compared with the CELF algorithm, the running time is reduced by nearly 100 times, providing higher generalization performance, stability, and applicability to topology changes and large-scale social networks.

Key words: social network, influence maximization, information propagation model, Reverse Reachable(RR) set, sub-modularity

中图分类号:

TP301.6

邓心惠, 宾晟, 孙更新. 基于反向可达集的影响力最大化算法[J]. 计算机工程, 2022, 48(1): 60-68,74.

DENG Xinhui, BIN Sheng, SUN Gengxin. Influence Maximization Algorithm Based on Reverse Reachable Set[J]. Computer Engineering, 2022, 48(1): 60-68,74.

http://www.ecice06.com/CN/Y2022/V48/I1/60

图/表 13

20220108121444

20220108121448

20220108121451

20220108121457

20220108121500

20220108121504

20220108121508

20220108121512

20220108121516

20220108121519

20220108121523

20220108121527

20220108121531

参考文献

[1] RICHARDSON M, DOMINGOS P.Mining knowledge-sharing sites for viral marketing[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2002:61-70.
[2] DOMINGOS P, RICHARDSON M.Mining the network value of customers[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2001:57-66.
[3] KEMPE D, KLEINBERG J, TARDOS E.Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2003:137-146.
[4] GOLDENBERG J, LIBAI B, MULLER E.Talk of the network:a complex systems look at the underlying process of word-of-mouth[J].Marketing Letters, 2001, 12(3):211-223.
[5] GOLDENBERG J, LIBAI B, MULLER E.Using complex systems analysis to advance marketing theory development:modeling heterogeneity effects on new product growth through stochastic cellular automata[J].Academy of Marketing Science Review, 2011, 9(3):1-18.
[6] 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:ACM Press, 2007:420-429.
[7] GOYAL A, LU W, LAKSHMANAN L V S.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:ACM Press, 2011:47-48.
[8] CHEN W, WANG Y J, YANG S Y.Efficient influence maximization in social networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2009:199-208.
[9] 李勇, 董思秀, 张强, 等.注意力流网络中节点影响力的层级性研究[J].计算机工程, 2021, 47(8):109-115, 123. LI Y, DONG S X, ZHANG Q, et al.Research on the hierarchy of node influence in attention flow network[J]. Computer Engineering, 2021, 47(8):109-115, 123.(in Chinese)
[10] CHEN W, WANG C, WANG Y J.Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2010:1029-1038.
[11] JUNG K, HEO W, CHEN W.IRIE:scalable and robust influence maximization in social networks[C]//Proceedings of the 12th International Conference on Data Mining.Washington D.C., USA:IEEE Press, 2012:918-923.
[12] WANG Z F, WANG H, LIU Q, et al.Influential nodes selection:a data reconstruction perspective[C]//Proceedings of the 37th International ACM SIGIR Conference on Research & Development in Information Retrieval.New York, USA:ACM Press, 2014:879-882.
[13] LIU D, JING Y, ZHAO J, et al.A fast and efficient algorithm for mining top-k nodes in complex networks[J].Scientific Reports, 2017, 7:43330.
[14] NGUYEN D L, NGUYEN T H, DO T H, et al.Probability-based multi-hop diffusion method for influence maximization in social networks[J].Wireless Personal Communications, 2017, 93(4):903-916.
[15] 谢胜男, 刘勇, 朱敬华, 等.社会网中基于主题的局部影响最大化算法研究[J].计算机科学与探索, 2016, 10(5):646-656. XIE S N, LIU Y, ZHU J H, et al.Research on topic-based local influence maximization algorithm in social network[J].Journal of Frontiers of Computer Science and Technology, 2016, 10(5):646-656.(in Chinese)
[16] 曹玖新, 董丹, 徐顺, 等.一种基于k-核的社会网络影响最大化算法[J].计算机学报, 2015, 38(2):238-248. CAO J X, DONG D, XU S, et al.A k-core based algorithm for influence maximization in social networks[J].Chinese Journal of Computers, 2015, 38(2):238-248.(in Chinese)
[17] BORGS C, BRAUTBAR M, CHAYES J, et al.Maximizing social influence in nearly optimal time[C]//Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms.Philadelphia, USA:Society for Industrial and Applied Mathematics, 2014:946-957.
[18] MAY R M, LLOYD A L.Infection dynamics on scale-free networks[J].Physical Review E:Statistical, Nonlinear, and Soft Matter Physics, 2001, 64(6):066112.
[19] HETHCOTE H W.The mathematics of infectious diseases[J].SIAM Review, 2000, 42(4):599-653.
[20] 李松阳.在线社会网络中节点发现及信息传播机制研究[D].重庆:重庆邮电大学, 2017. LI S Y.Research on node detection and information propagation in online social network[D].Chongqing:Chongqing University of Posts and Telecommunications, 2017.(in Chinese)
[21] 赵月爱, 冯丽萍.社交网络中用户行为对病毒传播的影响因素[J].太原理工大学学报, 2018, 49(4):573-578. ZHAO Y A, FENG L P, Influencing factors of user behavior on virus transmission in social networks[J].Journal of Taiyuan University of Technology, 2018, 49(4):573-578.(in Chinese)
[22] LESKOVEC J, KREVL A.SNAP[EB/OL].[2020-11-10].http://snap.stanford.edu/data.

选择文件类型/文献管理软件名称

选择包含的内容