Поиск полной матрицы смежности в R

Question

У меня есть матрица смежности из пакета 'bnlearn' с использованием функции amat (матрица ациклична). Например:

+---+-------------------------------+    
    | | 1  2  3  4  5 |    
    +---+-------------------------------+    
    | 1 | 0  1  0  0  0 |    
    | 2 | 0  0  1  0  0 |    
    | 3 | 0  0  0  1  0 |    
    | 4 | 0  0  0  0  1 |    
    | 5 | 0  0  0  0  0 |    
    +---+-------------------------------+   

Мне нужно найти полную матрицу зависимостей от этого. Для одной матрицы лаг зависимостей можно использовать:

New_matrix<- if(old_matrix+old_matrix*old_matrix)>0 then 1 else 0 

Для два матрицы лаг зависимостей можно использовать:

New_matrix_2<- if(new_matrix+new_matrix*old_matrix)>0 then 1 else 0 

проблему, я не знаю, где смежность является полной, то есть для сколько итераций я запускаю это, чтобы попасть в итоговую матрицу с включенными взаимозависимостями?

+---+-------------------------------+    
    | | 1  2  3  4  5 |    
    +---+-------------------------------+    
    | 1 | 0  1  1  1  1 |    
    | 2 | 0  0  1  1  1 |    
    | 3 | 0  0  0  1  1 |    
    | 4 | 0  0  0  0  1 |    
    | 5 | 0  0  0  0  0 |    
    +---+-------------------------------+ 

Для этого ответ - 3 итерации. Но матрица, которую мне нужно решить, - 500х500. Есть ли прямой способ получить полную матрицу смежности?

Answer 1

Чтобы найти пути со всех узлов, вероятно, проще использовать пакет igraph.

Используя ваш пример,

library(bnlearn) 
library(igraph) 

# Create BN in your example 
g <- empty.graph(LETTERS[1:5]) 
amat(g) <- rbind(cbind(0, diag(4)),0) 
amat(g) 
# A B C D E 
# A 0 1 0 0 0 
# B 0 0 1 0 0 
# C 0 0 0 1 0 
# D 0 0 0 0 1 
# E 0 0 0 0 0 

---

# Convert to igraph object using BN adj. matrix as input 
g1 <- graph_from_adjacency_matrix(amat(g)) 

# You can find all ancestors for each node by using 
# the mode="in" argument, and order to specify the depth of the search 
neighborhood(g1, order=nrow(amat(g)), mode="in") 

# Similarly, you can get the full connected graph 
# using the same options 
ances <- connect(g1, order=nrow(amat(g)), mode="in") 
get.adjacency(ances, sparse=FALSE) 
# A B C D E 
# A 0 1 1 1 1 
# B 0 0 1 1 1 
# C 0 0 0 1 1 
# D 0 0 0 0 1 
# E 0 0 0 0 0 

В качестве альтернативы, вы можете использовать матрицу экспоненциальный

m <- amat(g) 
1* as.matrix((Matrix::expm(m) - diag(ncol(m))) > 0)