posted on 2011-02-01, 00:00authored byLeman 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.
History
Publisher Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-19823-6_4