r - 使矩阵传递 R

Question

对于 R 中的二进制矩阵，是否有一种快速/有效的方法使矩阵具有传递性？也就是说，如果 [i, j] == 1, and [i, k] == 1, set [j, k] = 1. 例如，假设我们有一个方阵的个体，并且连续有一个 1/column 表示它们是相关的。有没有快速的方法来找出哪些人以某种方式相关？

取矩阵 Mx

 Mx a b c d e
 a  1 1 0 1 0
 b  0 1 0 0 0 
 c  0 0 1 1 0
 d  0 0 0 1 0
 e  0 0 0 0 1

由于 [a, b] == 1 和 [a,d] == 1，[b,d] 和 [d, b] 应设置为 1。
类似地，[c, d] == 1，并且由于 a、b 和 d 是相关的，因此 a、b、c、d 应该是 1。最终的矩阵看起来像这样，并且应该在对角线上对称。

Mx a b c d e 
 a 1 1 1 1 0
 b 1 1 1 1 0
 c 1 1 1 1 0
 d 1 1 1 1 0 
 e 0 0 0 0 1

因此，对于家庭示例，这意味着 a、b、c 和 d 以某种方式相关。
现在我有一个计算第二个矩阵的函数，但它运行 n^3 次，其中 n 是行数/列数。有没有更快的方法来做到这一点？谢谢

n^3 函数:

   # Repeat loop three times for completion
     for (rep in 1:3) {
   # For every individual i
       for (i in 1:N) {
   # For every individual j
         for (j in 1:N) {
   # For every individual k
           for (k in 1:N) {
    # If i and j are related and j and k are related
            if (Mx[i,j] == 1 && Mx[j, k] == 1) {
        #i and k are related
              Mx[i,k] <- 1
              Mx[k,i] <- 1
                    }
                  }
               }
            }
         }

Answer 1

查找与任意关系关联的等价关系
归结为找到相应图的连通分量。
它可以用
depth-first search .
它已经在 igraph 中实现了包裹。

library(igraph)
n <- 5
A <- matrix( sample(0:1, n^2, prob=c(.8,.2), replace=T), n, n)
A
#      [,1] [,2] [,3] [,4] [,5]
# [1,]    0    0    0    0    0
# [2,]    0    1    0    0    0
# [3,]    0    0    1    0    1
# [4,]    1    0    1    0    1
# [5,]    0    0    0    0    0
i <- clusters(graph.adjacency(A))$membership
B <- A
B[] <- i[row(A)] == i[col(A)]
B
#     [,1] [,2] [,3] [,4] [,5]
# [1,]    1    0    1    1    1
# [2,]    0    1    0    0    0
# [3,]    1    0    1    1    1
# [4,]    1    0    1    1    1
# [5,]    1    0    1    1    1

如果你想要传递和自反闭包(自反，传递，但不一定对称——这个例子已经是传递的，但不是自反的):

library(relations)
 relation_incidence( reflexive_closure( transitive_closure( as.relation(A) ) ) )
# Incidences:
#   1 2 3 4 5
# 1 1 0 0 0 0
# 2 0 1 0 0 0
# 3 0 0 1 0 1
# 4 1 0 1 1 1
# 5 0 0 0 0 1