影响最大化问题中基于K-truss的投票改进算法

doi:10.19678/j.issn.1000-3428.0063033

摘要/Abstract

摘要： 在社交网络的影响最大化（IM）问题中，近似算法通过大量的Monte-Carlo模拟计算节点集的影响范围，导致时间复杂度提高，而多数启发式算法在具有不同拓扑结构的图上存在稳定性较差的问题。提出基于K-truss的改进投票算法TrussVote。在投票阶段，通过引入K-truss的相关理论及算法定义节点的有效投票能力，用于表示节点对其不同邻居的投票倾向，同时在计算得票分数时考虑边的传播概率，提高解决IM问题的效率。在每轮投票结束后，将得票分数最高的节点选为种子节点。在更新阶段，结合节点间的相似性指标定义衰减因子，以有效区分邻居节点投票能力的弱化程度。此外，基于IC模型下的原始传播结果，提出传播差异作为传播范围的等价分析指标。在不同规模真实网络数据集上的实验结果表明，相比RNR、VoteRank++等算法，该算法不仅能有效降低时间复杂度，而且可在最短的时间内感染更多的节点，具有广泛的影响范围。

关键词: 社交网络, 影响最大化, 投票算法, K-truss分解, IC模型, SIR模型

Abstract: In the Influence Maximization(IM) problem of social networks, approximation algorithms are used to calculate the impact range of node sets via a significant amount of Monte-Carlo simulations, thus resulting in an increase in time complexity.Most heuristic algorithms exhibit unsatisfactory stability on graphs with different topological structures.This study proposes an improved voting algorithm, TrussVote, which is based on K-truss.In the voting stage, the effective voting ability of a node is defined by introducing the relevant theory and algorithm of K-truss, which is used to represent the voting tendency of a node to its different neighbors.Additionally, the propagation probability of edges is considered when calculating the voting score to improve the efficiency of the algorithm in solving IM problems.After each round of voting, the node with the highest voting score is selected as the seed node.In the update phase, the attenuation factor is defined based on the similarity index between nodes to effectively distinguish the weakening degree of neighboring nodes' voting ability.In addition, based on the original propagation results under the IC model, the Diffusion Difference(DD) is proposed as an analysis index equivalent to the propagation range.Experimental results on real network datasets of different scales show that compared with RNR, VoteRank++, and other algorithms, the proposed algorithm not only effectively reduces the time complexity, but also infects more nodes in the shortest duration and has a wider range of influence.

Key words: social network, Influence Maximization(IM), voting algorithm, K-truss decomposition, IC model, SIR model

中图分类号:

TP391

孙飞翔, 陈卫东, 林天森. 影响最大化问题中基于K-truss的投票改进算法[J]. 计算机工程, 2022, 48(11): 291-298.

SUN Feixiang, CHEN Weidong, LIN Tiansen. Improved Voting Algorithm Based on K-truss for Influence Maximization Problem[J]. Computer Engineering, 2022, 48(11): 291-298.

https://www.ecice06.com/CN/Y2022/V48/I11/291

图/表 8

20230221181904

20230221181907

20230221181910

20230221181913

20230221181919

20230221181923

20230221181926

20230221181930

参考文献

[1] WU J, HU B, ZHANG Y.Maximizing the performance of advertisements diffusion:a simulation study of the dynamics of viral advertising in social networks[J].Simulation, 2013, 89(8):921-934.
[2] WU P, PAN L.Scalable influence blocking maximization in social networks under competitive independent cascade models[J].Computer Networks, 2017, 123:38-50.
[3] FAN C J, ZENG L, SUN Y Z, et al.Finding key players in complex networks through deep reinforcement learning[J].Nature Machine Intelligence, 2020, 2(6):317-324.
[4] KEMPE D, KLEINBERG J, TARDOS É.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.
[5] 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.
[6] 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.
[7] ZHANG J X, CHEN D B, DONG Q, et al.Identifying a set of influential spreaders in complex networks[J].Scientific Reports, 2016, 6:27823.
[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] SHEIKHAHMADI A, NEMATBAKHSH M A, SHOKROLLAHI A.Improving detection of influential nodes in complex networks[J].Physica A:Statistical Mechanics and Its Applications, 2015, 436:833-845.
[10] WANG X J, SU Y Y, ZHAO C L, et al.Effective identification of multiple influential spreaders by degree punishment[J].Physica A:Statistical Mechanics and Its Applications, 2016, 461:238-247.
[11] 曹玖新, 董丹, 徐顺, 等.一种基于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)
[12] SHEIKHAHMADI A, NEMATBAKHSH M A.Identification of multi-spreader users in social networks for viral marketing[J].Journal of Information Science, 2017, 43(3):412-423.
[13] ZHAO Y X, LI S H, JIN F.Identification of influential nodes in social networks with community structure based on label propagation[J].Neurocomputing, 2016, 210:34-44.
[14] KUMAR S, SINGHLA L, JINDAL K, et al.IM-ELPR:influence maximization in social networks using label propagation based community structure[J].Applied Intelligence, 2021, 51(11):7647-7665.
[15] RUI X B, MENG F R, WANG Z X, et al.A reversed node ranking approach for influence maximization in social networks[J].Applied Intelligence, 2019, 49(7):2684-2698.
[16] HE Q, WANG X W, LEI Z C, et al.TIFIM:a two-stage iterative framework for influence maximization in social networks[J].Applied Mathematics and Computation, 2019, 354:338-352.
[17] SUN H L, CHEN D B, HE J L, et al.A voting approach to uncover multiple influential spreaders on weighted networks[J].Physica A:Statistical Mechanics and Its Applications, 2019, 519:303-312.
[18] KUMAR S, PANDA B S.Identifying influential nodes in social networks:neighborhood coreness based voting approach[J].Physica A:Statistical Mechanics and Its Applications, 2020, 553:1-12.
[19] GUO C, YANG L, CHEN X, et al.Influential nodes identification in complex networks via information entropy[J].Entropy, 2020, 22(2):1-9.
[20] LIU P F, LI L J, FANG S Y, et al.Identifying influential nodes in social networks:a voting approach[J].Chaos, Solitons & Fractals, 2021, 152:1-9.
[21] KITSAK M, GALLOS L K, HAVLIN S, et al.Identification of influential spreaders in complex networks[J].Nature Physics, 2010, 6(11):888-893.
[22] MALLIAROS F D, ROSSI M E G, VAZIRGIANNIS M.Locating influential nodes in complex networks[EB/OL].[2021-09-20].https://www.nature.com/articles/srep19307.pdf.
[23] MALLIAROS F D, GIATSIDIS C, PAPADOPOULOS A N, et al.The core decomposition of networks:theory, algorithms and applications[J].The VLDB Journal, 2020, 29(1):61-92.
[24] ZHOU T, LÜ L, ZHANG Y C.Predicting missing links via local information[J].The European Physical Journal B, 2009, 71(4):623-630.
[25] RADICCHI F, CASTELLANO C.Fundamental difference between superblockers and superspreaders in networks[EB/OL].[2021-09-20].https://arxiv.org/pdf/1610.02908.pdf.
[26] PASTOR-SATORRAS R, VESPIGNANI A.Epidemic dynamics and endemic states in complex networks[J].Physical Review E, 2001, 63(6):1-10.

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

选择包含的内容