用户互动表示下的影响力最大化算法

doi:10.11772/j.issn.1001-9081.2020081225

摘要/Abstract

摘要： 影响力最大化问题旨在社交网络中选取一组有效的种子用户，使信息通过这些用户能够达到最大范围的传播。传统影响力最大化问题的研究依赖于特定的网络结构和扩散模型，而经过人工处理的简化网络和建立在假设之上的扩散模型在评估用户真实影响力时存在较大局限。为解决该问题，提出一种基于用户互动表示的影响力最大化算法（IMUIR）。首先，根据用户互动痕迹进行随机采样，构造用户上下文对，并经过SkipGram模型训练得到用户的向量表示；然后，利用贪婪策略，根据源用户自身的活跃度和这些用户与其他用户的交互联系度选择最佳种子集。为验证IMUIR的有效性，将其与Random、AC、Kcore和Imfector在2个拥有真实互动信息的社交网络上进行对比实验。结果表明，利用IMUIR选出的种子集质量更高，产生的影响传播范围较广，且在2个数据集上表现稳定。

关键词: 社交网络, 用户互动表示, 影响力最大化, 表示学习, SkipGram模型, 贪婪策略

Abstract: The problem of influence maximization is to select a group of effective seed users in social networks, through which information can reach the largest scope of spread. Traditional researches on influence maximization rely on the specific network structures and diffusion models, however, the manually processed simplified networks and the diffusion models based on assumptions have great limitations on assessing the real influence of users. To solve this problem, an Influence Maximization algorithm based on User Interactive Representation (IMUIR) was proposed. First, the context pairs were constructed through random sampling according to users' interaction traces, and the vector representations of the users were obtained by the SkipGram model training. Then, the greedy strategy was used to select the best seed set according to the activity degrees of the source users and the interaction degrees between these users with other users. To verify the effectiveness of IMUIR, experiments were conducted to compare it with Random, Average Cascade (AC), Kcore and Imfector algorithms on two social networks with real interactive information. The results show that IMUIR selects the seed set with higher quality, produces a wider scope of influence spread, and performs stablely on the two datasets.

Key words: social network, user interactive representation, influence maximization, representation learning, SkipGram model, greedy strategy

中图分类号:

TP301.6

张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.

ZHANG Meng, LI Weihua. Influence maximization algorithm based on user interactive representation[J]. Journal of Computer Applications, 2021, 41(7): 1964-1969.

参考文献

[1] 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:ACM,2001:57-66.
[2] 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:ACM,2003:137-146.
[3] PEROZZI B,AI-RFOU R,SKIENA S. DeepWalk:online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM,2014:701-710.
[4] MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality[C]//Proceedings of the 26th International Conference on Neural Information Processing Systems. Red Hook, NY:Curran Associates Inc.,2013:3111-3119.
[5] GROVER A,LESKOVEC J. node2vec:scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM,2016:855-864.
[6] TANG J,QU M,WANG M,et,al. LINE:large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web. Republic and Canton of Geneva:International World Wide Web Conferences Steering Committee, 2015:1067-1077.
[7] RIBEIRO L F R, SAVERESE P H P, FIGUEIREDO D R. struc2vec:learning node representations from structural identity[C]//Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM,2017:385-394.
[8] 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:ACM,2009:199-208.
[9] 李敏佳, 许国艳, 朱帅, 等. 基于结构洞和度折扣的影响力最大化算法[J]. 计算机应用,2018,38(12):3419-3424.(LI M J, XU G Y,ZHU S,et,al. Influence maximization algorithm based on structure hole and degree discount[J]. Journal of Computer Applications,2018,38(12):3419-3424.)
[10] ALDAWISH R,KURDI H. A modified degree discount heuristic for influence maximization in social networks[J]. Procedia Computer Science,2020,170:311-316.
[11] KIM S,KIM D,OH J,et al. Scalable and parallelizable influence maximization with random walk ranking and rank merge pruning[J]. Information Sciences,2017,415/416:171-189.
[12] 张宪立, 唐建新, 曹来成. 基于反向PageRank的影响力最大化算法[J]. 计算机应用,2020,40(1):96-102.(ZHANG X L, TANG J X,CAO L C. Influence maximization algorithm based on reverse PageRank[J]. Journal of Computer Applications,2020, 40(1):96-102.)
[13] 吴安彪, 袁野, 乔百友, 等. 大规模时序图影响力最大化的算法研究[J]. 计算机学报,2019,42(12):2647-2664.(WU A B, YUAN Y,QIAO B Y,et al. The influence maximization problem based on large scale temporal graph[J]. Chinese Journal of Computers,2019,42(12):2647-2664.)
[14] JIANG Q,SONG G,CONG G,et al. Simulated annealing based influence maximization in social networks[C]//Proceedings of the 25th AAAI Conference on Artificial Intelligence. Palo Alto,CA:AAAI Press,2011:127-132.
[15] 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.
[16] 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.
[17] SANKAR C P,S A,KUMAR K S. Learning from bees:an approach for influence maximization on viral campaigns[J]. PLoS ONE,2016,11(12):No. e0168125.
[18] TANG J,ZHANG R,WANG P,et,al. A discrete shuffled frogleaping algorithm to identify influential nodes for influence maximization in social networks[J]. Knowledge-Based Systems, 2020,187:No. 104833.
[19] PANAGOPOULOS G,MALLIAROS F D,VAZIRGIANNIS M. DiffuGreedy:an influence maximization algorithm based on diffusion cascades[C]//Proceedings of the 7th International Conference on Complex Networks and Their Applications,SCI 812. Cham:Springer,2019:392-404.
[20] WANG F,JIANG W,WANG G,et al. Influence maximization by leveraging the crowdsensing data in information diffusion network[J]. Journal of Network and Computer Applications,2019,136:11-21.
[21] 王正海. 基于网络嵌入的影响力最大化算法研究[D]. 兰州:兰州大学,2019:45-54. (WANG Z H. Study of influence maximization based on network embedding[D]. Lanzhou:Lanzhou University,2019:45-54.)
[22] FENG S, CONG G, KHAN A, et al. Inf2vec:latent representation model for social influence embedding[C]//Proceedings of the IEEE 34th International Conference on Data Engineering. Piscataway:IEEE,2018:941-952.
[23] PANAGOPOULOS G,MALLIAROS F D,VAZIRGIANNIS M. Multi-task learning for influence estimation and maximization[EB/OL].[2021-01-18]. https://arxiv.org/pdf/1904.08804.pdf.
[24] PEI S,MUCHNIK L,ANDRADE J S,et al. Searching for superspreaders of information in real-world social media[J]. Scientific Reports,2014,4:No. 5547.
[25] MIKOLOV T,CHEN K,CORRADO G,et al. Efficient estimation of word representations in vector space[EB/OL].[2020-11-12]. https://arxiv.org/pdf/1301.3781.pdf.