Approximate Optimal Anomaly Subgraph Detection And Application In Attributed Networks

Anomaly subgraphs detection means the subgraphs with the behaviors(attributes)of nodes or edges significantly different from others.For example,cyber-attacks and intrusion are found in computer networks,and corporates with anomaly business are positioned in the corporate investment networks,etc.However,most existing methods pay attention to anomaly information used for modeling of node attributes,overlook the information contained in the subgraphs,and such methods are likely to be affected by noises.In view of the defects of existing methods as mentioned above,the ”the Subgraph Detection of Approximate Anomaly-Structured Maximization in Attributed Networks” is put forward in this thesis,and research is carried out in three aspects,including algorithm innovation,case study and practical application in combination with priori knowledge of the nonparametric scanning statistics method and the anomaly data pattern(e.g.specific structure)given by experts.The specific work is as follows:First,a specific structure targeted anomaly subgraph detection algorithm – AnomalyStructured Maximization to Query in Attributed Networks(AnomalyMaxQ)is put forward.With this algorithm,modeling of empirical distribution of nodes is conducted first to realize quick detect anomaly nodes,and the upper bound of scores function is constructed based on the node anomalous degree;and then the lower bound of scores function of subgraph approximate to the anomaly pattern is constructed with the approximate subgraph matching algorithm,and the most anomaly subgraph approximate to a specific structure is obtained via iteration.The experimental result shows that AnomalyMaxQ algorithm is applicable to large-scale datasets,its precision is more than 0.2higher than the comparison approach,and the precision of the specific query can be up to 1.0;in terms of the robustness,the noise reaches 20%,and the precision maintains 0.7;in terms of the time efficiency,the time spent on reaching the data size of million-level nodes is only 30% of that with other optimal methods.Besides,we verify our method can be applied in different practical scenarios.First,corporate investment risk case analysis was completed based on the corporate investment network.It was successfully found that risk business occurred to enterprises and affiliated companies involved in a number of civil disputes.Second,team recommendation case analysis was completed based on the natural science paper partner network.This thesis demonstrated that the academic cooperation network has the characteristics of scale-free and small-world property.It means that a few authors play a leading role in the network,and The close cooperation among authors is mostly within the research institutions.If the number of academic achievements is more than the expected definition as an exception,the influential groups can be found through the abnormal subgraph detection algorithm.It was judged whether a node in the partner network has increasing significant influences,i.e.an anomaly node,by referring to previous published achievements,and found the subgraph with the most anomaly nodes.With this algorithm,the excellent team led by teacher Wu from Dalian University of Technology was successfully discovered.At last,the academic team recommendation platform was realized based on our method.The platform has many functions like research relationship schema exhibition,multi-perspective visualized academic outcome analysis,etc.This platform can recommend promising academic teams to users and realize visualized analysis.To sum up,AnomalyMaxQ for anomaly subgraph detection in attributed networks is put forward innovatively,effectively reduce the impact of data scale,noise and other factors.Empirical analysis indicates that our method can be used for investors to hedge investment traps and reduce capital loss,and can help to seek for talents and scientific research teams in a specific field.So,it is of practical significance.