Detecting voting rings with HyperLogLog

(written by lawrence krubner, however indented passages are often quotes). You can contact lawrence at: lawrence@krubner.com, or follow me on Twitter.

While this seems like a clever trick, I typically want a lot of metrics regarding voting, so throwing away the metadata doesn’t seem like an option to me. As an aggregate tool whose only purpose is finding voting rings, maybe this useful maybe?

But consider what would happen if we created a HyperLogLog counter for every user on Reddit, and any time that a user receives an upvote, we update the corresponding HyperLogLog counter with the id of the user who did the upvoting. Given this setup, here’s how we detect the voting ring. First, for a given user, retrieve the estimated count of unique upvotes from that user’s HyperLogLog counter and let’s label this quantity as estimated_unique_upvotes. Next, tally up the total number of actual upvotes…

(these things)

across all of that user’s posts. Let’s call this quantity as global_total_upvotes. The probability that a given user is involved in a voting ring will correlate highly with the ratio of these numbers. In other words we can define

voting_honesty = estimated_unique_upvotes / global_total_upvotes

Think about it. If a user is not in a voting ring, then their upvotes are going to be organically generated from anyone one the world-wide-web that thinks their links are interesting. Because the internet is a big place, this user’s estimated_unique_upvotes and global_total_upvotes will tend toward the same number and their voting_honesty “probability” will tend toward 1. On the other hand, a user wrapped up in seedy underworld of Reddit voting rings will have many more global_total_upvotes across all posts than they have estimated_unique_upvotes. For this user, the voting_honesty will tend toward 0.

Post external references

  1. 1
    http://opensourceconnections.com/blog/2013/10/14/detecting-reddit-voting-rings-using-hyperloglog-counters/
Source