3.2 TP – Modèle \(G(n,p)\)

Dans ce TP nous allons étudier la question si le modèle \(G(n,p)\) est approprié pour modéliser des graphes issus d’applications.

Modèle \(G(n,p)\) ou modèle de Erdös-Rényi

La fonction sample_gnp() du package igraph permet de simuler un graphe d’Erdös-Rényi. On donne comme paramètres le nombre \(n\) de noeuds et la probabilité \(p\) de connection entre deux noeuds.

Simulons deux graphes différents : un faiblement connecté, et un très connecté :

library("igraph")
set.seed(1)
n <- 40
p1 <- 0.1
p2 <- 0.7
G1 <- sample_gnp(n,p1)
G2 <- sample_gnp(n,p2)
par(mfrow=c(1,2))
plot(G1)
plot(G2)

Exercice 1

  1. [Sans R] Donner un estimateur \(\hat p\) de \(p\) dans le modèle \(G(n,p)\), et rappeler la distribution marginale du degré \(D_i\) du noeud \(i\) dans \(G(n,p)\).
  2. Simuler des graphes \(G(n,p)\) pour différentes valeurs de \(n\) et de \(p\). Pour chaque graphe simulé, évaluez l’estimateur \(\hat p\) et comparez à \(p\). De plus, tracez la distribution empirique des degrés des noeuds et superposez la distribution des degrés attendus sous le modèle \(G(n,p)\). Qu’observez-vous ?

Exercice 2

Reprenez un des graphes réels analysés lors du dernier TP. Quelle est la valeur estimée de \(p\)? Tracez la distribution empirique des degrés des noeuds et superposez la distribution des degrés attendus sous le modèle \(G(n,p)\). Que constatez-vous ?