мультипликативное расстояние между узлами графа - PullRequest
Новая
       8

мультипликативное расстояние между узлами графа

0 голосов
/ 24 апреля 2018

Я хочу найти расстояние между всеми узлами на графике, но вместо суммирования весов ребер я хочу их умножить.

Как пример: 

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, и я изо всех сил пытаюсь выяснить это самостоятельно (в реальных данных матрицы намного больше, иРазнообразие размеров).Любые предложения будут высоко ценится.

Ответы [ 2 ]

0 голосов
/ 24 апреля 2018

Написание функции, как в ответе выше, безусловно, лучший путь.Но другой способ осмыслить проблему состоит в том, что если вам нужны продукты весов, а 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
0 голосов
/ 24 апреля 2018

Вот предложение.Вероятно, есть много возможностей для улучшения, но это дает ожидаемый результат.Идея состоит в том, чтобы извлечь кратчайший путь для каждой пары узлов, а затем умножить веса, связанные с каждым путем (я использовал некоторый код из этого answer ). 

shortest.paths.multi <- function(mx) {
  output <- mx
  mx2 <- graph.adjacency(mx, weighted = TRUE)
  for (r in 1:nrow(mx)){
    for (c in 1:nrow(mx)){
      SP <- shortest_paths(mx2, from = r, to = c)
      VP <- SP$vpath[[1]]
      EP <- rep(VP, each=2)[-1]
      EP <- EP[-length(EP)]
      output[r, c] <- prod(E(mx2)$weight[get.edge.ids(mx2, EP)])
    }
  }
  diag(output) <- 0
  output
}

shortest.paths.multi(mx)

      [,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

РЕДАКТИРОВАТЬ

Вот, вероятно, лучший способ написать эту функцию: 

shortest.paths.multi <- function(r, c){ 
  SP <- shortest_paths(mx2, from = r, to = c)
  VP <- SP$vpath[[1]]
  EP <- rep(VP, each=2)[-1]
  EP <- EP[-length(EP)]
  prod(E(mx2)$weight[get.edge.ids(mx2, EP)])
}

VecFun <- Vectorize(shortest.paths.multi)

output <- outer(1:nrow(mx), 1:ncol(mx), FUN = VecFun)
diag(output) <- 0
output
...