OddBall: Spotting Anomalies in Weighted Graphs. 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 million nodes, where oddball indeed spots unusual nodes that agree with intuition.

References in zbMATH (referenced in 11 articles )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Eswar, Srinivas; Kannan, Ramakrishnan; Vuduc, Richard; Park, Haesun: ORCA: outlier detection and robust clustering for attributed graphs (2021)
  2. Riahi, Fatemeh; Schulte, Oliver: Model-based exception mining for object-relational data (2020)
  3. Tosyali, Ali; Kim, Jinho; Choi, Jeongsub; Kang, Yunyi; Jeong, Myong K.: New node anomaly detection algorithm based on nonnegative matrix factorization for directed citation networks (2020)
  4. Bhamidi, Shankar; Jin, Jimmy; Nobel, Andrew: Change point detection in network models: preferential attachment and long range dependence (2018)
  5. Zhou, Dawei; Karthikeyan, Arun; Wang, Kangyang; Cao, Nan; He, Jingrui: Discovering rare categories from graph streams (2017)
  6. Chan, Hau; Akoglu, Leman: Optimizing network robustness by edge rewiring: a general framework (2016)
  7. Davis, Michael Charles; Ma, Zhanyu; Liu, Weiru; Miller, Paul; Hunter, Ruth; Kee, Frank: Generating realistic labelled, weighted random graphs (2015)
  8. Koutra, Danai; Kang, U.; Vreeken, Jilles; Faloutsos, Christos: Summarizing and understanding large graphs (2015)
  9. Li, Zhongmou; Xiong, Hui; Liu, Yanchi: Mining blackhole and volcano patterns in directed graphs: a general approach (2012)
  10. Tong, Hanghang; Lin, Ching-yung: Non-negative residual matrix factorization: problem definition, fast solutions, and applications (2012)
  11. Akoglu, Leman; McGlohon, Mary; Faloutsos, Christos: Oddball: Spotting anomalies in weighted graphs (2010) ioport