4

对于 R 中的二进制矩阵，是否有一种快速/有效的方法来使矩阵传递？也就是说，如果 [i, j] == 1，并且 [i, k] == 1，则设置 [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
                    }
                  }
               }
            }
         }
4

1 回答 1

4

找到与任意关系相关的等价关系归结为找到相应图的连通分量。它可以通过 深度优先搜索来完成。它已经在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
于 2013-07-24T17:50:08.810 回答