Non-personalized ranking systems that average the ratings of individual users are prone to attacks associated with bribing. Grouping users according to their preferences and weighting the average by the reputation of the users allows to generate more personalized rankings. These rankings are also less prone to attacks.

In a paper published in the ACM Transactions on Knowledge Discovery from Data (TKDD), with João Saúde, Guilherme Ramos, and Carlos Caleiro, we propose a new reputation-based ranking system, utilizing multipartite rating subnetworks, which clusters users by their similarities using three measures, two of them based on Kolmogorov complexity. We also study its resistance to bribery and how to design optimal bribing strategies.

A Multipartite Reputation-Based Ranking System

To enable the multimodal rating behavior of the users in the ranking, our group ranking system employs a multipartite graph. Our approach works in four steps:

1. User similarity extraction. Considering the ratings of two users for the items rated by both, we introduce three measures to compute their similarity.
2. Extraction of the multipartite graph. We compute the similarities between the users, considering three metrics, namely, Linear Similarity (LS), compression Similarity (CS), and Kolmogorov Similarity (KS). Based on these similarities, we build a new graph that connects two users if their similarity is above a threshold. We merge this graph with the bipartite graph that models the rating of the users, to form a multipartite graph.
3. Group detection. The multipartite graph is split into subgraphs, considering the connected components in it.
4. Reputation-based ranking computation. Given the users in a subgraph, we propose an algorithm that iteratively updates both the reputation of the users, according to the ratings they gave and the ranking estimations, and the ranking of the item, according to the ratings users gave and their reputations.

Readers can refer to the full paper for the details of our approach, the proof of its convergence, and its computational complexity analysis.

Bribing in ranking systems

Bribing is a common and relevant scenario because consumers rely on rankings to make decisions. Henceforth, since the sellers are aware of how ratings impact sales, they need robust ranking systems. Suppose that the seller of item i has, initially, a wealth (and popularity) proportional to the ranking of the item and the number of users that rated the item. A company may invest its wealth to persuade users directly or indirectly to buy an item, for instance, by giving free samples of the item, by offering discount vouchers, by paying directly to users to rate/review the item. In turn, the users start to like more the product.

We analyze three distinct cases: (case 1) the seller of item i bribes users that already rated the item, so that the buyer changes its rating; (case 2) the seller bribes users that did not buy a product i previously; (case 3) the mixed case, where the seller bribes both types of buyers.

In our study, we present a theoretical analysis, showing under which condition a strategy is profitable.

Experiments and results

We validate our proposed rankings systems under the perspectives of effectiveness (given by the Kendall tau of the rankings’ vector versus a ground truth) and robustness, assessed via a metric that evaluates the ability of the system to cope with noise or spamming attacks (please, see the paper for the mathematical details). Specifically, we study the robustness of the algorithm to different kinds of spamming/attacks, namely, random spamming, love/hate attack, and reputation attack.

Our evaluation was conducted on synthetic data and on three real-world datasets, namely Amazon’s “Amazon Instant Video” and “Tools and Home Improvement”, and Movielens-1M.

While our paper contains an extensive evaluation, here are the main outcomes emerging from our results:

• Robustness against random spamming. We notice an increase of robustness for the LS, whereas for the KS and CS we obtain similar robustness to the bipartite methods.
• Robustness against the love/hate attack. The best similarity measure to avoid the effect of the attack on the target item’s ranking is the KS.
• Robustness against the reputation attack. The robustness has a similar behavior as in the love/hate attack, and the best result is achieved in the multipartite scenario when using LS.
• Robustness against bribery. The impact of the bribing strategy is, actually, dimmed when reputations are recomputed, i.e., the return of the strategy is smaller for dynamic reputations than when the reputations are fixed.