Mining social networks for anomalies: Methods and challenges

Online social networks have received a dramatic increase of interest in the last decade due to the growth of Internet and Web 2.0. They are among the most popular sites on the Internet that are being used in almost all areas of life including education, medical, entertainment, business, and telemarketing. Unfortunately, they have become primary targets for malicious users who attempt to perform illegal activities and cause harm to other users. The unusual behavior of such users can be identified by using anomaly detection techniques. Anomaly detection in social networks refers to the problem of identifying the strange and unexpected behavior of users by exploring the patterns hidden in the networks, as the patterns of interaction of such users deviate significantly from the normal users of the networks. Even though a multitude of anomaly detection methods have been developed for different problem settings, this field is still relatively young and rapidly growing. Hence, there is a growing need for an organized study of the work done in the area of anomaly detection in social networks. In this paper, we provide a comprehensive review of a large set of methods for mining social networks for anomalies by providing a multi-level taxonomy to categorize the existing techniques based on the nature of input network, the type of anomalies they detect, and the underlying anomaly detection approach. In addition, this paper highlights the various application scenarios where these methods have been used, and explores the research challenges and open issues in this field.