Sujet 1 : Transmission de virus

On cherche à calculer le temps de transmission d’un virus dans une population de N individus avec au départ un seul individu contaminé. Un individu peut transmettre directement le virus seulement à un voisin. On va étudier plusieurs cas : le graphe complet, la ligne 1D et la grille 2D. A mon avis, le temps de propagation avec un graphe complet devrait être assez court, avec une grille 2D moyen et avec une ligne 1D très long.

Q1. Cas du graphe complet

set.seed(80)

# Donne le temps de propagation pour une population de N individus
tn = function(N) {
  population = c(1, rep(0, N-1))
  TN = 0
  
  while (sum(population==1) < N) {
    i = sample.int(N, 2)
    if(sum(population[i]) == 1) {
      population[i] = 1
    }
    TN = TN+1
  }
  
  returnValue(TN)
}

# Donne une moyenne de temps de propagation pour une population de N individus avec rep répétitions
moyenne_tn = function(N, rep) {
  res = c()
  for (i in 1:rep) {
    res = c(res, tn(N))
  }
  returnValue(mean(res))
}

# Affiche les points TN en fonction de N
plot_tn = function(vect_N, rep) {
  data = c()
  for (i in vect_N) {
    moyenne = moyenne_tn(i, rep)
    data = c(data, moyenne)
  }
  plot(vect_N, data, xlab = 'N', ylab = 'TN')
  title('TN en fonction de N pour un graphe complet')
}

plot_tn(seq(from=20, to=500, by=20), 10)

On remarque que TN semble être linéaire. On va s’en assurer en calculant l’espérance de TN.

La probabilité de contaminer une nouvelle personne sachant qu’il y a déjà i personnes contaminées vaut : P = (i(N-i)) / (N(N-1)/2)

On peur maintenant calculer l’espérance de TN.

# Calcule l'espérance de TN en fonction de N
esperance_tn = function(N) {
  somme = 0
  for (i in 1:(N-1)) {
    somme = somme + (N*(N-1)/2) / (i*(N-i))
  }
  returnValue(somme)
}

# Affiche la courbe de l'espérance de TN
plot_esperance_tn = function(vect_N) {
  data = c()
  for (i in vect_N) {
    data = c(data, esperance_tn(i))
  }
  plot(vect_N, data, xlab = 'N', ylab = 'TN', type = 'l')
  title('Espérance de TN')
}

plot_esperance_tn(seq(from=2, to=502, by=100))

Cela confirme nos observations.

Q2. Graphe ligne 1D et grille 2D

# Donne le temps de propagation pour une population de N individus
tn1D = function(N) {
  population = c(1, rep(0, N-1))
  population = sample(population)
  TN = 0
  
  while (sum(population==1) < N) {
    i = sample.int(N-1, 1)
    i = c(i, i+1)
    if(sum(population[i]) == 1) {
      population[i] = 1
    }
    TN = TN+1
  }
  
  returnValue(TN)
}


# Donne une moyenne de temps de propagation pour une population de N individus avec rep répétitions
moyenne_tn1D = function(N, rep) {
  res = c()
  for (i in 1:rep) {
    res = c(res, tn1D(N))
  }
  returnValue(mean(res))
}

# Affiche les points TN en fonction de N
plot_tn1D = function(vect_N, rep) {
  data = c()
  for (i in vect_N) {
    moyenne = moyenne_tn1D(i, rep)
    data = c(data, moyenne)
  }
  plot(vect_N, data, xlab = 'N', ylab = 'TN')
  title('TN en fonction de N pour une ligne 1D')
}

plot_tn1D(seq(from=50, to=500, by=50), 3)

On observe un temps TN largement supérieur avec une ligne 1D qu’avec un graphe complet.

# Donne le temps de propagation pour une population de N individus
tn2D = function(N) {
  population = c(1, rep(0, N-1))
  population = sample(population)
  cote = sqrt(N)
  TN = 0
  
  while (sum(population==1) < N) {
    i = sample.int(N, 1)
    voisins = c()
    
    if(i > cote) { # pas en haut
      voisins = c(voisins, i-cote)
    }
    if(i <= N-cote) { # pas en bas
      voisins = c(voisins, i+cote)
    }
    if(i%%cote > 0) { # pas à droite
      voisins = c(voisins, i+1)
    }
    if(i%%cote != 1) { # pas à gauche
      voisins = c(voisins, i-1)
    }
    i = c(i, sample(voisins, 1))
    
    if(sum(population[i]) == 1) {
      population[i] = 1
    }
    TN = TN+1
  }
  
  returnValue(TN)
}


# Donne une moyenne de temps de propagation pour une population de N individus avec rep répétitions
moyenne_tn2D = function(N, rep) {
  res = c()
  for (i in 1:rep) {
    res = c(res, tn2D(N))
  }
  returnValue(mean(res))
}

# Affiche les points TN en fonction de N
plot_tn2D = function(vect_N, rep) {
  data = c()
  for (i in vect_N) {
    moyenne = moyenne_tn2D(i, rep)
    data = c(data, moyenne)
  }
  plot(vect_N, data, xlab = 'N', ylab = 'TN')
  title('TN en fonction de N pour un grille 2D')
}

plot_tn2D(seq(from=4, to=22, by=2)^2, 10)

On voit que le temps TN est supérieur au graphe complet mais inférieur à la ligne 1D. Cela confirme mon intuition de départ.