Abnormal link detection algorithm based on semi-local structure

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.

Keywords

• complex network
• graph-based anomaly detection
• abnormal link detection
• robustness