Graph Feature Based Multilayer Social Network Analysis for Anomaly Detection

Abstract

Online social networks have received a dramatic increase of interest in the last decade due to the growth of the Internet and Web 2.0. They provide convenient platforms for people to share, communicate, and collaborate in real-time regardless of the differences and geographic distances among them. However, with the openness and the diversity of the users of social networks, malicious users turn online social networks into platforms for illicit activities such as spamming, identity theft, cyber-attacks, organized crimes, and even terrorist attack planning. Discovering such suspicious and illicit behavior in social networks is a significant and challenging problem in social network analysis. The unusual behavior of users that cause harm to legitimate users can be identified by using anomaly detection techniques. The major categories of anomalies occurring in social networks are point anomalies and collective or group anomalies. Point anomalies or anomalous nodes signify the unusual behavior of individual users whereas collective anomalies signify the unusual behavior of groups of users. As these two types of anomalies can signify illegal and illicit behavior, they are to be detected to uncover such suspicious behavior. Several techniques and tools have been proposed for detecting point and collective anomalies in social networks. These techniques and tools are developed for single-layer social networks with only one type of interaction among the individuals. However, the social relationships among individuals are more complex and they interact with each other in multiple ways simultaneously leading to multiple networks among the same set of individuals, or a multi-layer social network with each layer representing one type of interaction. The analysis of only one type of interaction for anomaly detection does not provide a complete picture of the relationships among the users of the networks. Therefore, there is an urgency and need for multi-layer analysis of the networks for identifying the anomalies by employing the rich information hidden in the individual network layers. Hence, this work aims at developing approaches for detecting point and collective anomalies in multi-layer social networks. In social networks, if the neighborhood of a user is a clique/near-clique or a star/near-star pattern, the online behavior of the user can be linked to an anomalous behavior, as only minority of users follow these patterns. In a multi-layer social network, if the neighborhoods of nodes in different layers are close to stars or cliques, they can signify anomalous behavior. Hence, in this work, an unsupervised approach called Anomaly Detection On Multi-layer Social networks (ADOMS) is proposed for idetecting these point anomalies in multi-layer social networks, by using graph-theoretic features of the networks and data mining techniques. The online behavior of users is modeled as an unattributed multi-layer social network, and the network structure-based features of the network are extracted to detect anomalies. Anomaly scores are computed for the nodes of the multi-layer network and the nodes are then ranked based on their anomalousness. The nodes with high anomaly scores are the top ranked anomalies. The proposed approach is evaluated using extensive experiments on multiple real-world multi-layer network datasets, and the experimental results substantiate that the approach can effectively detect anomalous nodes in multi-layer social networks. Spamming is the most predominant form of anomalous activity prevalent in online social networks that involves malicious users sending unsolicited messages to legitimate users with the intention of wasting their time, bandwidth, and money. Being one of the fastest growing online social networks, Twitter has become a cardinal target platform for social spammers. A substantial amount of research work has been carried out in the field of detecting spam messages and social spammers in Twitter. However, one of the important issues in Twitter is that the social spammers collaborate with each other and form collective anomalies or spammer communities to spread spam messages to a large set of legitimate users. Consequently, it is highly desirable to detect such spammer communities prevailing in Twitter. Hence, in this work, an unsupervised approach called Spammer Community detection (SpamCom) is proposed for detecting spammer communities in Twitter by using graph-theoretic features of the network and the network attributes. The Twitter network is modeled as an attributed multi-layer social network, and the overlapping community-based features of the network are exploited to identify spammers based on their structural behavior and URL characteristics. The utilization of community-based features of the network, URL characteristics of user accounts, and content similarity among the tweets makes the approach robust and efficient. The approach is evaluated on real-world dataset, and the experimental results show significant performance in detecting spammers and spammer communities.