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 (relevance search), and 2) finding
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 effectiveness
and efficiency of the methods are confirmed by experiments
on several real datasets.