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

Cut-Vertex-Based Influence Maximization Problem in Social Network

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

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.