网络与信息安全学报 ›› 2022, Vol. 8 ›› Issue (1): 63-72.doi: 10.11959/j.issn.2096-109x.2021040

• 专栏：安全感知与检测方法 • 上一篇    下一篇

基于半局部结构的异常连边识别算法

石灏苒1, 吉立新2, 刘树新2, 王庚润2   

  1. 1 信息工程大学，河南 郑州 450001
    2 国家数字交换系统工程技术研究中心，河南 郑州 450002
  • 修回日期:2021-03-06 出版日期:2022-02-15 发布日期:2022-02-01
  • 作者简介:石灏苒（1997− ），男，重庆人，信息工程大学硕士生，主要研究方向为网络科学、图异常检测
    吉立新（1969− ），男，江苏淮安人，国家数字交换系统工程技术研究中心研究员、博士生导师，主要研究方向为电信网安全、数据挖掘
    刘树新（1987− ），男，山东潍坊人，博士，国家数字交换系统工程技术研究中心助理研究员，主要研究方向为链路预测、通信网络安全
    王庚润（1987− ），男，安徽蒙城人，博士，国家数字交换系统工程技术研究中心助理研究员，主要研究方向为电信网安全、数据处理
  • 基金资助:
    国家自然科学基金(61803384)

Abnormal link detection algorithm based on semi-local structure

Haoran SHI1, Lixin JI2, Shuxin LIU2, Gengrun WANG2   

  1. 1 Information Engineering University, Zhengzhou 450001, China
    2 National Digital Switching System Engineering Technology Research Center, Zhengzhou 450002, China
  • Revised:2021-03-06 Online:2022-02-15 Published:2022-02-01
  • Supported by:
    The National Natural Science Foundation of China(61803384)

在线阅读

16

pdf下载

205

摘要：

随着网络科学领域研究的进展，所涉及的真实网络类型愈加广泛。复杂系统中存在的冗余错误关系，或出于异常目的刻意发生的行为，如网页错误点击、电信网刺探呼叫等，都对基于网络结构的分析工作造成了重大影响。复杂网络异常连边识别作为图异常检测重要分支，旨在识别网络结构中由于人为制造或数据收集错误所产生的异常连边。现有方法主要从结构相似性角度出发，利用节点间连通结构评估连边异常程度，易导致网络结构分解，且检测精度受网络类型影响较大。针对这一问题，提出了一种CNSCL算法，在半局部结构尺度下计算节点重要性，分析不同类型局部结构，在不同结构中根据半局部中心性量化连边对网络整体连通性贡献，结合节点结构相似性差异量化连边可信程度。由于计算过程中需去掉连边以衡量对网络整体连通性影响，存在节点重要性需重复计算问题。因此在计算过程中，所提算法还设计了一种动态更新方法以降低算法计算复杂度，降低了算法计算复杂度，使其可推广应用至大规模网络。在7种具有不同结构紧密程度的真实网络上与现有方法进行对比，实验结果表明，在 AUC 衡量标准下，该方法较基准方法具有更高的检测精度，且在网络稀疏或缺失条件下，仍能保持较为稳定的识别精度。

关键词: 复杂网络, 图异常检测, 异常连边识别, 鲁棒性

Abstract:

With the research in network science, real networks involved are becoming more and more extensive.Redundant error relationships in complex systems, or behaviors that occur deliberately for unusual purposes, such as wrong clicks on webpages, telecommunication network spying calls, have a significant impact on the analysis work based on network structure.As an important branch of graph anomaly detection, anomalous edge recognition in complex networks aims to identify abnormal edges in network structures caused by human fabrication or data collection errors.Existing methods mainly start from the perspective of structural similarity, and use the connected structure between nodes to evaluate the abnormal degree of edge connection, which easily leads to the decomposition of the network structure, and the detection accuracy is greatly affected by the network type.In response to this problem, a CNSCL algorithm was proposed, which calculated the node importance at the semi-local structure scale, analyzed different types of local structures, and quantified the contribution of edges to the overall network connectivity according to the semi-local centrality in different structures, and quantified the reliability of the edge connection by combining with the difference of node structure similarity.Since the connected edges need to be removed in the calculation process to measure the impact on the overall connectivity of the network, there was a problem that the importance of nodes needed to be repeatedly calculated.Therefore, in the calculation process, the proposed algorithm also designs a dynamic update method to reduce the computational complexity of the algorithm, so that it could be applied to large-scale networks.Compared with the existing methods on 7 real networks with different structural tightness, the experimental results show that the method has higher detection accuracy than the benchmark method under the AUC measure, and under the condition of network sparse or missing, It can still maintain a relatively stable recognition accuracy.

Key words: complex network, graph-based anomaly detection, abnormal link detection, robustness

中图分类号: 

No Suggested Reading articles found!