file.pdf (3.07 MB)
Download file

OddBall: Spotting Anomalies in Weighted Graphs

Download (3.07 MB)
journal contribution
posted on 01.02.2011, 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.

History

Publisher Statement

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-19823-6_4

Date

01/02/2011

Usage metrics

Exports