Randomizacje sieci

W poprzednim ćwiczeniu mogło się okazać, że średnia długość ścieżki w sieci Forresta Gumpa jest mniejsza niż w sieci losowej. Jeśli uruchamiałeś kod kilka razy, z pewnością zauważyłeś, że niemal zawsze jest ona niższa w sieci Forresta Gumpa. Sugeruje to, że sieć Forresta Gumpa jest bardziej wzajemnie powiązana niż poszczególne sieci losowe – nawet jeśli te ostatnie mają taką samą liczbę wierzchołków i niemal identyczną gęstość grafu. Zamiast wielokrotnie powtarzać ten kod, możesz przeprowadzić bardziej formalną analizę: wygeneruj 1000 losowych grafów opartych na liczbie wierzchołków i gęstości oryginalnego grafu Forresta Gumpa, a następnie sprawdź, ile razy średnia długość ścieżki w grafach losowych jest mniejsza niż w oryginalnej sieci. Taki test nazywa się testem randomizacyjnym.

Graf g oraz jego średnia długość ścieżki (obliczona w poprzednim ćwiczeniu) g.apl są dostępne w twoim środowisku roboczym.

To ćwiczenie jest częścią kursu

Analiza sieci w R

Zobacz kurs

Instrukcje do ćwiczenia

Wygeneruj 1000 losowych grafów na podstawie oryginalnego grafu g, wykonując kod tworzący obiekt listy gl oraz pętlę for.
Oblicz średnią długość ścieżki dla 1000 losowych grafów za pomocą lapply(). Utwórz wektor gl.apls z tych 1000 wartości, wykonując kod korzystający z unlist().
Narysuj histogram średnich długości ścieżek dla 1000 losowych grafów, wywołując hist() na wektorze gl.apls. Dodaj do wykresu czerwoną przerywaną linię pionową za pomocą abline(), gdzie punkt przecięcia z osią x to wartość średniej długości ścieżki oryginalnego grafu, g.apl.
Oblicz proporcję przypadków, w których wartości średniej długości ścieżki losowych grafów gl.apls są niższe od wartości dla oryginalnego grafu g.apl. Jest to w istocie prawdopodobieństwo, że zaobserwowana średnia długość ścieżki mogłaby pojawić się losowo, przy danej gęstości i liczbie wierzchołków oryginalnego grafu.

Interaktywne ćwiczenie praktyczne

Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.

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(___ < ___)

Edytuj i uruchom kod