A comparative analysis of structural graph metrics to identify anomalies in online social networks. (January 2017) - Kaur, Ravneet; Singh, Sarbjeet
Highlights: The paper presents a comparative study covering both theoretical as well as experimental evaluation of different graph metrics to identify anomalous nodes in online social networks. The analysis of a specific graph metric, called Brokerage is carried out to examine its effectiveness for detecting anomalous nodes. The statistical and graphical analysis of the anomalous nodes is presented. The comparative analysis of rankings given by different measures is investigated. Experiments are performed using four diverse data sets each belonging to somewhat different domain, which helps to analyze the effectiveness of metrics in different domains. Abstract: Social networks are becoming vulnerable to a number of fraudulent attacks and mischievous activities due to their widespread use and increasing popularity. So, detection of anomalous activities, especially in social networks, is essentially required as it helps to identify important and significant information regarding the behavior of anomalous users. In order to detect anomalies in social networks, researchers have mainly relied on the use of behavior and structure based approaches. Working in the similar direction, we extend the graph structure based approach by introducing and analyzing important graph metrics to detect anomalous activities. The comparison and effectiveness of measures have been presented on the basis of statistical measures like precision, recall and F-score, as well as on the basis of calculated anomalous scores. Theoretical and empirical evaluation reveals that the relationship between brokerage and number of edges helps to detect and correctly rank maximum number of anomalies. Graphical abstract: