Randomizări de rețele

În exercițiul anterior ai observat, probabil, că lungimea medie a traseului din rețeaua Forrest Gump era mai mică decât cea a rețelei aleatorii. Dacă ai rulat codul de mai multe ori, ai fi constatat că valoarea este aproape întotdeauna mai mică în rețeaua Forrest Gump față de rețeaua aleatorie. Aceasta sugerează că rețeaua Forrest Gump este mai bine interconectată decât fiecare rețea aleatorie, chiar dacă rețelele aleatorii au același număr de vârfuri și densități de graf aproximativ identice. În loc să rulezi codul de mai multe ori, poți aborda această problemă mai riguros: generează 1.000 de grafuri aleatorii pe baza numărului de vârfuri și a densității grafului original Forrest Gump, apoi verifică de câte ori lungimea medie a traseului grafurilor aleatorii este mai mică decât cea a rețelei originale Forrest Gump. Aceasta se numește test de randomizare.

Graful g și lungimea sa medie a traseului (calculată în exercițiul anterior), g.apl, se află deja în spațiul tău de lucru.

Acest exercițiu face parte din cursul

Analiza rețelelor în R

Vezi cursul

Instrucțiuni pentru exercițiu

Generează 1.000 de grafuri aleatorii pornind de la graful original g, executând codul care creează obiectul de tip listă gl și bucla for.
Calculează lungimea medie a traseului pentru cele 1.000 de grafuri aleatorii folosind lapply(). Creează un vector gl.apls cu cele 1.000 de valori, executând codul care utilizează unlist().
Trasează o histogramă a lungimilor medii ale traseului pentru cele 1.000 de grafuri aleatorii, aplicând hist() pe vectorul gl.apls. Adaugă o linie verticală roșie punctată în grafic folosind abline(), cu interceptul pe axa x egal cu valoarea lungimii medii a traseului din graful original, g.apl.
Calculează proporția cazurilor în care valorile lungimii medii a traseului grafurilor aleatorii gl.apls sunt mai mici decât valoarea grafului original g.apl. Aceasta reprezintă, în esență, probabilitatea de a obține lungimea medie a traseului observată doar prin întâmplare, date fiind densitatea și numărul de vârfuri ale grafului original.

Exercițiu interactiv practic

Încearcă acest exercițiu completând acest cod de exemplu.

library(igraph)

# Generate 1000 random graphs
gl <- vector('list', 1000)
  
for(i in 1:1000){
  gl[[i]] <- erdos.renyi.game(n = gorder(g), p.or.m = gd, type = "gnp")
}

# Calculate average path length of 1000 random graphs
gl.apls <- unlist(lapply(gl, ___, directed = FALSE))

# Plot the distribution of average path lengths
___(gl.apls, xlim = range(c(1.5, 6)))
abline(v = ___, col = "red", lty = 3, lwd = 2)

# Calculate the proportion of graphs with an average path length lower than our observed
mean(___ < ___)

Editează și rulează codul