8
$\begingroup$

Here's a mathematical modeling problem I came across while working on a hobby project.

I have a website that presents each visitor with a list of movie titles. The user has to rank them from most to least favorite. After each visit, I want to create a cumulative ranking that takes into account each visitor's individual ranking. Normally I would just take the mean ordinal rank: e.g., if Person A rated "Avatar" 10th and Person B rated it 20th, its cumulative rank would be 15th. However, new movies will be added to the list as the website grows, so each person will have ranked only a subset of the full movie list.

Any thoughts on how I can define "average rank" when some rankings do not cover the whole set? My best idea so far is to model this as a directed graph, where nodes are movies and weighted edges are preferences (e.g. "10 people ranked 'Avatar' right above 'District 9'"), and then finding sinks and sources. How else could one go about this?

(Sorry if this question is too applied.)

Improve this question
$\endgroup$
4
  • $\begingroup$ It's not a duplicate, but there's some relation to this question: mathoverflow.net/questions/6019/… $\endgroup$
    – Tom Leinster
    Commented Feb 21, 2010 at 3:48
  • $\begingroup$ What is the final goal of this; i.e. what do you want your cumulative ranking to reflect? Depending on this, there are various possibilities. E.g. if you just want to get something that generally reflects the popularity of each movie, you can go with a trivial extension of what you do now. For each movie, just compute the fraction of people who ranked it 1st, 2nd, etc. -- the fraction is relative to the total number of people who ranked this movie. Then do something with this (take the average w.r.t. the fractions, or the mode, etc.) $\endgroup$
    – user3035
    Commented Feb 21, 2010 at 4:04
  • $\begingroup$ this is question related to the netflix prize? $\endgroup$
    – john mangual
    Commented Feb 21, 2010 at 4:14
  • $\begingroup$ @John: not related to the Netflix Prize, although maybe there is something I can learn from that. $\endgroup$
    – RexE
    Commented Feb 21, 2010 at 4:20

1 Answer 1

Reset to default
5
$\begingroup$

There are a few different ways of approaching the problem. A good reference for this precise problem is 'Rank Aggregation methods For The Web', by Dwork, Kumar, Naor and Sivakumar from the WWW conference in 2001. It's not the most recent work, but it lays out the mathematics nicely.

In general, the way to define an average is to define a metric, and then look at the point that minimizes the sum of distances from the individual lists. If the lists were full (i.e all defined over the same set), you could use Spearman's footrule distance, or the Kendall distance. Since they are not, the general idea is to find some global ranking that's locally optimal (i.e there's no other full ranking that yields a smaller distance to the partial lists and can be obtained by flipping rankings from the current candidate). As an aside, you can compare a full ranking with a partial ranking by merely projecting the full ranking onto the partial ranking and then computing one of the above mentioned distances.

Most of this is worked out in detail in the paper referenced, so your best bet is to start there.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .