根据成对排名计算所有项目的顺序

Question

我对人的身高进行了成对比较，一个人的 ID 在 'person1' 列，另一个在 'person2' 列。 'height' 变量表示 'person1' 和 'person2' 中谁最高。如果 'height' 为 1，则 'person1' 最高。

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

我需要从这些人与人之间的顺序联系中找出谁最高。看看这个玩具数据，我知道顺序应该是：

D, C, B, A

我的第一个想法是成功给分，然后尝试追查对方的记录，并为他们比其他人高加分。示例：

A 会从直接关系中得到 0p，因为他比 B 和 D 矮。从间接关系中他会得到 0，因为 B 比 C 矮，但会得到 1，因为 D 比 C 高。我认为一轮不是够了，但我需要像这样更进一步。

我的真实数据是多人。

Answer 1

一种可能是将个人的成对排名视为有向图。计算出边的度数。获取从源顶点（最大度数；最高个体）到目标顶点（度数 = 0；最短个体没有出边）的简单路径。抓住最长的路径。

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)

根据成对排名计算所有项目的顺序

Calculate order of all items based on pairwise rankings

r

rank