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 が何らかの形で関連していることを意味します。現在、この 2 番目の行列を計算する関数がありますが、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 に答える