2

For each edge in a graph I would like to add an numeric attribute (weight) that is the product of an attribute (probability) of the incident vertices. I can do it by looping over the edges; that is:

    for (i in E(G)) {
      ind <- V(G)[inc(i)]
      p <- get.vertex.attribute(G, name = "prob", index=ind)
      E(G)[i]$weight <- prod(p)
    }

However, this is qute slow for my graph (|V| ~= 20,000 and |E| ~= 200,000). Is there a faster way to do this operation?

sahoang
  • 375
  • 3
  • 9
  • 2
    Is this any faster? `E(G)$weight <- sapply(E(G),function(e) prod(V(G)[inc(e)]$prob))` – jlhoward Dec 11 '14 at 21:46
  • Yes it is. I get ~10x speed increase. Thank you. However, what I would really like to know is if there is a way to accomplish the same thing using only igraph's methods, which seem to be very efficient; i.e., avoiding R's looping statements/functions -- for, sapply, etc. – sahoang Dec 11 '14 at 22:05

2 Answers2

5

Here is probably the fastest solution. The key is to vectorize.

library(igraph)
G <- graph.full(45)
set.seed(1)
V(G)$prob <- pnorm(vcount(G))

## Original solution
system.time(
  for (i in E(G)) {
    ind <- V(G)[inc(i)]
    p <- get.vertex.attribute(G, name = "prob", index=ind)
    E(G)[i]$wt.1 <- prod(p)
  }
)
#>    user  system elapsed 
#>   1.776   0.011   1.787 

## sapply solution
system.time(
  E(G)$wt.2 <- sapply(E(G), function(e) prod(V(G)[inc(e)]$prob))
)
#>    user  system elapsed 
#>   1.275   0.003   1.279 

## vectorized solution 
system.time({
  el <- get.edgelist(G)
  E(G)$wt.3 <- V(G)[el[, 1]]$prob * V(G)[el[, 2]]$prob
})
#>    user  system elapsed 
#>   0.003   0.000   0.003 

## are they the same?
identical(E(G)$wt.1, E(G)$wt.2)
#> [1] TRUE
identical(E(G)$wt.1, E(G)$wt.3)
#> [1] TRUE

The vectorized solution seems to be about 500 times faster, although more and better measurements would be needed to evaluate this more precisely.

Gabor Csardi
  • 10,705
  • 1
  • 36
  • 53
3

Converting my comment to an answer.

library(igraph)
# sample data  - you should have provided this!!!
G <- graph.full(10)
set.seed(1)
V(G)$prob <- pnorm(rnorm(10))
length(E(G))

# for-loop
for (i in E(G)) {
  ind <- V(G)[inc(i)]
  p <- get.vertex.attribute(G, name = "prob", index=ind)
  E(G)[i]$wt.1 <- prod(p)
}

# sapply
E(G)$wt.2 <- sapply(E(G),function(e) prod(V(G)[inc(e)]$prob))

# are they the same?
identical(E(G)$wt.1, E(G)$wt.2)

With just 10 vertices and 45 edges, sapply(...) is about 4 times faster; with 100 vertices and ~5,000 edges, it is about 6 times faster.

jlhoward
  • 58,004
  • 7
  • 97
  • 140
  • 1
    Thank you for selecting my answer, but you should really deselect it and select @Gabor's, as his is clearly the preferred method. BTW he wrote the igraph package. – jlhoward Dec 12 '14 at 20:00