Sujet 2 : Communication dans une grille non fiable

L’objectif de ce sujet est d’évaluer la connexité d’un réseau non fiable. Le réseau est constitué d’une grille 2D où chaque nœud interne est connecté à 4 voisins. Malheureusement les liens entre les voisins ne sont pas fiables et peuvent tomber en panne.

On suppose qu’un lien est en panne avec la probabilité 1 − p et on s’intéresse à l’ensemble des nœuds connectés au nœud (0,0).

. Q1. Algorithme de génération Écrire un algorithme qui génère une grille [−n, n] × [−n, n] et dont les liens sont en panne avec la probabilité (1 − p).

. Q2. Connectivité Étudier pour un n fixé et suffisamment grand, en fonction de p le nombre de nœuds connectés au nœud (0,0).

En particulier, vous vous poserez la question de l’existence d’une probabilité critique pc telle que si p < pc le nombre de nœuds connectés au nœud (0,0) est supérieur à n² (i.e., moralement aussi grand que le graphe tout entier).

Intuition

La première intuition qui peut être faite est que pour un n (demi-taille de la grille) fixé et suffisamment grand, lorsque p augmente, le nombre de noeuds connectés au noeud (0,0) sera plus élevé et inversemement car la probabilité qu’un lien soit en panne est de 1 - p. C’est à dire si p augmente, un lien entre 2 noeuds a moins de chance de tomber en panne et donc peut potentiellement augmenter le nombre de noeuds connectés à (0,0) car plus de noeuds sont connectés entre eux.

A partir d’un certain seuil pour p, on peut penser que tous les noeuds seront connectés au noeud (0,0) car il y aurait assez de liens pour couvrir tout le graphe.

Pour effectuer les simulations, on fixe la graine pour la génération aléatoire.

set.seed(42);

Question 1 : Algorithme de génération

Afin d’étudier la connexité dans le graphe, nous allons utiliser une matrice d’adjacence.

matriceAdjacence = function(n, probaConnexion) {
  
  tailleGrille = 2 * n + 1;
  tailleMatrice = tailleGrille^2;
  
  #Génération de la matrice
  matrice <- matrix(data = 0, nrow = tailleMatrice, ncol = tailleMatrice);
  
  #Calcul des liens des noeuds
  for(i in 1:tailleMatrice) {
    if(i %% tailleGrille != 0){
      matrice[i, i+1] = rbinom(n = 1, size = 1, prob = probaConnexion);
      matrice[i+1, i] = matrice[i, i+1];
    }
    if( (i + tailleGrille) <= tailleMatrice){
      matrice[i, i + tailleGrille] = rbinom(n = 1, size = 1, prob = probaConnexion);
      matrice[i + tailleGrille, i] = matrice[i, i + tailleGrille];
    }
  }
  
  return (matrice);
}

Question 2 : Connectivité

On calcule le nombre de noeuds connectés au noeud (0,0).

connexionCentre = function(matrice) {
  
  #On récupère la taille de la matrice
  tailleMatrice = sqrt(length(matrice));
  
  #Le numéro de sommet du centre
  centre = (tailleMatrice / 2) + 1;
  
  #Matrice des sommets visités
  tempMatrice = matrix(data = rep(0,tailleMatrice), nrow = tailleMatrice);
  
  #On cherche les voisins du centre
  X1 = rep(0,tailleMatrice);
  X1[centre] = 1;
  X2 = matrix(data = X1, nrow = tailleMatrice);
  
  #Boucle tant qu'on a pas visité tous les voisins
  while(!identical(X2, tempMatrice)) {
    #Mise ) jour des sommets visités
    tempMatrice = X2;
    X3 = ((matrice %*% X2)) != 0;
    #Ajout des voisins dans le calcul de l'ensemble des voisins
    temp = which(X2 != (X3));
    for (i in temp) {
      X2[i] = 1;
    }
  }
  
  return (sum(X2)-1);
}

On effectue des tests sur des cas simples pour voir que ça fonctionne.

matrice = matriceAdjacence(1, 0.2);
matrice;
##       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
##  [1,]    0    1    0    1    0    0    0    0    0
##  [2,]    1    0    0    0    1    0    0    0    0
##  [3,]    0    0    0    0    0    0    0    0    0
##  [4,]    1    0    0    0    0    0    0    0    0
##  [5,]    0    1    0    0    0    0    0    0    0
##  [6,]    0    0    0    0    0    0    0    0    0
##  [7,]    0    0    0    0    0    0    0    0    0
##  [8,]    0    0    0    0    0    0    0    0    0
##  [9,]    0    0    0    0    0    0    0    0    0
connexionCentre(matrice);
## [1] 3

En faisant le calcul à la main, tout a l’air de fonctionner. On va maintenant passer à des n plus grands. Et faire une étude sur le nombre de noeuds connectés à (0,0) par rapport à p (probabilité d’avoir une connexion).

n = 10;
iteration = 30;
nbConnexionVect = c();

for (i in 1:100) {
  
  nbConnexion = 0;
  
  for (j in 1:iteration) {
      matrice = matriceAdjacence(n, i/100);
      nbConnexion =  nbConnexion + connexionCentre(matrice);

  }
  nbConnexionVect[i] = nbConnexion/iteration;
}
  plot((1:100)/100, nbConnexionVect, main='Nombre de noeuds connectés en fonction de p', xlab = "p", ylab = "nbNoeux");

On remarque trois phases : une premier phase pour p entre 0 et 0.4 où il y a peu de noeuds connectés au noeud central; Une deuxième phase entre 0.4 et 0.7 où le nombre de noeuds connecté augmente beaucoup; Une troisième phase entre 0.7 et 1 où le nombre de noeuds connectés aussi grand que le graphe entier.

Il y a donc bien l’existence d’une probabilité critique. Considérant p la probabilité qu’il y ait une connexion, pc serait plutôt une borne inférieur à p et serait aux alentours de 0.7.