Dominance-directed (tournament) graph metrics

Question

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)

create a data frame of edges

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)

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)

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.

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.

Thanks in advance!

Answer 1

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 

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 

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