一种基于标签传播算法的关键链路探测方法

摘要

随着网络脆弱性逐渐引起人们的关注,对于一个复杂网络,对其关键链路的探测已经越来越重要.根据网络所具有的社团结构特征,立足于网络的社团划分,结合GN算法思想,把标签传播算法引入关键链路探测中.针对原有算法在迭代过程中出现的每个顶点都会得到一个标签而造成的资源浪费和随机迭代出现结果不稳定的问题,采用一次传播标签把结构较紧密的顶点绑定在一起和依据度顺序来更新标签的方法.通过实验验证,该算法能快速、稳定、高效地查找复杂网络中的关键链路.%As network vulnerability gradually attracts people's attention,detection of critical links (critical links problem) is playing an increasingly significant role in complex networks.According to the features of network society structure,and starting from the division of the network community,we are inspired by the Girvan-Newman (GN) algorithm and propose a critical links detection method on the ba sis of label propagation algorithm.Aiming at the resources wasting issue caused by assigning labels for each vertex in the algorithm iterative process,and the problem of instable results caused by random iteration,we bind the vertexes that have closer structure together by propagating labels once,and update the labels according to the sequence.Experiments show that the algorithm can figure out the critical links rapidly,stably and efficiently in a complex network.