R: IGRAPH Exzentrizität scheint nicht Kante gewogen verwenden

Question

I verwenden IGRAPH den Eckpunkten Exzentrizität zu berechnen, wird der Graph gewichtet und zufällig erzeugt wird, wie folgt

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 

Es ist ein kleines Weltnetz, mit 500 Vertices und zufällige gewichtete Kanten. Verwenden Sie diameter und "is.weighted", um zu überprüfen, ob es gewichtet ist. Jedoch eccentricity nicht das Gewicht, verwenden und erzeugen das folgende Ergebnis,

d_list <- eccentricity(g) 
summary(d_list) 

Ausgang, wie folgend,

d_list < - Exzentrizität (g)
Zusammenfassung (d_list)
Min. 1. Qu. Mittlerer Mittelwert 3rd Qu. Max.
4,000 4,000 4,000 4,004 4,000 5,000

, wie dieses Problem zu lösen?

jetzt verwende ich , um es zu lösen, aber ich denke, es ist kein effizienter und eleganter Weg.

Answer 1

Ich glaube nicht Exzentrizität geben Ihnen die Möglichkeit, aber wenn ich mich nicht über die elegancy der Abstände ausspricht() -Methode von einem Wirkungsgrad Sicht werden beide Algorithmen ausführen in O(|V|^2*log(|V|)) (unter der Annahme |E| = O(|V|)) berechnen die Exzentrizität jedes Knotens, wenn Sie einige Test laufen Sie diese:

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

Wie Sie alle haben die gleiche Zeit asymptotisch Komplexität sehen kann, aber in dem ungewichteten Fall ergibt die Verwendung von BFS ein bessere Zeitkonstante. (Um die asymptotische Komplexität zu veranschaulichen, siehe das skalierte Diagramm unten)