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

计算机工程与科学

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

董建亮，赵文涛，李方,黄心昊

（国防科技大学计算机学院,湖南长沙 410073）

收稿日期:2016-04-25 修回日期:2016-09-12 出版日期:2017-11-25 发布日期:2017-11-25

A critical links detection method

based on label propagation algorithm

DONG Jian-liang,ZHAO Wen-tao,LI Fang,HUANG Xin-hao

（College of Computer,National University of Defense Technology,Changsha 410073,China）

Received:2016-04-25 Revised:2016-09-12 Online:2017-11-25 Published:2017-11-25

摘要/Abstract

摘要：

随着网络脆弱性逐渐引起人们的关注，对于一个复杂网络，对其关键链路的探测已经越来越重要。根据网络所具有的社团结构特征，立足于网络的社团划分，结合GN算法思想，把标签传播算法引入关键链路探测中。针对原有算法在迭代过程中出现的每个顶点都会得到一个标签而造成的资源浪费和随机迭代出现结果不稳定的问题，采用一次传播标签把结构较紧密的顶点绑定在一起和依据度顺序来更新标签的方法。通过实验验证，该算法能快速、稳定、高效地查找复杂网络中的关键链路。

关键词: 标签传播, 关键链路, 复杂网络, 网络脆弱性, 社团结构

Abstract:

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 basis 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.

Key words: label propagation, critical links, complex network, network vulnerability, community structure

董建亮，赵文涛，李方,黄心昊. 一种基于标签传播算法的关键链路探测方法[J]. 计算机工程与科学.

DONG Jian-liang,ZHAO Wen-tao,LI Fang,HUANG Xin-hao.

A critical links detection method

based on label propagation algorithm

[J]. Computer Engineering & Science.

[1]	皇甫斐斐, 杨阳, 邓晓懿, . 基于节点影响力的理性节点标签传播算法[J]. 计算机工程与科学, 2022, 44(04): 713-722.
[2]	燕云鸿, 钱晓东. 区块链环境下电商消费者网络多子群混合增长模型构建及特性研究[J]. 计算机工程与科学, 2021, 43(12): 2157-2168.
[3]	张丽, 马静. 融合词语统计特征和语义信息的文本分类方法研究[J]. 计算机工程与科学, 2021, 43(07): 1308-1315.
[4]	张士进, 张胜, 田纪彪, 吴志强, 戴维凯. 基于深度编码器的复杂网络社区发现算法 #br# [J]. 计算机工程与科学, 2020, 42(09): 1640-1648.
[5]	潘曙灿, 许青林. 融合特征向量中心性与标签熵的标签传播算法[J]. 计算机工程与科学, 2020, 42(08): 1489-1499.
[6]	徐曼1,2,3，鲁富荣1,2,3，马国帅1,2,3，钱宇华1,2,3. 基于信息传播影响因素的边重要性度量方法[J]. 计算机工程与科学, 2020, 42(01): 55-63.
[7]	杨迪，刘琰，陈静，张伟丽. 基于模体的目标区域网络拓扑划分方法[J]. 计算机工程与科学, 2019, 41(03): 466-478.
[8]	李慧，杨青泉，王慧慧. 一种基于局部扩展优化的重叠社区发现算法[J]. 计算机工程与科学, 2018, 40(12): 2258-2264.
[9]	付丹龙1，朱淑华1，原智峰2，梁倬骞1,2，邓原2. 基于不同子网络级联机制的相依网络鲁棒性研究[J]. 计算机工程与科学, 2018, 40(03): 439-444.
[10]	吕铃，彭雅丽，曾欣怡,杨雨鑫，黄明和. 公共自行车复杂网络可达性指标潜力评价模型[J]. 计算机工程与科学, 2018, 40(01): 175-183.
[11]	伍杰华1,2,沈静1,周蓓1. 改进朴素贝叶斯模型的复杂网络关系预测[J]. 计算机工程与科学, 2017, 39(10): 1825-1831.
[12]	聂祥林1,2,张玉梅1,2,吴晓军1,2,吴霞1. 基于节点依赖度和相似社团融合的社团结构发现算法[J]. 计算机工程与科学, 2017, 39(07): 1273-1280.
[13]	张其林1，董政呈2，赵永标1 . 一种具有核心-边缘结构的无标度网络演化模型[J]. 计算机工程与科学, 2017, 39(03): 500-504.
[14]	曾振华1，毕贵红2，张寿明1，蔡子龙2. 语言竞争社会仿真模型与计算实验[J]. 计算机工程与科学, 2016, 38(12): 2514-2528.
[15]	张红，王小军. 软件体系结构脆性分析与验证[J]. 计算机工程与科学, 2016, 38(11): 2254-2260.