Relevance Search and Anomaly Detection in Bipartite Graphs Jimeng Sun, Huiming Qu, Deepayan Chakrabarti, and Christos Faloutsos   View Paper (PDF)   Return to December 2005, Volume 7, Issue 2 Abstract Many real applications can be modeled using bipartite graphs, such as users vs. files in a P2P system, traders vs. stocks in a finan- cial trading system, conferences vs. authors in a scientific publica- tion network, and so on. We introduce two operations on bipartite graphs: 1) identifying similar nodes (relevance search), and 2) find- ing nodes connecting irrelevant nodes (anomaly detection). And we propose algorithms to compute the relevance score for each node using random walk with restarts and graph partitioning; we also propose algorithms to identify anomalies, using relevance scores. We evaluate the quality of relevance search based on semantics of the datasets, and we also measure the performance of the anomaly detection algorithm with manually injected anomalies. Both ef- fectiveness and efficiency of the methods are confirmed by experi- ments on several real datasets. ©2006 Association for Computing Machinery