R: igraph eccentricity seems not use weighed edge

Question

I use igraph to compute the vertices eccentricity, the graph is weighted, and random generated as following

n <- 500
g <- sample_smallworld(1, n, 10, 0.05)
E(g)$weight <- (runif(1)+0.1)*10
is.weighed(g)
dia <- diameter(g)
dia

It is a small world network, with 500 vertices, and random weighted edges. Use diameter and 'is.weighted' to check it does be weighted. However, eccentricity does not use the weight, and generate the following result,

d_list <- eccentricity(g)
summary(d_list)

output as following,

d_list <- eccentricity(g)
summary(d_list)
Min. 1st Qu. Median Mean 3rd Qu. Max.
4.000 4.000 4.000 4.004 4.000 5.000

how to solve this problem?

now I use max(distances(g)) to solve it, but I think it not an efficient and elegant way.

user1470500 user1470500 · Accepted Answer · 2016-07-29T06:31:21

I don't think eccentricity give you the option but if I will not pronounce myself about the elegancy of the distances() method, from an efficiency point of view both algorithms will execute in O(|V|^2*log(|V|)) (assuming |E| = O(|V|)) to compute the eccentricity of each node, if you run some test you get this:

f1 <- function(n) {
  g <- sample_smallworld(1, n, 10, 0.05)
  E(g)$weight <- (runif(n*10)+0.1)*10
  system.time(eccentricity(g))
}

f2 <- function(n) {
  g <- sample_smallworld(1, n, 10, 0.05)
  E(g)$weight <- (runif(n*10)+0.1)*10
  system.time(distances(g))
}


f3 <- function(n) {
  g <- sample_smallworld(1, n, 10, 0.05)
  tmp <- (runif(n*10)+0.1)*10
  system.time(eccentricity(g))
}

f4 <- function(n) {
  g <- sample_smallworld(1, n, 10, 0.05)
  tmp <- (runif(n*10)+0.1)*10
  system.time(distances(g))
}

t1 <- sapply((10:60)*50, function(x){f1(x)[3]})
t2 <- sapply((10:60)*50, function(x){f2(x)[3]})
t3 <- sapply((10:60)*50, function(x){f3(x)[3]})
t4 <- sapply((10:60)*50, function(x){f4(x)[3]})

d <- data.frame(x = (10:60)*50, t1, t2, t3, t4)


ggplot(d, aes(x = x))+
  geom_line(aes(y = t1, col = "'Weighted' eccentricity"))+
  geom_line(aes(y = t2, col = "Weighted distances"))+
  geom_line(aes(y = t3, col = "Unweighted eccentricity"))+
  geom_line(aes(y = t4, col = "Unweighted distances")) +
  scale_x_continuous(name = "Number of Nodes") +
  scale_y_continuous(name = "Time (s)")

As you can see they all have the same time asymptotic complexity, but in the unweighted case the use of BFS gives a better time constant. (To illustrate the asymptotic complexity, see the scaled graph below:)

R: igraph eccentricity seems not use weighed edge

1 Answers