PAKDD 2010, Hyderabad, India, 21-24 June 2010. BEST PAPER AWARD!
Leman Akoglu, Mary McGlohon, Christos Faloutsos
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
Given a large, weighted graph, how can we find anomalies? Which rules should be violated, before we label a node as an anomaly? We propose the OddBall algorithm, to find such nodes. The contributions are the following: (a) we discover several new rules (power laws) in density, weights, ranks and eigenvalues that seem to govern the socalled “neighborhood sub-graphs” and we show how to use these rules for anomaly detection; (b) we carefully choose features, and design OddBall, so that it is scalable and it can work un-supervised (no user-defined constants) and (c) we report experiments on many real graphs with up to 1.6 million nodes, where OddBall indeed spots unusual nodes that agree with intuition
FULL PAPER: pdf