Anomaly detection in networks is a dynamically growing field with compelling applications in areas such as security (detection of network intrusions), finance (frauds), and social sciences (identification of opinion leaders and spammers). Its applicability is propelled by an ever increasing availability of network data: the ubiquity of handheld devices gave rise to a plethora of community and network-based services that in turn generate a wide spectrum of graph data in the most different domains.
This work addresses the problem of outlier detection in plain, static graphs. We analyze three fundamental, a feature, a network structure and an information theory driven anomaly detection technique. We demonstrate their effectiveness and results on four real-world datasets from the domains of discussion, social, spatial, and market basket networks. Each network's unique characteristic is presented along with an overarching set of features allowing for network comparison. Finally, we offer an outline to extend the examined anomaly detection techniques to the dynamic context of graphs. We conclude with a discussion on possible directions of future work.