Transitive reduction on adjaceny matrix in R

user_12009991 0
Viewed 214

I have a pairwise matrix that I can consider an adjacency matrix of a graph. I am hoping to apply a transitive reduction algorithm to find the graph with the fewest edges but retains the connectivity of the original graph - see image below.

The head of my matrix looks like so:

               EN_DavaW      EN_DrumW   CN_ShainW  CN_Glasdrum        19-CCP
EN_DavaW     0.0000000000  2.286985e-03 0.014775598  0.013954988 -0.0149552822
EN_DrumW    -0.0022869851  0.000000e+00 0.013133681  0.011270755 -0.0166146429
CN_ShainW   -0.0147755985 -1.313368e-02 0.000000000 -0.001550990 -0.0244997421
CN_Glasdrum -0.0139549879 -1.127075e-02 0.001550990  0.000000000 -0.0328348644
19-CCP       0.0149552822  1.661464e-02 0.024499742  0.032834864  0.0000000000

In this matrix a positive integer can be visualised by an arrow from Pop 1 to Pop 2. Whereas a negative value the arrow would be from Pop 2 to Pop1.

I am struggling to find a package available for R version 4.02 that will carry this out on my matrix. I have looked at the package nem, more specifically the function nem::transitive.reduction see here but it is not available for the version stated above. Even when installing through bioconductor

Are there any other packages or can I create my own function to carry out transitive reduction on a pairwise matrix?

Example of transitive reduction

transitive-closure bioconductor igraph graph-theory r
1 Answers

I think you can try a combination of igraph + relations like below

library(igraph)
library(relations)

g <- graph_from_adjacency_matrix(m, mode = "directed", weighted = TRUE)
df <- get.data.frame(g)
r <- endorelation(
  domain = as.list(unique(unlist(df[c("from", "to")]))),
  graph = df[c("from", "to")]
)
mat <- relation_incidence(transitive_reduction(r))
mattr <- m[row.names(mat), colnames(mat)] * mat
gtr <- graph_from_adjacency_matrix(mattr, mode = "directed", weighted = TRUE)
  • Origin graph

enter image description here

  • Transitive reduction graph

enter image description here

Data

> dput(m)
structure(c(0, -0.0022869851, -0.0147755985, -0.0139549879, 0.0149552822, 
0.002286985, 0, -0.01313368, -0.01127075, 0.01661464, 0.014775598,
0.013133681, 0, 0.00155099, 0.024499742, 0.013954988, 0.011270755,
-0.00155099, 0, 0.032834864, -0.0149552822, -0.0166146429, -0.0244997421,
-0.0328348644, 0), .Dim = c(5L, 5L), .Dimnames = list(c("EN_DavaW",
"EN_DrumW", "CN_ShainW", "CN_Glasdrum", "19-CCP"), c("EN_DavaW",
"EN_DrumW", "CN_ShainW", "CN_Glasdrum", "19-CCP")))
user_121587570
Related