Randomizace sítí

V předchozím cvičení sis možná všiml/a, že průměrná délka cesty v síti Forrest Gump byla menší než průměrná délka cesty náhodné sítě. Pokud jsi kód spustil/a vícekrát, pravděpodobně sis všiml/a, že je téměř vždy nižší v síti Forrest Gump než v náhodné síti. To naznačuje, že síť Forrest Gump je propojenější než jednotlivé náhodné sítě, přestože mají stejný počet vrcholů a přibližně stejnou hustotu grafu. Místo opakovaného spouštění kódu můžeš tuto otázku formálněji zodpovědět tak, že vytvoříš 1 000 náhodných grafů vycházejících z počtu vrcholů a hustoty původního grafu Forrest Gump. Pak zjistíš, kolikrát je průměrná délka cesty náhodných grafů menší než v původní síti Forrest Gump. Tomuto postupu se říká randomizační test.

Graf g a jeho průměrná délka cesty (vypočítaná v předchozím cvičení) g.apl jsou dostupné ve tvém pracovním prostoru.

Toto cvičení je součástí kurzu

Analýza sítí v R

Zobrazit kurz

Pokyny k cvičení

Vygeneruj 1 000 náhodných grafů z původního grafu g spuštěním kódu, který vytváří listový objekt gl a příslušnou smyčku for.
Vypočítej průměrnou délku cesty pro všech 1 000 náhodných grafů pomocí lapply(). Spuštěním kódu využívajícího unlist() vytvoř vektor gl.apls s těmito 1 000 hodnotami.
Vykresli histogram průměrných délek cest 1 000 náhodných grafů pomocí hist() aplikovaného na vektor gl.apls. Do grafu přidej červenou přerušovanou svislou čáru pomocí abline(), přičemž průsečík s osou x bude odpovídat hodnotě průměrné délky cesty původního grafu g.apl.
Vypočítej podíl případů, kdy jsou hodnoty průměrné délky cesty náhodných grafů gl.apls nižší než hodnota původního grafu g.apl. Jde v podstatě o pravděpodobnost, s jakou bychom mohli pozorovanou průměrnou délku cesty očekávat náhodně při dané hustotě a počtu vrcholů původního grafu.

Interaktivní cvičení na vyzkoušení si v praxi

Vyzkoušejte si toto cvičení dokončením tohoto ukázkového kódu.

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

Upravit a spustit kód