计算机科学与探索

作者：杨书新, 宋建缤, 梁文

单位：1. 江西理工大学 信息工程学院,江西 赣州 341000；2. 长春理工大学 计算机科学技术学院,长春 130000

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

基金：国家自然科学基金(61662028);江西省教育厅科学技术研究项目基金(GJJ170518);江西省研究生创新专项资金项目(YC2018-S331)

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

来源：2022年第6期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2022年第6期