Neighborhood Formation and Anomaly Detection in Bipartite Graphs

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

Research output: Contribution to conferencePaperpeer-review


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)
StatePublished - 2005
Externally publishedYes


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

Cite this