rank correlation algorithm

Question

I have a ranking list of friends. Then, I get few more lists of the same friends but different ranking. Is there an algorithm to check which list is the closest to the original ranking list?

Thanks

I think you could do this by using the [array inversions algorithm](http://stackoverflow.com/questions/337664/counting-inversions-in-an-array) which runs in O(n log n). Basically, you take your original ranking and you assign to each item an ID in increasing order and then you search in the "different ranking" for each of your n items to assign to them the corresponding IDs from the initial ranking (you should be able to do this efficiently) and then you apply the algorithm I mentioned above on the IDs assigned to the "different ranking". — Mihai Todor, Mar 21 '13 at 12:09

score 2 · Accepted Answer · answered Mar 21 '13 at 14:53

2

It likely depends on what your measure of "distance" between two rankings is.

For example, if we define

dist(R1, R2) = Sum abs(position of i in R1 - position of i in R2), over all i

then you can store the positions of every i in the first ranking in an array

i.e.

pos[Peter] = 3

means that Peter shows up as the third friend in your ranking.

The closest ranking can be found in linear time by calculating the sum above using pos.

answered Mar 21 '13 at 14:53

abeln

3,749
2
22
31

It's a good solution. However, it doesn't tell me a lot about the importance of the distance. Let say I have a ranking list with 200 friends that are off by 1 place, and on the other hand, I have a ranking list where one friend's ranking is off by 200 places. The distance will be the same. However, the second ranking list is much more off than the first ranking list. – Mike Apr 02 '13 at 23:01
1

You can penalize large discrepancies by taking the square or the cube of the differences in position. – abeln Apr 03 '13 at 13:38

score 2 · Answer 2 · answered Mar 21 '13 at 15:55

I think you should compare rank distances between them, but using weights. Because for example if user ranked 1st is on 10th place, it is a big difference, but if user ranked 101th is on 110th place, that's not a big change. So you should put higher coefficients on differences of higher ranked users.

rank correlation algorithm

2 Answers2