Research On Anomaly Detection Method In Complex Network Background

Network anomaly detection is an important research content in the field of signal processing,which is widely used in many applications such as communication network,computer network,social network and biological network.In general,a large amount of data in a network is composed of network nodes and connections between nodes,known as " relationship " data.This "relationship" data tends to be random,usually expressed as a random graph.The random graph models that represent the network connection relationship have Erd?s-Rényi(ER)model,statistical block model and chang-lu(CL)model,etc.Among them,ER random graph is a special graph model with the same probability of connection between the endpoints,and the graph structure is relatively simple.The statistical block model and the CL model random graph have the non-uniform characteristics,and the connection probabilities between different blocks and even arbitrary endpoints are often different,which have more complex graph structure characteristics.When there is an abnormal situation such as malicious traffic or threatening behavior in the network,the connection between nodes parts of the network is extremely frequent,which is shown in the graph model as the statistical property of the edge probability increase corresponding to the subgraph of the abnormal endpoint.The purpose of this paper is to determine whether the network is abnormal according to the observed "relationship" data or observed graph in the background graph(network normal graph model)of the statistical block model and CL random graph.Because the network anomaly is reflected in the relationship data between some nodes,the network anomaly detection under the graph model is also called abnormal subgraph detection.Considering that the graph data is in the form of offline data or real-time data flow,abnormal subgraph detection can be further divided into offline abnormal subgraph detection and online change detection.Offline abnormal subgraph detection is a typical binary detection problem,its purpose is to determine whether the graph is a normal background graph pattern or part of the endpoint corresponding to the subgraph occurrence abnormal situation according to the obtained observed graph.The existing typical anomaly subgraph detection algorithms mainly include the anomaly detection methods based on matrix characteristic spectrum and the likelihood ratio anomaly detection methods.The likelihood ratio method can provide high detection performance,but it is generally assumed that the background graph is the ER random graph model,which does not apply to more complex statistical block model or CL random graph model.The anomaly detection methods based on matrix characteristic spectrum can be applied to statistical block model or CL stochastic graph model.Compared with the likelihood ratio methods,the anomaly detection methods based on matrix characteristic spectrum have enhanced the practicability of the anomaly detection algorithm,but the likelihood ratio methods are better in detecting performance.Therefore,it is necessary and meaningful to explore the anomaly detection algorithm based on the characteristic spectrum of high detection performance.Online subgraph detection(changepoint detection)is a dynamic anomaly detection problem,it is based on the observed graph data flow to determine when the graph sequence is changed from normal graph mode to abnormal state,which is to estimate the time of network anomaly.It is worth pointing out that when the abnormal time is infinite,it is considered that the observed sequence data flow is normal mode(or null hypothesis).In essence,the changepoint detection requires a binary decision on the corresponding observed graph at each observed moment to determine whether there is an abnormal occurrence.Therefore,changepoint detection can be regarded as a series of binary detection problems.Since the sequence of graphs are collected online,the indexs measuring the detection performance of the changepoint are not only the estimation precision,but also the real-time performance of the algorithm or the computational complexity of the algorithm.At present,the changepoint detection methods of abnormal subgraph mainly have the methods of changepoint detection based on graph feature and the likelihood ratio detection methods.The above methods have better estimation precision,but their computational complexity are generally higher.How to reduce the complexity of the algorithm to improve the real-time performance of the algorithm is still an urgent problem.For the problems existing in the study of offline abnormal subgraph detection and online abnormal subgraph detection(changepoint detection),based on the summarizing the domestic and foreign research of abnormal subgraph detection,this paper analyzed the characteristics of the background graph model such as ER random graph and statistical block model,from the aspects of random matrix characteristic spectrum and figure characteristic carried out the anomaly detection method research under the background of complex network.The specific work contents are as follows:(1)According to the eigenvalue characteristics of the adjacency matrix of the statistical block random graph,the detection algorithm of characteristic spectrum anomaly subgraph under the statistical block model is proposed.(2)Based on the analysis of statistical block observed graph on the change of the characteristic of node betweenness before and after abnormal subgraph embedding,the detection method of anomaly subgraph based on node betweenness is explored.Simulation results show that this method has high detection performance.(3)A low complexity changepoint detection algorithm for CL random graph is proposed by using the triangle subgraph.Compared with traditional detection methods,this method has a lower computational load and can meet the real-time requirement of changepoint detection in the background of large dimension network.