Epidémiologie dans les petits mondes

Matthieu Martel
 
matthieu.martel@cea.fr

1  Introduction

Dans une lettre à la revue Nature datée de juin 1998 [3], Duncan J. Watts et Steven H. Strogatz ont introduit la notion de petit monde pour caractériser des graphes (aussi appelés réseaux) modélisant des systèmes complexes de nature biologique, sociale, ou technologique. Nous verrons par exemple que le réseau électrique de l'ouest des Etats Unis, le graphe des acteurs ayant joué dans un même film, le graphe des citations entre auteurs d'articles scientifiques ou encore le réseau neuronal du vers Caenorhabditis elegans sont tous des petits mondes.

Pour comprendre l'intérêt des petits mondes, il faut savoir que pour modéliser les interactions entre les composants d'un système complexe, on utilise en général soit des graphes réguliers dans lesquels les noeuds sont de même degré et sont reliés les uns aux autres suivant un même motif (tore, anneau, etc.), soit des graphes aléatoires dans lesquels les noeuds sont reliés les uns aux autres au hasard. Cependant Watts et Strogatz ont constaté que la plupart des réseaux que l'on rencontre dans la vie courante, tels que ceux mentionnés au paragraphe précédent, ne sont ni vraiment réguliers, ni vraiment aléatoires : c'est ce que l'on appellera les petits mondes.

Les réseaux d'amitié sont de bons exemples de petits mondes : une personne rencontrant souvent une autre personne par l'intermédiaire d'une connaissance commune, les réseaux d'amitié sont en général localement ordonnés (si A connaît B et B connaît C, alors A a plus de chances de connaître C qu'une autre personne prise au hasard), sans être réguliers.

Les petits mondes offrant une bonne modélisation des réseaux sociaux, ils présentent un grand intétêt pour l'étude de la diffusion d'une épidémie au sein d'une population. En supposant qu'un individu malade contamine ses voisins dans le réseau à une certaine vitesse, une épidémie se propagera différemment dans un petit monde que dans un autre type de réseau. Les particularités des petits mondes peuvent influencer la stratégie à mettre en place pour éradiquer la maladie.

2  Caractérisation des petits mondes

Pour une description plus détaillée des petits mondes, on se réfèrera à l'article de Watts et Strogatz [3]. Afin de modéliser ces réseaux, ni parfaitement réguliers, ni totalement aléatoires, on introduit une procédure de recablage aléatoire : en partant d'un réseau régulier, on modifie au hasard la destination de chaque arête, avec une faible probabilité p. La figure 1 illustre cette procédure pour un graphe en forme d'anneau, dans lequel chaque noeud est initialement connecté à ses k voisins de l'anneau les plus proches.



Figure 1 : Effets de la procédure de recablage aléatoire (k=2).



Appelons L la longueur moyenne des plus courts chemins entre tous les noeuds d'un graphe G=(V,E) et C la cliquicité de G. C est défini comme suit : soit v un noeud ayant kv voisins Vois(v)⊆ V. Ces voisins ont au plus
K=
kv(kv-1)
2
arêtes entre eux. La cliquicité de v est définie comme étant la proportion de ces arêtes effectivement présentes dans le graphe :
cv=
Card({ (x,y)∈ E : x,y∈ Vois(v)})
K
La cliquicité C du graphe est définie comme étant la moyenne des cliquicités des noeuds qui le composent. Un petit monde est alors défini comme un graphe G non régulier pour lequel
Lreg » LLrandom   et   CregC» Crandom
Lrandom et Crandom (resp. Lreg et Creg) sont la distance moyenne et la cliquicité d'un graphe aléaoire (resp. régulier) ayant le même nombre de sommets et le même nombre d'arêtes que G. Intuitivement, dans un graphe régulier, la longueur moyenne L des plus courts chemins et la cliquicité C sont élevées, tandis que dans un graphe totalement aléatoire, L et C sont faibles. Les petits mondes sont des graphes intermédiaires, dans lesquels L est faible, comme dans les graphes aléatoires et C est élevée, comme dans les graphes réguliers.

Il a été montré que de nombreux systèmes complexes de la vie courante, tels que ceux mentionnés dans l'introduction, avaient les caractéristiques de petits mondes.

3  Propagation d'épidémies dans un réseau

Parce que les petits mondes ont les mêmes caractéristiques que de nombreux systèmes de la vie courante, ils constituent un bon modèle pour étudier la propagation d'influences à travers un réseau. Par exemple, ces influences peuvent être des épidémies se propageant au sein d'une population ou des virus informatiques diffusés par messages électroniques. En ce qui concerne les épidémies [2], on distingue en général deux modes de propagation :
Mode SIR :
dans le mode SIR (Susceptible, Infected, Removed), lorsqu'un individu a été infecté, il est ensuite retiré du réseau.
Mode SIS :
dans le mode SIS (Susceptible, Infected, Susceptible), les individus guérissent de la maladie et sont à nouveau susceptibles de l'attraper.
Certaines maladies se propagent dans une population suivant le mode SIR, tandis que les virus informatiques ont plutôt un mode de propagation de type SIS.

Pour modéliser la propagation d'une maladie dans un réseau, on associe à chaque individu une probabilité t d'infecter un de ses voisins et une probabilité tg d'infecter un non voisin. On peut de plus supposer qu'un individu infecté peut être soigné avec une probabilité c (de façon à ne pas disparaître dans le mode SIR, et à redevenir sain plus rapidement dans le mode SIS). Enfin, un individu peut être immunisé (avec une probabilité i) contre la maladie et ne pas la transmettre, s'il est vacciné par exemple.

En partant d'un ou de plusieurs individus initialement infectés et d'une instance des paramètres décrits dans le paragraphe précédent, on peut alors étudier la façon dont va se propager une maladie. Typiquement, si le ratio τ=t+tg/c est élevé la maladie s'étendra à l'ensemble de la population tandis qu'elle s'éteindra si τ est faible, indépendamment de la structure du réseau. En revanche, pour des valeurs intermédiaires de τ, la dynamique dépendra du réseau, c.à.d., dans le cas des petits mondes, de la probabilité p de recablage.

A partir de la modélisation décrite dans les paragraphes précédents, il est alors possible de tester différentes stratégies d'immunisation de la population : en supposant qu'un nombre borné d'individus peut être soigné ou vacciné à chaque pas de temps, est-il plus efficace de traiter prioritairement les individus les plus récemment infectés, ou bien ceux qui ne sont pas seulement connectés à leurs voisins directs dans le graphe régulier, ou faut-il encore envisager une autre approche? Quelle partie de la population faut-il vacciner pour qu'en moyenne, l'épidémie ne touche pas plus qu'un certain pourcentage de la population (percolation)?

4  Travail demandé

Le but de ce projet est d'écrire un logiciel permettant de simuler la propagation d'épidémies dans les petits mondes.

Références

[1]
Jean-Jacques Levy. Cours d'informatique fondamentale. Ecole Polytechnique, chapitre 4, 2003-2004.

[2]
Cristopher Moore and M. E. J. Newman. Epidemics and percolation in small-world networks. Physical Review E, 61:5678--5682, 2000.

[3]
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of small-world networks. Nature, 393:440--442, 1998.

Ce document a été traduit de LATEX par HEVEA.