Neighborhood Formation and Anomaly Detection

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. au-thors in a scientific publication network, and so on. We introduce two operations on bipartite graphs: 1) identify-ing similar nodes (Neighborhood formation), and 2) find-ing abnormal nodes (Anomaly detection). And we propose algorithms to compute the neighborhood for each node us-ing random walk with restarts and graph partitioning; we also propose algorithms to identify abnormal nodes, us-ing neighborhood information. We evaluate the quality of neighborhoods based on semantics of the datasets, and we also measure the performance of the anomaly detection al-gorithm with manually injected anomalies. Both effective-ness and efficiency of the methods are confirmed by experi-ments on several real datasets.