支配性(锦标赛)图指标 [英] Dominance-directed (tournament) graph metrics

问题描述

我有兴趣为优势有向图(又称锦标赛图)中的节点导出优势度量(如在优势层次中).我可以使用R和包igraph轻松构建此类图，例如

I am interested in deriving dominance metrics (as in a dominance hierarchy) for nodes in a dominance directed graph, aka a tournament graph. I can use R and the package igraph to easily construct such graphs, e.g.

library(igraph)

创建边缘的数据框

the.froms <- c(1,1,1,2,2,3)

the.tos <- c(2,3,4,3,4,4)

the.set <- data.frame(the.froms, the.tos)

set.graph <- graph.data.frame(the.set)

plot(set.graph)

此图显示节点1影响节点2、3和4(对它们来说是主要的)，节点2对3和4来说是主要的，而3对4来说是主要的.

This plotted graph shows that node 1 influences nodes 2, 3, and 4 (is dominant to them), that 2 is dominant to 3 and 4, and that 3 is dominant to 4.

但是，我发现没有简单的方法可以像在页面中那样实际计算一个支配地位层次结构:

However, I see no easy way to actually calculate a dominance hierarchy as in the page: https://www.math.ucdavis.edu/~daddel/linear_algebra_appl/Applications/GraphTheory/GraphTheory_9_17/node11.html . So, my first and main question is does anyone know how to derive a dominance hierarchy/node-based dominance metric for a graph like this using some hopefully already coded solution in R?

此外，在我的实际情况下，我实际上有一个稀疏的矩阵，缺少一些交互作用，例如

Moreover, in my real case, I actually have a sparse matrix that is missing some interactions, e.g.

incomplete.set <- the.set[-2, ]

incomplete.graph <- graph.data.frame(incomplete.set)

plot(incomplete.graph)

在此绘制的图中，物种1和3之间没有任何联系，但是对传递性进行一些假设时，优势层次与上面相同.

In this plotted graph, there is no connection between species 1 and 3, however making some assumptions about transitivity, the dominance hierarchy is the same as above.

这是一个更为复杂的问题，但是如果有人对我如何得出像这样的稀疏矩阵的基于节点的支配性度量有任何意见，请告诉我.我希望在R中使用已经编码的解决方案，但是我当然比愿意自己编写解决方案更为重要.

This is a much more complicated problem, but if anyone has any input about how I might go about deriving node-based metrics of dominance for sparse matrices like this, please let me know. I am hoping for an already coded solution in R, but I'm certainly MORE than willing to code it myself.

提前谢谢！

推荐答案

不确定这是完美的方法还是我完全理解这一点，但是通过反复试验，它似乎可以正常工作:

Not sure if this is perfect or that I fully understand this, but it seems to work as it should from some trial and error:

library(relations)
result <- relation_consensus(endorelation(graph=the.set),method="Borda")
relation_class_ids(result)
#1 2 3 4 
#1 2 3 4 

method=有很多潜在的选项可用于处理领带等-有关更多信息，请参见?relation_consensus.使用线性顺序的method="SD/L"可能最适合您的数据，尽管由于较复杂的示例中存在冲突，它可能会建议多种解决方案.对于当前的简单数据，情况并非如此-尝试:

There are lots of potential options for method= for dealing with ties etc - see ?relation_consensus for more information. Using method="SD/L" which is a linear order might be the most appropriate for your data, though it can suggest multiple possible solutions due to conflicts in more complex examples. For the current simple data this is not the case though - try:

result <- relation_consensus(endorelation(graph=the.set),method="SD/L",
                             control=list(n="all"))
result
#An ensemble of 1 relation of size 4 x 4.

lapply(result,relation_class_ids)
#[[1]]
#1 2 3 4 
#1 2 3 4 

?relation_consensus中的示例中再次提供了处理此问题的方法.

Methods of dealing with this are again provided in the examples in ?relation_consensus.

这篇关于支配性(锦标赛)图指标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！