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

随着网络科学领域研究的进展,所涉及的真实网络类型愈加广泛.复杂系统中存在的冗余错误关系,或出于异常目的 刻意发生的行为,如网页错误点击、电信网刺探呼叫等,都对基于网络结构的分析工作造成了重大影响.复杂网络异常连边识别作为图异常检测重要分支,旨在识别网络结构中由于人为制造或数据收集错误所产生的异常连边.现有方法主要从结构...

Abnormal link detection algorithm based on semi-local structure

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.