SpotRank: Robust voting scheme for social news websites

In this post I give a short overview of SpotRank, an algorithm designed by Thomas Largillier, Guillaume Peyronnet and Myself. The goal of SpotRank is to offer a voting mechanism for social news website (such as Digg for instance) which is robust to manipulation attempts by malicious users. Again the post is highly inspired by our research paper. A previous post introduced social news websites and related issues.

We consider that the voting system SpotRank is used by a community of users that can propose its own news (or content), that we will call spots. Any user of the community can vote for a spot.
It is important to understand that SpotRank  is based on two key notions. The first one is that two votes do not necessarily have the same value. Indeed, we will assign, depending on many factors, a score to each vote. This will induce a score for each spot (the sum of the score of each vote in favor of this spot). The higher the score of a spot, the closer to the first place (e.g. the top of the front page) is the spot. A large part of
SpotRank is the score computation mechanism. The other key notion is the pertinence. The pertinence of a user depends on the pertinence of the spots he voted for, and vice versa. A part of the score update of a spot will depend on the pertinence of the user that votes for this spot. Last, an additional mechanism is used in order to avoid large scale manipulations: a method to detect cabals (i.e. group of users that repeatedly vote one for each other).

The method is working as follows:

• A user proposes a spot. The score of this spot is initialised according to several criteria (all related to the known behavior of the user).
• Users vote for the spot. Each vote induces an update on the spot’s score and pertinence, but also of the pertinence of users that previously voted for this spot. The score of the spot is then used by a social news website in order to rank published content.
• Periodically, an algorithm that detects collusion between users outputs clusters of potential malicious users. These clusters are used for computing the score of a vote.
• To avoid old very strong spots to stay forever at the top of the ranking, we reduce the score of a spot periodically.

The following picture depicts the voting process of SpotRank for a given spot:

SpotRank

In the next post, I give some experimental results. It’s here.