NetProbe: A Fast and Scalable System for Fraud Detection in Online Auction Networks
Shashank Pandit (Carnegie Mellon University)
Duen Horng Chau (Carnegie Mellon University)
Samuel Wang (Carnegie Mellon University)
Christos Faloutsos (Carnegie Mellon University)
Given a large online network of online auction uesrs and their histories of transactions, how can we spot anomalies, or even auction fraud? We describe the algorithms and system design decisions behind our proposed NetProbe system for uncovering auction fraud. We show that it is possible to do fast and scalable fraud detection, in large auction networks. The main idea is to use the machinery of "Markov Random Fields" (MRF), and try to guess the hidden state (fraud/honest) of each participant. We describe the algorithms behind our system, that are based on "belief propagation"; we provide our own incremental but accurate approximations to it; and we list and justify our design decisions for efficient crawling of real auction networks. We report experiments on synthetic graphs containing as many as 7,000 nodes and 30,000 edges, where NetProbe was able to spot fraudulent nodes with over 90 % precision and recall, with execution times in the order of seconds. We also report experiments on a real graph consisting of about 700,000 transactions between more than 66,000 eBay users, where NetProbe was highly effective at unearthing hidden networks of fraudsters, within a realistic response time of about 6 minutes.
Alberta, Saturday, May 12, 2007, 3:30pm to 5:00pm.