Neighborhood Formation and Anomaly Detection in Bipartite Graphs

Jimeng Sun, Huiming Qu, D. Chakrabarti, C. Faloutsos

Research output: Contribution to conferencePaperpeer-review

Abstract

Many real applications can be modeled using bipartite graphs, such as users vs. files in a P2P system, traders vs. stocks in a financial trading system, conferences vs. authors in a scientific publication network, and so on. We introduce two operations on bipartite graphs: 1) identifying similar nodes (Neighborhood formation), and 2) finding abnormal nodes (Anomaly detection). And we propose algorithms to compute the neighborhood for each node using random walk with restarts and graph partitioning; we also propose algorithms to identify abnormal nodes, using neighborhood information. We evaluate the quality of neighborhoods based on semantics of the datasets, and we also measure the performance of the anomaly detection algorithm with manually injected anomalies. Both effectiveness and efficiency of the methods are confirmed by experiments on several real datasets.
Original languageEnglish (US)
Pages418-425
DOIs
StatePublished - 2005
Externally publishedYes

Fingerprint

Dive into the research topics of 'Neighborhood Formation and Anomaly Detection in Bipartite Graphs'. Together they form a unique fingerprint.

Cite this