R：的igraph偏心似乎不使用称重边缘

我使用的igraph计算顶点偏心，图形被加权，并且如以下R：的igraph偏心似乎不使用称重边缘

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

它是一个小世界网络，用500个顶点随机生成的，并且随机加权边缘。使用diameter和'is.weighted'来检查它是否加权。然而，eccentricity不使用权重，以及生成以下结果，

d_list <- eccentricity(g) 
summary(d_list)

输出如下，

d_list < - 偏心率（克）
摘要（d_list）
最小。第一曲。中位数均值3曲。最大。
4.000 4.000 4.000 4.004 4.000 5.000

如何解决这个问题？

现在我用max(distances(g))来解决它，但我认为它不是一个高效和优雅的方式。

来源

2016-07-29 bourneli

我不认为偏心给你的选择，但如果我不会发出自己关于distance（）方法的优点，从效率的角度来看，这两种算法都将在O(|V|^2*log(|V|))（假设|E| = O(|V|)）中执行以计算每个节点的偏心率，如果你运行一些测试，你会得到：

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)")

正如你可以看到它们都具有相同的时间渐近复杂性，但在未加权的情况下，使用BFS的给出了一个更好的时间常数。（为了说明渐近的复杂性，请参见下面的缩放图:)

来源

2016-07-29 06:31:21 user1470500

R：的igraph偏心似乎不使用称重边缘

回答

相关问题