Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (7): 1964-1969.DOI: 10.11772/j.issn.1001-9081.2020081225

Special Issue: 数据科学与技术

• Data science and technology • Previous Articles     Next Articles

Influence maximization algorithm based on user interactive representation

ZHANG Meng, LI Weihua   

  1. School of Information, Yunnan University, Kunming Yunnan 650504, China
  • Received:2020-08-14 Revised:2020-11-06 Online:2021-07-10 Published:2021-07-22


张萌, 李维华   

  1. 云南大学 信息学院, 昆明 650504
  • 通讯作者: 李维华
  • 作者简介:张萌(1996-),女,云南昆明人,硕士研究生,主要研究方向:数据挖掘;李维华(1977-),女,云南昆明人,副教授,博士,主要研究方向:数据挖掘、机器学习。

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

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

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

CLC Number: