Randomisations de réseau

Dans l'exercice précédent, vous avez peut‑être remarqué que la longueur moyenne des plus courts chemins du réseau de Forrest Gump était plus petite que celle du réseau aléatoire. Si vous avez exécuté le code plusieurs fois, vous aurez constaté qu'elle est presque toujours plus faible dans le réseau de Forrest Gump que dans le réseau aléatoire. Cela suggère que le réseau de Forrest Gump est plus fortement interconnecté que chacun des réseaux aléatoires, même si ces derniers ont le même nombre de sommets et des densités de graphe approximativement identiques. Plutôt que de relancer ce code de nombreuses fois, vous pouvez traiter la question plus formellement en créant 1000 graphes aléatoires basés sur le nombre de sommets et la densité du graphe Forrest Gump original. Vous pourrez ensuite voir combien de fois la longueur moyenne des plus courts chemins des graphes aléatoires est inférieure à celle du réseau Forrest Gump original. On appelle cela un test de randomisation.

Le graphe g, et sa longueur moyenne des plus courts chemins (que vous avez calculée à l'exercice précédent), g.apl, sont dans votre espace de travail.

Cette activité fait partie du cours

Analyse de réseaux avec R

Voir le cours

Instructions de l’exercice

Générez 1000 graphes aléatoires du graphe original g en exécutant le code qui crée l'objet liste gl et la boucle for.
Calculez la longueur moyenne des plus courts chemins des 1000 graphes aléatoires avec lapply(). Créez un vecteur gl.apls de ces 1000 valeurs en exécutant le code qui utilise unlist().
Tracez un histogramme des longueurs moyennes des plus courts chemins des 1000 graphes aléatoires en utilisant hist() sur le vecteur gl.apls. Ajoutez une ligne verticale pointillée rouge au graphique avec abline(), en prenant pour abscisse la valeur de la longueur moyenne des plus courts chemins du graphe original, g.apl.
Calculez la proportion de fois où les valeurs de la longueur moyenne des plus courts chemins des graphes aléatoires gl.apls sont inférieures à la valeur du graphe original g.apl. C'est essentiellement la probabilité d'observer notre longueur moyenne des plus courts chemins par hasard, étant donné la densité et le nombre de sommets du graphe original.

Exercice interactif pratique

Essayez cet exercice en complétant ce code d’exemple.

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

Modifier et exécuter le code