DM2_PS
Estelle ALLARD RICM4
Pour le 3 janvier 2017
Sujet 1 : Transmission de virus
Notre propagation de virus sera établie par un tirage uniforme de deux individus. Si au l’un des deux est infecté alors l’autre sera contaminé.
Dans notre sujet nous avons : N la taille de la population: qui correspond donc au nombre de sommets sur le graphe. Tn le temps nécessaire pour que toute la population soit infectée. Il nous est nécessaire d’initialiser la graine et de déclarer nos librairies utilisées.
set.seed(42);
library(ggplot2)Question 1 : Cas du graphe complet
Le caractère de graphe complet nous impose que chaque individu est relié à exactement N-1 individus. (N étant la taille de la population). Il est évident (à mon avis) que le temps de contamination sera d’autant plus grand si le nombre N l’est. La valeur de Tn augmente dès que deux individus rentrent en contact. Notre modèle sera donc le fait de tirer deux individus aléatoirement et de leur imposer la loi de contamination déterminée dans le sujet et ci dessus.
graphe_complet=function(N){
population = rep(0,N);
nb=sample.int(N,1);
x=sample(1:N,nb); #choix aléatoire des individus contaminés au départ
#Initialisation de ces personnes contaminées
for (i in 1:nb){
population[x[i]]=1;
}
Tn=0; #temps nécessaire pour que la totalité de la population soit infectée
#Détermination de la loi de propagation
while(!setequal(population,1)){ #setequal nous permet de vérifier si toutes les valeurs de population sont à 1, c'est à dire si tous les individus sont contaminés
#On tire aléatoirement deux individus de la population / en vérifiant à ne pas tirer deux fois le même individu
f=sample(1:N,1);
s=sample(1:N,1);
while(f==s){ #si on tire les deux même individus
s=sample(1:N,1);
}
if (population[f]!=population[s]){#si l'un des deux est contaminé
population[f]=1;
population[s]=1; #On s'assure que les deux sont alors contaminé;
}
Tn = Tn +1; #on augmente le temps de contamination;
}
return(Tn); #on retourne le temps de propagation
}
graphe_complet(100);## [1] 125Je remarque après plusieurs tentatives que les temps sont variables. Je décide donc de déteminer un temps moyen.
temps_moy=function(N,r){
#soit r le nombre de répétition de l'expérience
l=c();
for (i in 1:r){
l[i]=graphe_complet(N);
}
mean(l); #nous permet de calculer directement la moyenne de la liste des temps Tn.
}
temps_moy(100,100);## [1] 253.14Pour une visualisation plus facile nous allons représenter le temps de contamination Tn en fonction du nombre N d’individus dans la population. Mon intuition est la suivante : la temps de propagation sera proportionnel au nombre d’individus à contaminer.
complet=function(r,point){ #point correspondant aux valeurs de notre représentation graphique
df=data.frame();
for (i in 1:point){
N=i*20
moy=temps_moy(N,r);
df=rbind(df,data.frame(N,moy));
}
return (df);
}
tot=complet(100,15);
plot(tot$N,tot$moy,xlab="Nombre d'individus",ylab="Temps de contamination moyen");
On remarque donc bien l’aspect proportionnel entre N et Tn.
Espérance
En posant X la variable aléatoire qui détermine l’état de contamination d’un individu (0 ou 1) on remarque que X suit une loi de Bernouilli de paramètre p étant la probabilité de contamination. Notre probabilité dépend des liaisons entre les individus. Nous avons un graphe complet donc le nombre total de liens entre les individus (les arêtes) est de N(N-1)/2. Sachant que l’on a i personnes contaminées on peut en déduire la formule de probabilité suivante :
N=100; #le nb d’individus.
p=i(N-i)/N(N-1)/2; #i étant le nombre de personnes contaminées.
Notre espérence de Tn est donc la suivante :
espe=function(N){
a=0;
b=N-1;
for (i in 1:b){
a=a+((N*(N-1)/2)/(i+(N-i)));
}
return (a);
}
espe(100);## [1] 4900.5Question 2 : Graphe ligne 1D et grille 2D
Ligne 1D
Dans ce nouveau modèle de ligne 1D on ne peut plus se permettre de tirer au hasard les couples. Mais il s’agit de tirer un seul individu puis d’observer ses voisins, auxquels il est relié. Il parait probable que si le premier individu contaminé est situé en bout de ligne alors le temps de contamination sera d’autant plus long que si l’individu contaminé en premier se trouve au milieu de la ligne.
ligne_1D=function(N){
init=sample.int(N,1);#on tire aléatoirement le premier individu contaminé
population=rep(0,N);
population[init]=1; #on initialise l'individu contaminé
Tn=0;
while (!setequal(population,1)){
f=sample(1:N,1); #on tire un individu au hasard
if(f==1){#cas où l'individu tiré est le premier de la ligne
s=f+1;
}
else if(f==N){#cas où l'individu tiré est le dernier de la ligne
s=f-1;
}
else s=sample(c(f-1,f+1),1); #sinon on tire au hasard son voisin droite ou gauche pour choisir le second individu
if (population[f]!=population[s]){
population[f]=1;
population[s]=1;
}
Tn= Tn+1;
}
return(Tn);
}
ligne_1D(100);## [1] 7603De même que précédemment nous allons calculer le temps moyen. Ainsi que tracé le graphe de Tn en fonction de N.
temps_moy_1D=function(N,r){
#soit r le nombre de répétition de l'expérience
l=c();
for (i in 1:r){
l[i]=ligne_1D(N);
}
mean(l); #nous permet de calculer directement la moyenne de la liste des temps Tn.
}
temps_moy_1D(100,100);## [1] 7586.5graphe_1D=function(r,point){ #point correspondant aux valeurs de notre représentation graphique
df=data.frame();
for (i in 1:point){
N=i*20
moy=temps_moy_1D(N,r);
df=rbind(df,data.frame(N,moy));
}
return (df);
}
tot=graphe_1D(10,15);
plot(tot$N,tot$moy,xlab="Nombre d'individus",ylab="Temps de contamination moyen");
On remarque une fois de plus la proportionnalité entre le nombre d’invidus et le temps de contamination moyen. Cependant pour un graphe complet le temps de contamination moyen pour N=300 individus était d’environ 1000. Tandis qu’il est de plus de 60 000 pour le graphe de contact en ligne unidimensionnelle. Il est donc 60 fois plus long de contaminer l’intégralité de la population en ligne unidimensionnelle qu’en graphe complet.
Regardons la dépendance de l’individu infecté au départ.
ligne_1D_ind=function(N,init){
population=rep(0,N);
population[init]=1; #on initialise l'individu contaminé
Tn=0;
while (!setequal(population,1)){
f=sample(1:N,1); #on tire un individu au hasard
if(f==1){#cas où l'individu tiré est le premier de la ligne
s=f+1;
}
else if(f==N){#cas où l'individu tiré est le dernier de la ligne
s=f-1;
}
else s=sample(c(f-1,f+1),1); #sinon on tire au hasard son voisin droite ou gauche pour choisir le second individu
if (population[f]!=population[s]){
population[f]=1;
population[s]=1;
}
Tn= Tn+1;
}
return(Tn);
}
temps_moy_1D_ind=function(N,r,init){
#soit r le nombre de répétition de l'expérience
l=c();
for (i in 1:r){
l[i]=ligne_1D_ind(N,init);
}
mean(l); #nous permet de calculer directement la moyenne de la liste des temps Tn.
}
indiv_infect=function(r,N){
df=data.frame();
for (i in 1:(N/2)){
p=i*2;
moy=temps_moy_1D_ind(N,r,p);
df=rbind(df,data.frame(p,moy));
}
return(df);
}
tot=indiv_infect(10,100);
plot(tot$p,tot$moy,xlab="Numéro du premier individu infecté",ylab="Temps de contamination moyen");
On constate donc bien la vérification de la supposition faite plus haut. Plus l’individu infecté en premier est loin du centre de la ligne plus le temps de contamination est élevé.
Grille 2D
Nous effectuons à nouveau l’analyse du problème mais sur une grille 2D de côté sqrt(N). Le principe reste le même mais nous avons à vérifier plusieurs cas lors de la loi de contamination, suivant la position de l’individu tiré au hasard.
grille_2D=function(N,init){
population=rep(0,N);
population[init]=1; #on initialise l'individu contaminé
Tn=0;
cote=sqrt(N);
while (!setequal(population,1)){
f=sample(1:N,1); #on tire un individu au hasard
#Bord gauche
if (f%%cote==1){
if(f==1){#haut
s=sample(c(f+cote,f+1),1);
}
else if(f==(N-cote+1)){#bas
s=sample(c(f-cote,f+1),1);
}
else {#milieu
s=sample(c(f-cote,f+1,f+cote),1);
}
}
#Bord droit
else if (f%%cote==0){
if(f==cote){#haut
s=sample(c(f+cote,f-1),1);
}
else if(f==N){#bas
s=sample(c(f-cote,f-1),1);
}
else {#milieu
s=sample(c(f-cote,f-1,f+cote),1);
}
}
#Bord haut
else if (f<=cote){
s=sample(c(f-1,f+cote,f+1),1);
}
#Bord bas
else if (f>(N-cote)){
s=sample(c(f-1,f-cote,f+1),1);
}
else{#centre
s=sample(c(f-1,f-cote,f+1,f+cote),1);
}
if (population[f]!=population[s]){
population[f]=1;
population[s]=1;
}
Tn= Tn+1;
}
Tn;
}
grille_2D(100,1);## [1] 1679temps_moy_2D=function(N,r,init){
#soit r le nombre de répétition de l'expérience
l=c();
for (i in 1:r){
l[i]=grille_2D(N,init);
}
mean(l); #nous permet de calculer directement la moyenne de la liste des temps Tn.
}
grille=function(r,N){
df=data.frame();
for (i in 1:(N/5)){
p=i*5;
moy=temps_moy_2D(N,r,p);
df=rbind(df,data.frame(p,moy));
}
return(df);
}
tot=grille(10,100);
plot(tot$p,tot$moy,xlab="Numéro du premier individu infecté",ylab="Temps de contamination moyen");
On remarque alors que pour cette conception de la population ne permet pas d’établir une relation entre le numéro du premier individu infecté et le temps de propagation.
Cependant, dans cette configuration on constate un temps Tn maximum de 1400 donc légèrement supérieur au graphe complet mais fortement inférieur à la ligne 1D.