Ratings and rankings are everywhere in daily life. We rank sports teams, chess players, movies and TV-shows, doctors, local businesses, and sometimes even each other.

This article is about computing an overall rating in a setting where people have individually rated each other. Examples include dating apps like Tinder, e-commerce websites where people act as both sellers and buyers, and other platforms where we want to quantify the trustworthiness or quality of members.

We distinguish between two scenarios:

• Symmetry: if person \(a\) rates \(b\), then \(b\) must also rate \(a\). Their rating values may differ.
• No symmetry: if person \(a\) rates \(b\), then it does not necessarily follow that \(b\) rates \(a\) back.

In this article we’ll consider the more general non-symmetric scenario. Given individual ratings that are either positive or negative, the goal is to produce an overall rating of everyone. The figure below shows 5 people, where blue arrows indicate positive ratings and red arrows indicate negative ratings.

In the figure above, we expect \(a\) to be highly rated and \(c\) to be poorly rated.

Simple aggregation

The simplest thing we can do is to count the number of ratings and create a ratio \(r_i\) between \(0\) and \(1\) for each person.

We define a binary matrix \(P\) consisting of positive ratings and a matrix \(N\) of negative ratings.

The rating vector \(\boldsymbol{r}\) is computed by summing positive ratings and dividing by total ratings. One issue with the naive approach is that someone who has few ratings might end up with a total rating of \(0\) or \(1\), so we employ the rule of succession by adding two dummy ratings: one positive and one negative. The equation becomes

Or alternatively, in matrix notation, where \(\boldsymbol{1}\) and \(\boldsymbol{2}\) denote vectors of ones and twos and division is entry-wise:

Here’s a piece of Python code that implements this computation on the graph structure shown in the initial figure:

import numpy as np

P = np.array([
     [0, 1, 1, 1, 1], # <- Positive ratings given to A
     [0, 0, 0, 0, 0], # <- Positive ratings given to B
     [0, 0, 0, 0, 0],
     [0, 1, 1, 0, 0],
     [1, 0, 0, 0, 0], # <- Positive ratings given to E
    ])

N = np.array([
     [0, 0, 0, 0, 0], # <- Negative ratings given to A
     [0, 0, 1, 0, 0], # <- Negative ratings given to B
     [0, 1, 0, 1, 1],
     [1, 0, 0, 0, 1],
     [0, 0, 0, 0, 0], # <- Negative ratings given to E
    ])

# Simple aggregation
ratings = (1 + np.sum(P, axis=1)) / (2 + np.sum(P, axis=1) + np.sum(N, axis=1))
print(ratings.round(2))  # [0.83 0.33 0.2  0.5  0.67]

The results are superimposed on the graph in the figure below.

The popular person \(a\) gets the highest rating \(0.83\) as expected, and unpopular person \(c\) gets the lowest rating \(0.2\) as expected.

Weighted aggregation

Perhaps all users in a system should not be considered equally trustworthy. In other words, if \(a\) rates \(b\) positively, then our opinion of \(b\) might also depend on \(a\).

• If \(a\) is a long-time user, who is positively rated by others and who has given balanced ratings to others, then we should trust \(a\)’s ratings.
• If \(a\) is a new user, or is negatively rated by others, or rates everyone negatively, then we should perhaps not trust \(a\)’s ratings as much.

We weight each user with a weight \(w_j \in [0, 1]\) before we aggregate their individual ratings:

How do we choose the weights \(w_j\)? There are many possibilities, but the weights \(w_j\) must somehow represent the trustworthiness of person \(j\).

Weighting by discrimination

One idea is to look at how much discrimination each user applies. Whose ratings do you trust more: someone who rates everyone positively, or someone who rates half the population negatively and the other half positively? If you agree with me that the second person provides more useful information, then one option is to compute a scaled version of the entropy:

where \(n\) is the number of negative ratings the person has given and \(p\) is the number of positive ratings.

Observe that \(H(p=k, n=k) = 1\) for all \(k \geq 1\) and that \(H(p=k, n=0) = H(p=0, n=k) = 0\) for all \(k \geq 1\). In other words, this weighting function accomplishes what we set out to do: users with high discriminatory power are given a weight of one, while users who show no discrimination in their ratings are given a weight of zero.

from scipy.stats import entropy

def H(n, p):
    return entropy([n, p]) / np.log(2)

print(H(5, 5))  # 1.0
print(H(0, 5))  # 0.0

weights = entropy(np.stack((np.sum(P, axis=0), np.sum(N, axis=0))), axis=0) / np.log(2)

# Weighted positive and negative sums
P_w = P * weights
N_w = N * weights

# Weighted ratings
ratings = (1 + np.sum(P_w, axis=1)) / (2 + np.sum(P_w, axis=1) + np.sum(N_w, axis=1))
print(ratings.round(2))  # [0.83 0.34 0.21 0.49 0.67]

