快速算法與概率向圖

我正在與鄰接矩陣看起來像這樣的工作由一階鄰接矩陣計算二階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：如何快速計算概率有向圖中的二階鄰接矩陣？

來源

2017-02-03 generic_user

由於結構的原因，必須縮放N^2。我會用1-prod（1-pr）取代你的union.pr函數，我相信這會提高你的運行速度。 – Julius

您的union.pr函數比簡單高效的方法要慢500倍。所以用1-prod（1-pr）取代你的union.pr，你就可以獲得500倍的速度。

x <- runif(1000)*0.01 

t1 <- proc.time() 
for (i in 1:10000){ 
    y <- union.pr(x) 
} 
t1 <- proc.time()-t1 
print(t1) 
# user system elapsed 
# 21.09 0.02 21.18 

t2 <- proc.time() 
for (i in 1:10000){ 
    y <- 1-prod(1-x) 
} 
t2 <- proc.time() - t2 
print(t2) 
# user system elapsed 
# 0.04 0.00 0.03

來源

2017-02-03 22:35:27 Julius

所以@朱利葉斯的回答對於提醒我一些基本的概率規則很有用，但它並沒有加快計算速度。下面的函數，但是，可幫助一噸：

second_order_adjacency2 <- function(A, i, j){#function to calculate probability that i is linked to j through some other node 
    a1 <- A[i,1:nrow(A) %ni% c(i,j)] 
    a2 <- t(A)[j,1:nrow(A) %ni% c(i,j)] 
    1-prod(1-a1*a2) 
}

它仍然鱗片狀N^2，因爲它是一個循環，但需要在各種路徑的計算從i到j優點矢量化。因此它更快。

來源

2017-02-06 22:22:32

快速算法與概率向圖

回答

相關問題