Possibility and Probability

A Python programmer with a personality thinking about space exploration

5 December 2006

Graphing eBay users to find fraud

by Nick

Here’s an interesting article about data mining and auction fraud. Graphs, and what you can do with them, never ceases to amaze me. The article talks about how looking at the relationships between users on eBay can help uncover fraud and the accomplices that help keep it going. They do this by seeing if the relationship between groups of users turns into a biparte graph. That is, there is a concentration of links between two groups of users, and few links with other users. The links between users refers to the “feedback scores” that eBay users use to determine a user’s trustworthiness. Usually, when someone begins ripping others off, they get bad feedback until it reaches a point where no one will do business with them. This is the way that community sites commonly work (i.e. letting the population of users determine each other’s rankings). The issue is that sometimes there are people lurking in the shadows assisting the fraudster, but because they are never the target of the bad feedback, they are able to keep going supporting new fraudsters (i.e. a new user id). This setup allows a scammer to setup a new user id and get its feedback levels boosted quickly without having to engage in a lot of “legitimate” transactions. Think of it as passing a baton in a relay race: Instead of one person running a mile, why not let several people sprint as fast as they can for a quarter-mile and then hand off to someone “fresh”. Think about it: When was the last time you checked someone’s feedback ratings on eBay? Probably right before your last purchase/bid. But, when was the last time you checked the people who gave the feedback to see what their reputation was? Probably never. I know I had never thought of this before reading the article. This technique produces a graphical representation of this relationship which stands out quickly to a user. (Also, as side note, there are mathematical formulas that would/should see this also.) A normal user would probably have a relationship graph (over 2 or more degrees) that looks like a star-burst pattern. A potential scammer would show up in a clustered bipartite graph. This would give the community of users (eBay bidders) a powerful tool to determine who is the real deal and who is trying to give them a wooden nickel. Very cool stuff. Graph theory to the rescue!