DM2 : Topologie d’internet

Introduction

Ce devoir maison consiste à analyser des données réelles récuprées à partir d’observations sur une topologie de machine créant un réseau internet. On veut trouver une méthode théorique permettant de recréer une topologie internet approchant les faits réels.

Qestion 1 : Estimation de la structure d’Internet à partir du graphique

D’après le graphique fournit en annexe de l’énoncé, le graphe internet analysé comportait à peu près 3000 noeuds.

Une formule permettant de calculer le degré d’un noeud du graphe selon son rang est donné en annexe : exp(6,34763)*x**(-0,811392).

nb_noeud <- 3000
moy <- 0

for(x in 1:nb_noeud)
{
  moy = moy + (exp(6.34763)*x**(-0.811392))
}

moy = moy / nb_noeud

moy

## [1] 3.667533

On obtient une moyenne du degré des noeuds de 3.66 par noeud.

Qestion 2 : Distribution du degré pour Graphe Erdös-Renyi

nb_noeud = 3000
nb_arr_cur = 0
p = 0.25
deg <- c()
mat_arr <- matrix(ncol = nb_noeud, nrow = nb_noeud)

for(i in 1:nb_noeud)
{
  deg[i] = 0
}

for(i in 1:(nb_noeud-1))
{
  for(j in (i+1):nb_noeud)
  {
    d = runif(1)
    if(d <= p){
      mat_arr[i, j] = 1
      deg[i] = deg[i] + 1
      deg[j] = deg[j] + 1
      nb_arr_cur = nb_arr_cur + 1
    }
    else{
      mat_arr[i, j] = 0
    }
  }
}

deg_sorted = sort(deg, decreasing = TRUE)

plot(deg_sorted, main = "Modèle de Erdös-Renyi", ylab = "Degré", xlab = "Index")

Ce modèle ne ressemble pas à une loi de puissance de la forme a*x**k.

Voilà la même courbe mais en échelle logarithmique.

plot(deg_sorted, main = "Modèle de Erdös-Renyi (log)", ylab = "Degré", xlab = "Index", log="xy")

La moyenne des degrés des noeud de cet essai est :

2*nb_arr_cur/nb_noeud

## [1] 749.4407

Ci-dessous est représenté un boxplot.

boxplot(deg_sorted, main = "Boxplot du modèle de Erdös-Renyi", ylab = "Degré")

On voit clairement que les degrés sont disposés à peu près uniformément autour de la médiane qui s’avère être la moyenne

Enfin on s’aperçoit que la moyenne que l’on trouve est p*nb_noeud avec p la probabilité de créer un lien (1/4 dans notre cas) et nb_noeud le nombre de noeuds du graphe (3000 ici).

Qestion 3 : Modèle de Barabási-Albert

nb_noeud = 3000
nb_arr_cur = 1
p = 0
deg <- c(1, 1)
mat_arr <- matrix(ncol = nb_noeud, nrow = nb_noeud)
mat_arr[1, 2] = 1

for(i in 3:nb_noeud)
{
  deg[i] = 0
}

for(i in 3:nb_noeud)
{
  for(j in 1:(i-1))
  {
    d = runif(1)
    p = deg[j]/(2*nb_arr_cur)
    if(d <= p){
      mat_arr[j, i] = 1
      deg[i] = deg[i] + 1
      deg[j] = deg[j] + 1
      nb_arr_cur = nb_arr_cur + 1
    }
    else{
      mat_arr[j, i] = 0
    }
  }
}

deg_sorted = sort(deg, decreasing = TRUE)

plot(deg_sorted, main = "Modèle de Barabási-Albert", ylab = "Degré", xlab = "Index")

Ce modèle ressemble beaucoup plus à une loi de puissance de la forme a*x**k.

Voilà la même courbe mais en échelle logarithmique.

plot(deg_sorted, main = "Modèle de Barabási-Albert (log)", ylab = "Degré", xlab = "Index", log="xy")

## Warning in xy.coords(x, y, xlabel, ylabel, log): 1103 y values <= 0 omitted
## from logarithmic plot

La moyenne des degrés des noeud de cet essai est :

2*nb_arr_cur/nb_noeud

## [1] 1.982667

Ci-dessous est représenté un boxplot.

boxplot(deg_sorted, main = "Boxplot du modèle de Barabási-Albert", ylab = "Degré")

On voit clairement que les degrés sont disposés sont largement bas et que quelques valeurs s’écartent du lot vers le haut jusqu’à un certain maximum assez éloigné de la moyenne.

Enfin on s’aperçoit que la moyenne que l’on obtient avec cette méthode est bien plus proche de la réalité des observations que la méthodes testée en Question 2. Les écarts que l’on peut constater ici en Question 3 avec la réalité peut peut-être s’expliquer par un nombre assez conséquent de noeuds qui résulte avec aucune connexion. Ce sont des points totalement isolés (nombre de points qui peut s’élever à plus de 1/3 du nombre de noeuds initial du test). Pourtant on vois bien ici que cette méthode approche plutôt bien la réalité.

Conclusion

On peut conclure que la deuxième méthode approxime plutôt bien les résultats pratiques, et cela même intuitivement. Au contraire, la première méthode et très loin de la réalité car on ommet dans la probabilité de créer un lien de prendre en compte la popularité des noeuds. C’est ce qui rend le modèle de Barabási-Albert beaucoup plus intéressant dans notre cas.