Netprobe: a fast and scalable system for fraud detection in online auction networks

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.

REFERENCES

• 1: Auctionbytes: ebay auction fraud spawns vigilantism trend. http://www.auctionbytes.com/cab/abn/y02/m10/i12/s01, 2002.
• 2: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 3: D. H. Chau and C. Faloutsos. Fraud detection in electronic auction. In European Web Mining Forum at ECML/PKDD, 2005.
• 4: D. H. Chau, S. Pandit, and C. Faloutsos. Detecting fraudulent personalities in networks of online auctioneers. In Proc. ECML/PKDD, 2006.
• 5: Cecil Eng Huang Chua , Jonathan Wareham, Fighting Internet Auction Fraud: An Assessment and Proposal, Computer, v.37 n.10, p.31-37, October 2004 [doi>10.1109/MC.2004.165]
• 6: ebay inc. announces third quarter 2006 financial results. http: //biz.yahoo.com/bw/061018/20061018005916.html?.v=1, October 2006.
• 7: ebay: Avoiding fraud. http://pages.ebay.com/securitycenter/avoiding fraud.html, 2006.
• 8: Federal trade commission: Internet auctions: A guide for buyers and sellers. http: //www.ftc.gov/bcp/conline/pubs/online/auctions.htm, 2004.
• 9: Z. Gyongyi, H. G. Molina, and J. Pedersen. Combating web spam with trustrank. In VLDB, 2004.
• 10: Internet fraud complaint center: Ic3 2004 internet fraud -- crime report. http://www.ifccfbi.gov/strategy/statistics.asp, 2005.
• 11: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 12: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Extracting Large-Scale Knowledge Bases from the Web, Proceedings of the 25th International Conference on Very Large Data Bases, p.639-650, September 07-10, 1999
• 13: M. Melnik and J. Alm. Does a seller's ecommerce reputation matter? evidence from ebay auctions. Journal of Industrial Economics, 50:337--49, 2002.
• 14: J. Neville and D. Jensen. Collective classification with relational dependency networks. In 2nd Multi-Relational Data Mining Workshop, SIGKDD, 2003.
• 15: Jennifer Neville , Özgür Şimşek , David Jensen , John Komoroske , Kelly Palmer , Henry Goldberg, Using relational knowledge discovery to prevent securities fraud, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081922]
• 16: Jian Pei , Daxin Jiang , Aidong Zhang, On mining cross-graph quasi-cliques, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081898]
• 17: Paul Resnick , Ko Kuwabara , Richard Zeckhauser , Eric Friedman, Reputation systems, Communications of the ACM, v.43 n.12, p.45-48, Dec. 2000 [doi>10.1145/355112.355122]
• 18: P. Resnick, R. Zeckhauser, J. Swanson, and K. Lockwood. The value of reputation on ebay: A controlled experiment, 2003.
• 19: Georgos Siganos , Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, Power laws and the AS-level internet topology, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.514-524, August 2003 [doi>10.1109/TNET.2003.815300]
• 20: Usa today: How to avoid online auction fraud. http://www.usatoday.com/tech/columnist/2002/05/07/yaukey.htm, 2002.
• 21: Wei Wang , Chen Wang , Yongtai Zhu , Baile Shi , Jian Pei , Xifeng Yan , Jiawei Han, GraphMiner: a structural pattern-mining system for large disk-based graph databases and its applications, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066273]
• 22: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 23: Xifeng Yan , X. Jasmine Zhou , Jiawei Han, Mining closed relational graphs with connectivity constraints, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081908]
• 24: Jonathan S. Yedidia , William T. Freeman , Yair Weiss, Understanding belief propagation and its generalizations, Exploring artificial intelligence in the new millennium, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 25: Zhiping Zeng , Jianyong Wang , Lizhu Zhou , George Karypis, Coherent closed quasi-clique discovery from large dense graph databases, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150506]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.m Miscellaneous

General Terms:
Algorithms

Keywords:
belief propagation, bipartite cores, fraud detection, markov random fields