Повышение скорости вычисления веса ребра в графе Igraph R - PullRequest
Новая
       11

Повышение скорости вычисления веса ребра в графе Igraph R

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

У меня простая проблема. Я пытаюсь установить вес ребер в графе, на котором я хочу сделать некоторые вычисления. Мой рабочий код выглядит следующим образом: for(e in E(g)){ E(g)[e]$weight <- 1/(degree(g, v = V(g)[ends(g, e)][2], mode = "in")) }
Для небольших графиков это работает нормально. Но для графа, который имеет 105K ребер, это занимает слишком много времени (65 минут !!) Есть ли более эффективный способ сделать это, как я могу сделать это быстрее? Заранее большое спасибо!

1 Ответ

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

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

library(igraph)

# A small toy graph to demonstrate
set.seed(234)
g <- random.graph.game(10, .25, directed = T)

# Your approach for constructing weights
for(e in E(g)){
  E(g)[e]$weight <- 1/(degree(g, v = V(g)[ends(g, e)][2], mode = "in"))
}

# Vectorized version
res <- 1/degree(g, v = V(g)[ends(g, E(g))[,2]], mode = "in")

# We test to make sure the results are the same
all.equal(E(g)$weight, res)
#> [1] TRUE

# To show how much faster it is lets make a big graph with ~100k edges
set.seed(42)
g <- random.graph.game(1000, .1, directed = T)
length(E(g))
#> [1] 99307

microbenchmark::microbenchmark(E(g)$weight <- 1/degree(g, v = V(g)[ends(g, E(g))[,2]], mode = "in"))
#> Unit: milliseconds
#>                                                                   expr
#>  E(g)$weight <- 1/degree(g, v = V(g)[ends(g, E(g))[, 2]], mode = "in")
#>       min       lq     mean   median       uq      max neval
#>  15.45099 57.88469 54.22476 59.22422 60.43034 106.6269   100

Новая версия занимает около 60 миллисекунд на 99 307 фронтах.

...