我正在与邻接矩阵看起来像这样的工作由一阶邻接矩阵计算二阶adacency矩阵:快速算法与概率向图
N <- 5
A <- matrix(round(runif(N^2),1),N)
diag(A) <- 0
1> A
[,1] [,2] [,3] [,4] [,5]
[1,] 0.0 0.1 0.2 0.6 0.9
[2,] 0.8 0.0 0.4 0.7 0.5
[3,] 0.6 0.8 0.0 0.8 0.6
[4,] 0.8 0.1 0.1 0.0 0.3
[5,] 0.2 0.9 0.7 0.9 0.0
概率和定向。
这里来计算i
通过至少一个其他节点连接到j
概率缓慢方式:
library(foreach)
`%ni%` <- Negate(`%in%`) #opposite of `in`
union.pr <- function(x){#Function to calculate the union of many probabilities
if (length(x) == 1){return(x)}
pr <- sum(x[1:2]) - prod(x[1:2])
i <- 3
while(i <= length(x)){
pr <- sum(pr,x[i]) - prod(pr,x[i])
i <- 1+i
}
pr
}
second_order_adjacency <- function(A, i, j){#function to calculate probability that i is linked to j through some other node
pr <- foreach(k = (1:nrow(A))[1:nrow(A) %ni% c(i,j)], .combine = c) %do% {
A[i,k]*A[k,j]
}
union.pr(pr)
}
#loop through the indices...
A2 <- A * NA
for (i in 1:N){
for (j in 1:N){
if (i!=j){
A2[i,j] <- second_order_adjacency(A, i, j)
}
}}
diag(A2) <- 0
1> A2
[,1] [,2] [,3] [,4] [,5]
[1,] 0.000000 0.849976 0.666112 0.851572 0.314480
[2,] 0.699040 0.000000 0.492220 0.805520 0.831888
[3,] 0.885952 0.602192 0.000000 0.870464 0.790240
[4,] 0.187088 0.382128 0.362944 0.000000 0.749960
[5,] 0.954528 0.607608 0.440896 0.856736 0.000000
该算法鳞片状N^2,和我有数千个节点。而我的矩阵并不是那么稀疏 - 很多小数字都有一些大数字。我可以并行化,但我只能按核心数量来划分。有没有一些矢量化的技巧可以让我利用矢量化操作的相对速度?
tl; dr:如何快速计算概率有向图中的二阶邻接矩阵?
由于结构的原因,必须缩放N^2。我会用1-prod(1-pr)取代你的union.pr函数,我相信这会提高你的运行速度。 – Julius