Le virus

Présentation #

Comment une épidémie se propage-t-elle dans un réseau ? Cette question apparaît dans de nombreux domaines : diffusion de virus biologiques, propagation d’informations sur les réseaux sociaux, pannes dans des réseaux informatiques ou encore influence et propagation de rumeurs au sein d’un groupe de personnes.

Dans ce projet, nous travaillons sur la contamination de cellules de proche en proche. On représente notre situation par un graphe où des cellules sont connectées les unes aux autres. Certaines cellules sont contaminées au départ. À chaque étape, une cellule saine devient contaminée lorsqu’au moins un certain nombre de ses voisines sont déjà contaminées. Par exemple, dans un premier modèle, on peut étudier le cas simple où notre graphe est une grille et où une cellule se contamine lorsque la moitié de ses voisines le sont déjà. Sur l’image, on peut voir une grille avec deux cellules contaminées. À la prochaine étape, leurs voisines communes vont se contaminer et on aura 4 cellules malades au total.

À partir de cette règle simple émergent des comportements parfois surprenants : une petite poignée de cellules initialement contaminées peut parfois suffire à contaminer l’ensemble du graphe, tandis que d’autres configurations beaucoup plus importantes échouent à se propager.

Objectif #

L’objectif du projet est de comprendre et d’étudier la propagation de la contamination dans différents réseaux.

On cherchera notamment à répondre aux questions suivantes :

• Où placer les cellules contaminées au départ pour que toute la population soit finalement contaminée ?
• Quel est le nombre minimal de cellules initialement contaminées permettant de contaminer tout le réseau ?
• Comment ce nombre dépend-il de la taille du réseau ou des règles de contamination ?

Une première étape consistera à programmer la simulation de la propagation sur une grille carrée. On pourra ensuite tester différentes configurations initiales et observer leur évolution.

De nombreuses variantes du problème pourront être étudiées :

• Une cellule est contaminée lorsque au moins la moitié de ses voisines le sont.
• Une cellule est contaminée lorsque toutes ses voisines sauf une sont contaminées.
• …

On pourra étudier différentes formes de réseaux : grilles carrées, grilles triangulaires, graphes aléatoires, etc, et y rechercher les motifs minimaux de contamination.

Équipe encadrante #

Aline Parreau, Isaline Plaid, Théo Pierron, Laurent Feuilloley, Quentin Deschamps, Arthur Dumas.

Code #

Une première étape consistera à programmer la simulation de la propagation sur une grille carrée. On pourra ensuite tester différentes configurations initiales et observer leur évolution. Cela pourra se faire en Python.

Disponibilités #

Un membre de l’équipe encadrante passera chaque demi-journée.