Concurrent Detection of Compact Anomalous Subgraphs in Large Social Networks

This paper presents a new approach to the detection of asymptomatic anomalies based on the signal processing related to local information of graph that simultaneously detects small compact anomalous subgraphs in the unknown graphs of large social networks. It also introduces a novell sampling algorithm based on compressive sensing to retrieve the sparse properties of static networks, which aims to improve the accuracy of anomaly detection while reducing the complexity of data sampling. The results of experimental experiments with artificial random and real datasets of social networks in comparison with the state-of-the-art methods showed that the proposed approach, in addition to having the accuracy of simultaneous detection of anomalous compact subgraphs, the computational complexity reduced from O(n^4 √(log⁡n )) to O(n^2) in the n node networks and is easily applicable in complex dynamic networks.