Carnegie Mellon University
file.pdf (3.07 MB)
Download file

OddBall: Spotting Anomalies in Weighted Graphs

Download (3.07 MB)
journal contribution
posted on 2011-02-01, 00:00 authored by Leman Akoglu, Mary McGlohon, Christos Faloutsos

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 so-called “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 millionnodes, where oddball indeed spots unusual nodes that agree with intuition.


Publisher Statement

The final publication is available at Springer via



Usage metrics