In this particular problem instance, the results do not differ much from the previous ratings.

Entropy is by no means the only possible quality measure—it depends strongly on the specific use-case. A number of more complicated weighting functions could be used. For instance, we could also weight a user by:

1. how many ratings they have given in total
2. how long they have been users in the system/platform
3. how much information they have on their profile
4. how well they themselves are rated by others.

All of these signal high levels of trustworthiness. We will now pursue option (4): we’ll weight each person’s ratings by how highly they themselves are rated.

Weighted aggregation by rating

The final model that we’ll consider is the most advanced one. The idea is that the rating person \(a\) gives to person \(b\) should be weighted by the rating person \(a\) has. Building on the matrix notation we established earlier, we write the equation as:

• In an e-commerce platform, this means that if \(a\) is highly rated and gives a positive rating, then that is worth more than a positive rating from a user with mixed or negative ratings.
• In a dating app like Tinder where ratings signify attractiveness, the interpretation is that if someone who is attractive rates us favorably, then that rating is worth more than a rating from someone who is not considered attractive by others.

Notice the recursive definition: to weight the ratings given by person \(a\) to others, we need to know the overall rating of person \(a\)—but that quantity is exactly what we’re trying to compute in the first place!

Solution by fixed-point iteration

The simplest and fastest way to compute \(\boldsymbol{r}\) is to iterate the equation until it converges. Starting with an initial guess \(\boldsymbol{r}_0 = \boldsymbol{1} / 2\) we compute

repeatedly until convergence, as measured by \(\lVert \boldsymbol{r}_{k+1} - \boldsymbol{r}_{k}  \rVert < \epsilon\).

epsilon = 1e-12
ratings = np.ones(N.shape[0]) / 2
for iteration in range(99):
    new_ratings = (1 + P @ ratings) / (2 + P @ ratings + N @ ratings)
    if np.linalg.norm(new_ratings - ratings) < epsilon:
        break
    ratings = new_ratings

print(ratings.round(2))  # [0.74 0.44 0.29 0.42 0.63]

Convergence is linear, and after 13 iterations the procedure terminates.

All three ratings induce rankings on the people, and they are compared in the figure below.

Notice how:

• Person \(b\) moves up compared to the simple rating. He is given a negative rating by \(c\), but \(c\) has a low overall rating and this lessens the weight given to \(c\)’s opinion of \(b\).
• Person \(d\) moves down, because the negative rating from \(a\) matters a lot and the positive rating from \(c\) matters little.

Summary and references

Rating and ranking is interesting because it is part science and part art. There’s no fixed answer: every scenario is different and must be modeled appropriately.

The problem considered in this article, where people rate people, is special in two ways: (1) there is just one group and (2) ratings are not symmetric. The defining equation is

which is non-linear in the vector \(\boldsymbol{r}\) and may contain millions of unknown variables. Despite this, it’s solved by fixed-point iteration in a few seconds on a laptop.

I’ve previously written about how patients can rate doctors. In that problem there were two separate groups: doctors and patients. One group rates the other group. I’ve also written about rating football teams, which is a symmetric problem. If team \(a\) plays \(b\), then \(b\) necessarily plays \(a\) too.

The PageRank algorithm ranks websites, and it’s what made Google famous in the late 90s. The paper A Survey on PageRank Computing is an interesting read. Similar algorithms include HITS, SALSA and EigenTrust. The book Who’s #1?: The Science of Rating and Ranking gives an overview of simple methods, with a focus on sports. When users interact with each other, the field is sometimes called reputation systems. The paper The Digitization of Word of Mouth: Promise and Challenges of Online Feedback Mechanisms explores the online reputation mechanisms of the early internet.

The ideas in the paper Propagation of Trust and Distrust are similar to those expressed in this article, but the authors focus more on local propagation while we solve a global problem. Reputation and ranking is closely related to content discovery, recommendation systems and collaborative filtering, and the book Recommender Systems by Aggarwal is a handy reference. This has social implications too, which the paper On Social Machines for Algorithmic Regulation explores.

Appendix A: Empirical results

I created random sparse rating matrices for a million people. I set the density to \(p=10^{-5}\), so each matrix has approximately \(\left( 10^6 \right)^2 \times p = 10^7\) non-negative entries. Convergence is shown in the figure below.

Below is the computation on the third largest strongly connected component of the Epinions social network dataset. The full dataset has 131,828 nodes and 841,372 and is solved quickly, but it’s too large to visualize in full.

Appendix B: Solution by Newton’s method

