Randomisations de réseaux

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 faible 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 basse 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 chaque réseau aléatoire, même si ces réseaux aléatoires 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 cela plus formellement en créant 1000 graphes aléatoires basés sur le nombre de sommets et la densité du graphe Forrest Gump d’origine. 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. C’est ce qu’on appelle un test de randomisation.

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

Cet exercice fait partie du cours

Analyse de réseaux avec R

Afficher le cours

Instructions

Générez 1000 graphes aléatoires à partir du graphe original g en exécutant le code qui crée la liste gl ainsi que 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 appliquant hist() au vecteur gl.apls. Ajoutez une ligne verticale rouge en tirets au graphique avec abline(), en prenant pour intercept sur l’axe des x 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. Il s’agit en substance de la probabilité d’observer par hasard notre longueur moyenne des plus courts chemins, compte tenu de la densité et du nombre de sommets du graphe d’origine.

Exercice interactif pratique

Essayez cet exercice en complétant cet exemple de code.

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