Research On Anomaly Detection In Dynamic Complex Networks

Complex Network is a class of networks with certain common structural features,such as social network, citation network, coauthor network, AS Graph and Web Graph.Two important features of them are dynamics and large-scale, which make statisticalanomaly detection in dynamic complex network an extremely important problem. It canbe widely used in network management, web search monitoring, complex network theoryresearch. We solve two problems in thesis: (1) Given a time series of network, identifywhen occurs anomaly in the time series; (2) Given a time of anomaly, how to selectregions which best represents the change of network;For the first problem, we show a framework of anomaly detection in complex network.We definite anomalies under observation on real datasets(linear growth of vertex,edges), and research results (DPL and power law degree distribution), We give ananomaly detection algorithm with linear regression model. We propose an iterative algorithm,iLRAD algorithm further. The basic idea is to remove the detected outliers, fitthe line, get new outliers sets and do it again. The process stopped until the anomaliesset is stable. Experimental results on real datasets show that em iLRAD can achieveconvergence quickly and. significantly improve efficiency of anomaly detection.For the second problem, we consider the general version: Given two successivesnapshot of complex network, find regions which can best represent the changes of statisticalcharacteristics. We formalize the problem into an optimization problem, the k-CRproblem. Take the vertex statistical feature for an instance, we show the problem is NPhardwhich implies no algorithm can find the optimal solution in polynomial time. Wegive two approximation algorithms to solve the k-CR problem, the Top-k Score Algorithmand the Greedy Remove algorithm. The two algorithms are both linear time. Experimentalresults on real and synthetic datasets shows the greedy remove algorithm has agood approximation ratio. We also give a branch and bound algorithm to find the optimalsolutions. We show the strategy of estimate lower bound and make a sketch of proof.