R：的igraph偏心似乎不使用稱重邊緣

Question

我使用的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))來解決它，但我認爲它不是一個高效和優雅的方式。

Answer 1

我不認爲偏心給你的選擇，但如果我不會發出自己關於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的給出了一個更好的時間常數。 （爲了說明漸近的複雜性，請參見下面的縮放圖:)