Newton’s method and its variants can be an alternative to fixed-point iteration. While Newton’s method exhibits quadratic convergence (fixed-point iteration is linear), the time spent per iteration is so high that it ends up being an inferior choice in practice. Also, if the starting point is not good (\(\boldsymbol{r} = 1/2\) tends to work, while \(\boldsymbol{r} = 0\) does not) the algorithm will fail. Regardless, here’s how it can be done.

The matrix equation

 is equivalent to solving

which we can do with Newton’s method:

To find the Jacobian matrix \(J_{ij}(\boldsymbol{r}) = \partial F_i(\boldsymbol{r}) / \partial \boldsymbol{r}_{j}\), we first write out the components of \(F(\boldsymbol{r})\).

Differentiating with respect to \(r_j\), then switching back to matrix notation, we obtain:

This can be implemented in Python as:

def F_and_J(ratings, P, N):
    """Returns a tuple (F, J), with function value F and its jacobian J."""
    Pr = P @ ratings
    Pr_Nr = Pr + N @ ratings
    F = ratings * (2 + Pr_Nr) - 1 - Pr
    J = ratings * (P + N) - P
    np.fill_diagonal(J, J.diagonal() + 2 + Pr_Nr)
    return F, J

epsilon = 1e-12
ratings = np.ones(N.shape[0]) / 2
for iteration in range(99):
    F, J = F_and_J(ratings, P, N)
    new_ratings = ratings - np.linalg.solve(J, F)
    if np.linalg.norm(new_ratings - ratings) < epsilon:
        break
    ratings = new_ratings
print(ratings.round(2))  # [0.74 0.44 0.29 0.42 0.63] <- Same as fixed-point

Note that the code above explicitly stores zeros (it does not use sparse matrices), and would therefore be unsuitable for large matrices.

Appendix C: Properties of the fixed-point iteration

In millions of computational experiments with random matrices \(P\) and \(N\), the fixed-point iteration seemingly always converges to a unique fixed point. For a long time I conjectured that the fixed point iteration always converges to a unique, attracting fixed point. However, it turns out this conjecture is false.

A counterexample is the following structure: There are three groups and at least 16 people in each group. Within each group, everyone rates everyone else negatively. There are no self-ratings.

With 16 people in each group, the algorithm cycles between \((0.509, 0.366, 0.509)\) and \((0.29, 0.585, 0.29)\) when started at a random \(\boldsymbol{r}\). With 15 people in each group, the algorithm does not cycle, but will eventually converge.

Appendix D: Code

Here is some Python 3.12 code for the model.

import numpy as np  # Version: 2.1.3


class RatingProblem:

    def __init__(self, N, P):
        """Initialize a problem given positive binary ratings P
        and negative binary ratings N."""
        assert (N.shape == P.shape) and (N.shape[0] == N.shape[1])
        self.P, self.N = P, N

    @classmethod
    def random(cls, n, seed=None):
        """Create a random problem instance of size n."""
        rng = np.random.default_rng(seed)

        # Create adjacency matrix with random density
        density = rng.random()
        adj = (rng.random(size=(n, n)) < density).astype(int)

        # Zero out diagonal (can't rate yourself)
        np.fill_diagonal(adj, 0)

        # Randomly split into positive and negative ratings
        split = rng.random(size=(n, n)) < rng.random()
        return cls(N=adj * (1 - split), P=adj * split)

    def __call__(self, r):
        assert len(r) == self.N.shape[0]
        P, N = self.P, self.N
        return (1 + P @ r) / (2 + P @ r + N @ r)

    def jacobian(self, r):
        """Compute the Jacobian matrix at r."""
        assert len(r) == self.N.shape[0]

        P, N = self.P, self.N
        Pr, Nr = P @ r, N @ r

        # Vectorized jacobian computation
        numerator = (1 + Nr)[:, None] * P - (1 + Pr)[:, None] * N
        denominator = (2 + Pr + Nr) ** 2
        return numerator / denominator[:, None]

    def solve(self, r_0=None, epsilon=1e-12):
        """Solve using fixed-point iteration."""
        r_0 = np.ones(self.N.shape[0]) / 2 if r_0 is None else r_0

        assert len(r_0) == self.N.shape[0]

        ratings = r_0.copy()
        for iteration in range(99):
            new_ratings = self(ratings)
            if np.linalg.norm(new_ratings - ratings) < epsilon:
                break
            ratings = new_ratings
        return ratings


if __name__ == "__main__":

    rng = np.random.default_rng(0)

    # Test that different starting points converge to the same value
    for test in range(10**4):

        n = rng.integers(4, 20)
        problem = RatingProblem.random(n=n, seed=test)
        r1 = rng.random(size=n) * rng.random()
        r2 = rng.random(size=n) * rng.random()

        s1 = problem.solve(r1)
        s2 = problem.solve(r2)
        assert np.allclose(s1, s2)

        if test % 1_000 == 0:
            print(".", end="")