Netprobe

TLDR

The challenge is detecting anomalies and fraud in large online auction networks. The paper introduces NetProbe and its incremental variant to detect fraud in dynamic auction data. NetProbe models users and transactions as a Markov Random Field and uses belief propagation, while IncrementalNetProbe provides a fast approximate version for evolving data. NetProbe achieves over 90% precision and recall on synthetic graphs and rapidly uncovers fraud networks on real eBay data, and IncrementalNetProbe is twice as fast with more than 99% of the original accuracy.

Abstract

Given a large online network of online auction users and their histories of transactions, how can we spot anomalies and auction fraud? This paper describes the design and implementation of NetProbe, a system that we propose for solving this problem. NetProbe models auction users and transactions as a Markov Random Field tuned to detect the suspicious patterns that fraudsters create, and employs a Belief Propagation mechanism to detect likely fraudsters. Our experiments show that NetProbe is both efficient and effective for fraud detection. We report experiments on synthetic graphs with as many as 7,000 nodes and 30,000 edges, where NetProbe was able to spot fraudulent nodes with over 90% precision and recall, within a matter of seconds. We also report experiments on a real dataset crawled from eBay, with nearly 700,000 transactions between more than 66,000users, where NetProbe was highly effective at unearthing hidden networks of fraudsters, within a realistic response time of about 6 minutes. For scenarios where the underlying data is dynamic in nature, we propose IncrementalNetProbe, which is an approximate, but fast, variant of NetProbe. Our experiments prove that Incremental NetProbe executes nearly doubly fast as compared to NetProbe, while retaining over 99% of its accuracy.