Calculate order of all items based on pairwise rankings

user_3914086 0
Viewed 136

I have pairwise comparisons of heights of people, with one person ID in column 'person1' and the other in 'person2'. The 'height' variable indicates who is tallest of 'person1' and 'person2'. If 'height' is 1, then 'person1' is tallest.

df <- data.frame(person1 = c('A', 'C', 'B', 'D'),
                 person2 = c('B', 'D', 'C', 'A'),
                 height = c(0, 0, 0, 1))
df
#   person1 person2 height
# 1       A       B      0 # B is taller than A
# 2       C       D      0 # D is taller than C
# 3       B       C      0 # C is taller than B
# 4       D       A      1 # D is taller than A

I need to figure out who is tallest from these sequential links between people. Just looking at this toy data, I know the order should be:

D, C, B, A

My first idea was to give points from success and then try to track down opposite persons record and give extra points for them being taller than other ones. Example:

A would receive 0p from direct relations because he is shorter than B and D. From indirect he would get 0 because B is shorter than C but would get 1 because D is taller than C. I think one round is not enough, but I would need to go further like this.

My real data is with more persons.

rank r
1 Answers

One possibility may be to treat the pairwise ranking of individuals as a directed graph. Calculate degree of outgoing edges. Get simple paths from a source vertex (max degree; the tallest individual) to a target vertex (degree = 0; the shortest individual has no outgoing edges). Grab the longest path.

library(igraph)
library(data.table)

setDT(df)

# reorder columns to reflect direction of vertices 
df[height == 0, `:=`(person1 = person2, person2 = person1)]

g = graph_from_data_frame(df[ , 1:2])
deg = degree(g, mode = "out")
pth = all_simple_paths(g, from = names(deg[which.max(deg)]), to = names(deg[deg == 0]))
pth[which.max(lengths(pth))]
# [[1]]
# + 4/4 vertices, named, from 96b1b6c:
# [1] D C B A

plot(g)

enter image description here

user_18517120
Related