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