Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (6): 1316-1326.DOI: 10.3778/j.issn.1673-9418.2011018

• Network and Information Security • Previous Articles     Next Articles

Cut-Vertex-Based Influence Maximization Problem in Social Network

YANG Shuxin1,+(), SONG Jianbin1, LIANG Wen2   

  1. 1. School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou, Jiangxi 341000, China
    2. School of Computer Science and Technology, Changchun University of Science and Technology, Changchun 130000, China
  • Received:2020-11-05 Revised:2021-01-11 Online:2022-06-01 Published:2021-01-28
  • About author:YANG Shuxin, born in 1978, Ph.D., associate professor, M.S. supervisor, member of CCF. His research interests include social network analysis, bioinformatics, etc.
    SONG Jianbin, born in 1994, M.S. candidate. His research interests include social network analysis, data mining, etc.
    LIANG Wen, born in 1994, Ph.D. candidate, student member of CCF. His research interests include complex network dynamics, quantum informatics, etc.
  • Supported by:
    National Natural Science Foundation of China(61662028);Scientific Technology Research Foundation of Education Department of Jiangxi Province(GJJ170518);Special Foundation of Postgraduate Innovation of Jiangxi Province(YC2018-S331)

基于割点的社交网络影响最大化问题

杨书新1,+(), 宋建缤1, 梁文2   

  1. 1. 江西理工大学 信息工程学院,江西 赣州 341000
    2. 长春理工大学 计算机科学技术学院,长春 130000
  • 通讯作者: + E-mail: yimuyunlang@sina.com
  • 作者简介:杨书新(1978—),男,江西九江人,博士,副教授,硕士生导师,CCF会员,主要研究方向为社交网络分析、生物信息学等。
    宋建缤(1994—),男,江西吉安人,硕士研究生,主要研究方向为社交网络分析、数据挖 掘等。
    梁文(1994—),男,吉林梅河口人,博士研究生,CCF学生会员,主要研究方向为复杂网络动力学、量子信息学等。
  • 基金资助:
    国家自然科学基金(61662028);江西省教育厅科学技术研究项目基金(GJJ170518);江西省研究生创新专项资金项目(YC2018-S331)

Abstract:

Influence maximization problem is an important issue in social network analysis, the diversity of social network structure has continuously injected vitality into the influence maximization problem, which has been a hot issue in academic circles for nearly two decades. The research on the existing problem of influence maximization mainly focuses on the characteristics of the node, and rarely considers the influence maximization problem from the perspective of social networks connectivity. As a bridge between connected components, the cut-vertex is the core of connectivity. To this end, this paper comprehensively considers the characteristics of node and connectivity of social networks, and proposes a heuristic algorithm based on cut-vertex to solve the influence maximization problem. The algorithm uses degree and connected components to evaluate the influence of nodes, which solves the problem of overlapping influences to a certain extent. Based on the susceptible-infected-recovered model, this paper conducts related experiments on four open source datasets. In the algorithm comparison experiment, the influence maximization algorithm based on the cut-vertex performs well in terms of the running time, influence spread range and seed enrichment, which verifies the practicality and effectiveness of the algorithm.

Key words: social networks, cut-vertex, influence maximization

摘要:

影响最大化问题是社交网络分析中的重要问题,社交网络结构的多样化不断给影响最大化问题注入活力,让它在近二十年里经久不衰,一直是学术界的热门问题。针对已有影响最大化问题的研究,主要关注节点的特征,较少从社交网络的连通性角度来看待影响最大化问题。而割点作为连通分量间的桥梁,是连通性的核心。为此,综合考虑社交网络的节点特征和连通性,提出了基于割点的启发式算法来求解影响最大化问题。该算法用度和连通分量评估节点的影响力,在一定程度上解决了影响力重叠的问题。基于传染病模型,在四个开源数据集上进行了相关实验。在算法对比实验中,基于割点的影响最大化算法在运行时间、影响传播范围和种子富集性指标中表现优异,验证了算法的实用性和有效性。

关键词: 社交网络, 割点, 影响最大化

CLC Number: