Unsupervised Anomalous Vertices Detection Utilizing Link Prediction Algorithms Academic Article uri icon


  • In the past decade, complex network structures have penetrated nearly every aspect of our lives. The detection of anomalous vertices in these networks can uncover important insights, such as exposing intruders in a computer network. In this study, we present a novel unsupervised two-layered meta classifier that can be employed to detect irregular vertices in complex networks using solely features extracted from the network topology. Our method is based on the hypothesis that a vertex having many links with low probabilities of existing has a higher likelihood of being anomalous. We evaluated our method on ten networks, using three fully simulated, five semi-simulated, and two real world datasets. In all the scenarios, our method was able to identify anomalous and irregular vertices with low false positive rates and high AUCs. Moreover, we demonstrated that our method can be applied to security-related use cases and is able to detect malicious profiles in online social networks.

publication date

  • October 24, 2016