图节点之间的乘法距离

Question

我想找到图中所有节点之间的距离,而不是总和我想要乘以它们的边权重.

举个例子:

library(igraph)

# create a weighted adjacency matrix
mx <- structure(c(0, 0.5, 0, 0, 0, 0.5, 0, 0.5, 0.5, 0, 0, 0.5, 0, 0, 0.5, 0, 0.5, 
    0, 0, 0, 0, 0, 0.5, 0, 0), .Dim = c(5L, 5L))

## convert to igraph object
mx2 <- graph.adjacency(mx, weighted = TRUE)

我可以得到所有节点之间的距离如下:

shortest.paths(mx2)

 [,1] [,2] [,3] [,4] [,5]
[1,]  0.0  0.5  1.0  1.0  1.5
[2,]  0.5  0.0  0.5  0.5  1.0
[3,]  1.0  0.5  0.0  1.0  0.5
[4,]  1.0  0.5  1.0  0.0  1.5
[5,]  1.5  1.0  0.5  1.5  0.0

但是这会计算所有节点之间的距离,方法是将我想要乘以的相关权重相加,这将产生以下结果:

      [,1] [,2] [,3]  [,4]  [,5]
[1,] 0.000 0.50 0.25 0.250 0.125
[2,] 0.500 0.00 0.50 0.500 0.250
[3,] 0.250 0.50 0.00 0.250 0.500
[4,] 0.250 0.50 0.25 0.000 0.125
[5,] 0.125 0.25 0.50 0.125 0.000

据我所知,使用igraph中的"开箱即用"选项无法做到这一点,我正在努力自己解决这个问题(在真实数据中,矩阵更大,各种尺寸).任何建议将不胜感激.

Answer 1

像上面的答案一样编写函数肯定是更好的方法。但另一种思考问题的方式是，如果您想要权重的乘积，并shortest.paths()为您提供权重的总和，那么如果您shortest.paths()将权重的对数提供给函数，则结果的指数将等于权重的乘积。

这在实践中比我想象的要挑剔一些，因为您的权重介于 0 和 1 之间，并且shortest.paths()算法不会接受负权重，但是您可以通过在计算权重之前和之后乘以 -1 来解决。

library(igraph)

## Cheat and log it
ln.mx <- structure(c(0, 0.5, 0, 0, 0, 0.5, 0, 0.5, 0.5, 0, 0, 0.5, 0, 0, 0.5, 0, 0.5, 
                  0, 0, 0, 0, 0, 0.5, 0, 0), .Dim = c(5L, 5L))
ln.mx <- ifelse(ln.mx!=0, log(ln.mx), 0) 

## convert to igraph object
ln.mx2 <- graph.adjacency(ln.mx, weighted = TRUE)

# The issue with the approach is that the shortest.path algorithm doesn't like
# negative weights. Since your weights fall in (0,1) their log is negative.
# We multiply edge weights by -1 to swap the sign, and then will 
# multiply again by -1 to get
# the result
E(ln.mx2)$weight <- -1*E(ln.mx2)$weight

# The result is just the regular shortest paths algorithm,
# times -1 (to undo the step above) and exponentiated to undue the logging
res <- exp(shortest.paths(ln.mx2)* -1)

# its still not perfect since the diagonal distance defaults to
# zero and exp(0) is 1, not 0. So we manually reset the diagonal
diag(res) <- 0

# The result is as hoped
res
#>       [,1] [,2] [,3]  [,4]  [,5]
#> [1,] 0.000 0.50 0.25 0.250 0.125
#> [2,] 0.500 0.00 0.50 0.500 0.250
#> [3,] 0.250 0.50 0.00 0.250 0.500
#> [4,] 0.250 0.50 0.25 0.000 0.125
#> [5,] 0.125 0.25 0.50 0.125 0.000