基于割点移除的社交网络重要节点评估与仿真

Ranking and Simulation of Nodes Importance of Social Network based on Articulation Point Removal

在社交网络中找到关键节点具有重要的意义,对于当前传统节点重要性方法没有考虑到对网络结构的破坏,不适用于社交网络等问题,提出了一种改进的,基于割点移除的社交网络重要节点评估方法APRRank。动态的利用Tarjan算法找到并移除社交网络最大联通分量的割点,将这些节点移除的顺序作为社交网络中关键节点排序结果。以4个真实社交网络作为仿真数据,与现有算法进行对比,进行鲁棒性测试。仿真结果表明,使用APRRank得到的重要节点在鲁棒性评价标准上具有更优的结果,可以更快的使整个网络失效,因此APRRank算法可以有效的得到社交网络中的重要节点。

It is of great significance to find key nodes in social networks.The current traditional node importance methods do not take into account the damage to the network structure,and are not suitable for social networks and other issues.An improved social network method APRRank for evaluating important nodes of the network is proposed.based on articulation point removal.The Tarjan algorithm was used to dynamically find and remove the articulation point of the largest connected component of the social network,and the order in which these nodes are removed was used as the ranking result of the key nodes in the social network.Four real social networks were used as experimental simulation data,and compared with existing algorithms,the robustness test was performed.The simulation results show that the important nodes obtained by using APRRank have better results on the robustness evaluation standard,and can make the entire network faster.Therefore,the APRRank algorithm can effectively obtain the important nodes in social networks.