Incremental and parallel algorithm for anomaly detection in dynamic graphs

Financial fraud behavior, network intrusion and suspicious social actions can be detected by structural anomaly detection in graphs. The existing anomaly detection algorithms require high computational complexity and cannot process large-scale dynamic graphs. So an incremental and parallel algorithm is proposed to discover and detect abnormal patterns in dynamic graphs effectively and efficiently. The whole graph was partitioned into subgraphs by time sliding windows. N subgraphs in time sliding windows were processed in parallel by minimum description length (MDL) principle to discover both normal and abnormal patterns. Structural outliers can be detected gradually in parallel based on normal patterns. The results of experiments conducted in multiple large-scale graphs show that the precision rate for detecting the abnormal patterns of dynamic graph reaches 96%, recall rate reaches 85%, and running time reduces by an order of magnitude. The impact of the size of sliding windows and the number of parallel on running time of the algorithm is also discussed.