{"id":4199,"date":"2013-02-25T00:01:13","date_gmt":"2013-02-24T23:01:13","guid":{"rendered":"http:\/\/sciencetonnante.wordpress.com\/?p=4199"},"modified":"2013-02-25T00:01:13","modified_gmt":"2013-02-24T23:01:13","slug":"propagation-depidemies-et-graphes-aleatoires","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2013\/02\/25\/propagation-depidemies-et-graphes-aleatoires\/","title":{"rendered":"Propagation d’\u00e9pid\u00e9mies et graphes al\u00e9atoires"},"content":{"rendered":"

\"epidemie\"<\/a>Comprendre comment se propagent les \u00e9pid\u00e9mies peut \u00eatre d’une importance capitale. Qu’il s’agisse de maladies ou de virus informatiques, il est utile d’analyser \u00e0 partir de quel point une \u00e9pid\u00e9mie peut s’emballer, ou bien quelle est la meilleure mani\u00e8re de traiter une population si on poss\u00e8de un antidote.<\/p>\n

Pour \u00e9tudier cela avec des simulations, on fait appel \u00e0 des mod\u00e8les o\u00f9 les individus sont repr\u00e9sent\u00e9s par des noeuds d’un r\u00e9seau dont les liens sont al\u00e9atoires et figurent la possible propagation de l’\u00e9pid\u00e9mie : on parle de graphes al\u00e9atoires<\/strong>.<\/p>\n

Un mod\u00e8le simple d’\u00e9pid\u00e9mie<\/h3>\n

Imaginons qu’\u00e0 l’endroit o\u00f9 vous travaillez, une \u00e9pid\u00e9mie soit susceptible de se propager. Heureusement au cours d’une journ\u00e9e, tout le monde ne rencontre pas tout le monde. De surcroit, si deux personnes se croisent, il n’est pas dit que le virus passe, car ce dernier ne va se transmettre que si le contact est suffisamment proche.<\/p>\n

Supposons pour fixer les id\u00e9es qu’il y ait 30 personnes, nous allons repr\u00e9senter ces personnes par des points sur un graphique, que l’on va disposer en cercle (leur position pr\u00e9cise n’a pas d’importance).<\/p>\n

Imaginons qu’au cours d’une journ\u00e9e on croise en moyenne 40% des autres personnes, et que seulement 10% de ces contacts soient \u00ab\u00a0proches\u00a0\u00bb. Au global entre 2 personnes prises au hasard, il n’y a donc que 4% de probabilit\u00e9 d’une transmission du virus.<\/p>\n

Pour repr\u00e9senter cela, on va consid\u00e9rer tous les liens possibles dans le r\u00e9seau, et en tirer au hasard 4% qui seront actifs et donc susceptibles de transmettre le virus<\/strong>. On obtient un graphique comme celui repr\u00e9sent\u00e9 ci-dessous \u00e0 gauche.<\/p>\n

\"erdos_epidemie_1\"<\/a><\/p>\n

Introduisons maintenant un individu malade, repr\u00e9sent\u00e9 ici par un gros cercle rouge. Il n’y a plus qu’\u00e0 propager le virus le long des liens actifs pour conna\u00eetre la taille totale de la population infect\u00e9e<\/strong> : ici seulement 3 personnes. Il ne s’agit que d’un cas particulier, mais si on dispose d’un ordinateur, on peut simuler une telle situation un grand nombre de fois, en tirant \u00e0 chaque fois au hasard 4% des liens qui seront actifs et en comptant la taille de la population infect\u00e9e. Avec 30 individus et 4% de propagation, on va s’apercevoir que dans la quasi-totalit\u00e9 des cas, la taille de la population infect\u00e9e est petite, quelques individus tout au plus.<\/p>\n

\"erdos_epidemie_2\"<\/a>La notion de seuil \u00e9pid\u00e9mique<\/h3>\n

R\u00e9p\u00e9tons maintenant l’exp\u00e9rience en changeant un tout petit peu les chiffres. On va simplement doubler la probabilit\u00e9 que le virus se transmette. On reprend donc nos 30 individus et on tire \u00e0 nouveau au hasard les liens actifs, mais il y en aura cette fois 8% au lieu de 4%.<\/p>\n

On obtient un graphique comme celui-ci contre : comme vous pouvez le constater, si on introduit un individu malade, la maladie se transmet cette fois \u00e0 tout le monde ou presque<\/strong> ! En passant simplement de 4% \u00e0 8% de probabilit\u00e9, on a franchit un seuil qui conduit \u00e0 une propagation quasi-totale. On parle de seuil \u00e9pid\u00e9mique<\/strong>.<\/p>\n

Pour illustrer cet effet de seuil, j’ai fait une simulation plus riche : en prenant 100 individus, j’ai fait varier la probabilit\u00e9 de propagation de 0.1% \u00e0 10%, et j’ai r\u00e9p\u00e9t\u00e9 100 fois l’exp\u00e9rience pour chaque niveau. En calculant la taille moyenne de l’ensemble infect\u00e9, on obtient donc la probabilit\u00e9 de contamination en fonction de la probabilit\u00e9 de propagation. Le r\u00e9sultat est repr\u00e9sent\u00e9 ci-dessous.<\/p>\n

\"erdos\"<\/a><\/p>\n

On voit que pour des probabilit\u00e9s de propagation faibles, la probabilit\u00e9 de contamination est tr\u00e8s faible, alors que pour des probabilit\u00e9s de propagation \u00e9lev\u00e9es, elle est de 1 : c’est-\u00e0-dire que tout le monde tombe malade ! Entre les deux, on voit tr\u00e8s nettement se dessiner le seuil \u00e9pid\u00e9mique \u00e0 partir d’environ 1%, et la transition violente qui l’accompagne<\/strong>. Notez que la position du seuil d\u00e9pend du nombre d’individus : dans cette simulation j’ai utilis\u00e9 100 personnes (au lieu de 30 sur les dessins pr\u00e9c\u00e9dents), et donc le seuil critique a chang\u00e9 : \u00e0 4% on est d\u00e9j\u00e0 en contamination quasi-totale !<\/p>\n

Le mod\u00e8le d’Erd\u00f6s-R\u00e9nyi<\/h3>\n

Le mod\u00e8le que j’ai pr\u00e9sent\u00e9 ci-dessous, et la transition violente qui le caract\u00e9rise, a \u00e9t\u00e9 introduit \u00e0 la fin des ann\u00e9es 50 par les math\u00e9maticiens hongrois Erd\u00f6s et R\u00e9nyi<\/strong>. Ils ont d\u00e9montr\u00e9 que la transition violente se produit quand la probabilit\u00e9 de transmission p est \u00e9gale \u00e0 1\/N, o\u00f9 N est le nombre de noeuds du r\u00e9seau. Cela signifie que le seuil \u00e9pid\u00e9mique est franchi d\u00e8s qu’il existe en moyenne au moins un lien par personne<\/strong>. Tout cela est finalement assez logique !<\/p>\n

Le mod\u00e8le d’Erd\u00f6s-R\u00e9nyi est int\u00e9ressant pour commencer, mais il n’est en fait pas tr\u00e8s r\u00e9aliste. Dans ce mod\u00e8le, le nombre moyen de liens que poss\u00e8de un noeud est \u00e9gal \u00e0 p.N, et la plupart des noeuds ont un nombre de connexions proche de cette valeur moyenne. On dit que ce mod\u00e8le est homog\u00e8ne<\/strong>, car tous les individus jouent plus ou moins un r\u00f4le analogue.<\/p>\n

Mais dans un v\u00e9ritable r\u00e9seau (qu’il soit informatique ou social), on constate que beaucoup d’individus poss\u00e8dent peu de connexions alors que certains autres en poss\u00e8dent un tr\u00e8s grand nombre<\/strong>. Les r\u00e9seaux r\u00e9els sont h\u00e9t\u00e9rog\u00e8nes<\/strong> et il faut donc se tourner vers une autre repr\u00e9sentation.<\/p>\n

R\u00e9seaux r\u00e9els et petits mondes<\/h3>\n

\"scale<\/a>De nombreux r\u00e9seaux ont \u00e9t\u00e9 analys\u00e9s \u00e0 partir de donn\u00e9es r\u00e9elles : l’architecture d’Internet, les collaborations d’acteurs dans le monde du cin\u00e9ma et m\u00eame les r\u00e9seaux de partenaires sexuels [1] ! On constate qu’aucun de ces r\u00e9seaux n’est correctement repr\u00e9sent\u00e9 par un mod\u00e8le de Erd\u00f6s-R\u00e9nyi, car certains individus ont un nombre de liens avec les autres bien plus grand que la moyenne. Un r\u00e9seau r\u00e9el ressemble donc plut\u00f4t \u00e0 ce qui est repr\u00e9sent\u00e9 ci-contre. On voit qu’un tel r\u00e9seau est h\u00e9t\u00e9rog\u00e8ne et que certains noeuds ont un statut particulier.<\/p>\n

Gr\u00e2ce aux individus tr\u00e8s connect\u00e9s qui jouent le r\u00f4le de \u00ab\u00a0hub\u00a0\u00bb, les r\u00e9seaux r\u00e9els poss\u00e8dent une propri\u00e9t\u00e9 que l’on appelle \u00ab\u00a0petit monde<\/strong>\u00ab\u00a0. Cela signifie que l’on peut aller de n’importe quel point du r\u00e9seau \u00e0 un autre par un chemin assez court. Cela correspond \u00e0 cette id\u00e9e populaire qui dit que l’on peut trouver un lien entre 2 personnes prises au hasard dans un pays en moins de 6 connexions<\/strong>.<\/p>\n

\u00c9videmment, la propagation dans des r\u00e9seaux de ce type se fait bien plus facilement que dans un r\u00e9seau de type Erd\u00f6s-R\u00e9nyi ! La contrepartie, c’est que leur structure particuli\u00e8re permet d’imaginer des strat\u00e9gies de traitement plus efficaces qu’avec un r\u00e9seau homog\u00e8ne<\/strong>. Si on immunise quelques noeuds bien choisis, on peut grandement ralentir la propagation.<\/p>\n

Il existe donc tout un champ de recherche consacr\u00e9 \u00e0 la mise au point de strat\u00e9gies de traitement. Pour cela, on voudrait \u00e9videmment traiter en priorit\u00e9 les \u00ab\u00a0hubs\u00a0\u00bb, mais on ne sait pas forc\u00e9ment \u00e0 l’avance qui ils sont. Un exemple tr\u00e8s simple de strat\u00e9gie possible, c’est de tirer au hasard quelques individus, et d’immuniser tous ceux qui leur sont li\u00e9s<\/strong>. On a ainsi une mani\u00e8re de toucher naturellement les individus les plus connect\u00e9s !<\/p>\n

Pour aller plus loin : les r\u00e9seaux \u00ab\u00a0scale-free\u00a0\u00bb<\/em><\/h3>\n

Les propri\u00e9t\u00e9s des r\u00e9seaux r\u00e9els ont \u00e9t\u00e9 tr\u00e8s abondamment \u00e9tudi\u00e9es ces 20 derni\u00e8res ann\u00e9es. Math\u00e9matiquement parlant, la propri\u00e9t\u00e9 principale qui les caract\u00e9rise est la loi de distribution du nombre de connexion d’un noeud pris au hasard. Dans un r\u00e9seau homog\u00e8ne de type Erd\u00f6s-R\u00e9nyi, il s’agit d’une distribution de Poisson, que l’on peut en gros rapprocher d’une gaussienne. C’est-\u00e0-dire que si les individus ont en moyenne 10 liens, on trouvera pas mal de personnes avec entre 3 et 20 liens, mais tr\u00e8s peu au-del\u00e0. Dans un r\u00e9seau r\u00e9el, on trouve des individus avec un tr\u00e8s grand nombre de liens, ce qui fait que la loi de distribution ne peut pas \u00eatre une gaussienne.\u00a0<\/em><\/p>\n

Dans beaucoup de r\u00e9seaux r\u00e9els, cette distribution est celle d’une loi de puissance<\/strong>, c’est-\u00e0-dire que la probabilit\u00e9 P(k) qu’un individu poss\u00e8de k liens est donn\u00e9e par une loi du genre<\/em><\/p>\n

\\(P(k) \\sim \\frac{1}{k^\\gamma}\\)<\/em><\/p>\n

o\u00f9 l’exposant \\(\\gamma\\) vaut en g\u00e9n\u00e9ral entre 2 et 3. Comme je l’expliquais dans mon billet sur les fluctuations de la Bourse<\/a>, ces lois de puissance poss\u00e8dent beaucoup plus d’\u00e9v\u00e8nements extr\u00eames que les braves courbes en cloche : on aura donc un nombre significatif d’individus avec beaucoup plus de liens que les autres. <\/em><\/p>\n

\"scale<\/a>Un exemple ? Les relations sexuelles en Su\u00e8de [1]. Les auteurs de ce papier ont demand\u00e9 \u00e0 4800 Su\u00e9dois et Su\u00e9doises le nombre de partenaires sexuels qu’ils avaient eu l’ann\u00e9e pass\u00e9e. Ils ont ensuite analys\u00e9 la probabilit\u00e9 P(k) d’avoir eu k partenaires. Comme illustr\u00e9 ci-contre, la repr\u00e9sentation de P(k) en \u00e9chelle log-log<\/strong> fait appara\u00eetre une belle droite de coefficient \\(\\alpha\\) \u00e9gal \u00e0 environ 2.4. C’est le signe d’une distribution en loi de puissance ! Si la loi avait \u00e9t\u00e9 gaussienne, on n’aurait eu quasiment personne revendiquant plus de 10 partenaires dans l’ann\u00e9e. Ah oui, on constate aussi ce ph\u00e9nom\u00e8ne bien connus : les hommes s’attribuent plus de conqu\u00eates que les femmes !<\/em><\/p>\n

Revenons \u00e0 nos r\u00e9seaux poss\u00e9dant une distribution de nombre de connexions en loi de puissance. Des analyses identiques ont donc \u00e9t\u00e9 faites pour les r\u00e9seaux informatiques ou encore les r\u00e9seaux de collaboration des acteurs \u00e0 Hollywood. On retrouve toujours le m\u00eame ph\u00e9nom\u00e8ne avec une loi de puissance (et un exposant entre 2 et 3), dont d\u00e9coule notamment un effet petit monde : les individus les plus connect\u00e9s permettent facilement de relier entre elles 2 personnes prises au hasard en un petit nombre de lien. A Hollywood, il semble que l’individu le plus connect\u00e9 soit Kevin Bacon.<\/em><\/p>\n

Ces r\u00e9seaux sont appel\u00e9s \u00ab\u00a0scale free\u00a0\u00bb<\/strong> (sans \u00e9chelle) car la loi de puissance ne fait intervenir aucune taille caract\u00e9ristique (contrairement \u00e0 la gaussienne o\u00f9 la valeur moyenne impose une \u00e9chelle caract\u00e9ristique). Pour repr\u00e9senter ces r\u00e9seaux \u00ab\u00a0scale-free\u00a0\u00bb, les chercheurs se sont beaucoup gratt\u00e9 la t\u00eate : il fallait trouver un mod\u00e8le de r\u00e9seau al\u00e9atoire assez diff\u00e9rent de celui d’Erd\u00f6s-R\u00e9nyi. Deux solutions ont finalement \u00e9t\u00e9 propos\u00e9es. <\/em><\/p>\n

L’une permet de construire explicitement des r\u00e9seaux de type \u00ab\u00a0petit monde\u00a0\u00bb [2]. On part d’un r\u00e9seau o\u00f9 chaque individu n’est connect\u00e9 qu’\u00e0 ses plus proches voisins, et on ajoute al\u00e9atoirement des connexions qui connectent des individus tr\u00e8s \u00e9loign\u00e9s. Mais pour autant que je le comprenne, ceci ne donne pas la propri\u00e9t\u00e9 de \u00ab\u00a0scale free\u00a0\u00bb.<\/em><\/p>\n

La solution a \u00e9t\u00e9 trouv\u00e9e finalement par un mod\u00e8le d’une \u00e9l\u00e9gance et d’une simplicit\u00e9 fantastique : il suffit de construire le r\u00e9seau de mani\u00e8re explicite \u00e0 la mani\u00e8re dont se construisent les vrais r\u00e9seaux, c’est-\u00e0-dire progressivement. L’id\u00e9e cl\u00e9 est la suivante : la probabilit\u00e9 qu’un nouvel individu se connecte \u00e0 un individu d\u00e9j\u00e0 pr\u00e9sent est proportionnelle au nombre de connexions ce dernier que poss\u00e8de d\u00e9j\u00e0,<\/strong> ou autrement dit \u00ab\u00a0the rich get richer\u00a0\u00bb. Pour illustrer cette id\u00e9e, vous pouvez penser au r\u00e9seau informatique (on va tous chercher \u00e0 se connecter \u00e0 un hub tr\u00e8s connect\u00e9) et m\u00eame au r\u00e9seau des relations sexuelles : ceux ayant d\u00e9j\u00e0 eu beaucoup de partenaires poss\u00e8dent certainement le talent et le d\u00e9sir de se connecter encore plus.<\/em><\/p>\n

Bref, dans un de ces papiers simples et lumineux que j’aurai aim\u00e9 \u00e9crire [3], les deux auteurs de ce mod\u00e8le l’ont simul\u00e9 avec divers param\u00e8tres, et ont montr\u00e9 que cela donnait toujours des r\u00e9seaux avec une distribution des liens en loi de puissance avec un exposant -3. Bingo !<\/em><\/p>\n

Un point que je voulais pr\u00e9ciser : dans mes simulations \u00e9pid\u00e9miques, j’ai compl\u00e8tement ignor\u00e9 la question de la dynamique. J’ai suppos\u00e9 en gros que la transmission \u00e9tait instantan\u00e9e et qu’il n’y avait pas de gu\u00e9rison ou de mort. Dans les vrais mod\u00e8les, on prend \u00e7a en compte et on simule la propagation dynamique. On parle alors de seuil \u00e9pid\u00e9mique quand le taux de propagation de la maladie (rapport\u00e9 \u00e0 son taux de gu\u00e9rison) d\u00e9passe une certaine valeur critique. La question de la propagation dans les r\u00e9seaux \u00ab\u00a0scale-free\u00a0\u00bb a d’ailleurs \u00e9t\u00e9 r\u00e9solue r\u00e9cemment, et il a \u00e9t\u00e9 montr\u00e9 que pour ces derniers, le seuil \u00e9pid\u00e9mique est nul [4] ! Aussi petit que soit le taux d’infection, cela finira toujours par d\u00e9g\u00e9n\u00e9rer en \u00e9pid\u00e9mie. <\/em><\/p>\n

D’ailleurs pour faire le lien avec le r\u00e9seau des partenaires sexuels, on estime que la propagation du virus du SIDA \u00e0 l’\u00e9chelle mondiale a \u00e9t\u00e9 facilit\u00e9e par quelques \u00ab\u00a0hubs\u00a0\u00bb poss\u00e9dant un grand nombre de partenaires. On cite souvent le cas de Ga\u00ebtan Dugas, un stewart de Air Canada qui au d\u00e9but des ann\u00e9es 80 aurait eu plus de 2500 relations en quelques ann\u00e9es. Mentionnons tout de m\u00eame que les sp\u00e9cialistes r\u00e9cusent la th\u00e9orie du \u00ab\u00a0patient z\u00e9ro\u00a0\u00bb selon laquelle un unique individu aurait \u00e9t\u00e9 \u00e0 l’origine responsable de toute la transmission.<\/em><\/p>\n

R\u00e9f\u00e9rences :<\/span><\/p>\n

Comme vous pourrez le constater si vous lisez ces papiers, ce domaine de recherche a \u00e9t\u00e9 un temps tr\u00e8s \u00e0 la mode, et il contient un grand nombre des ingr\u00e9dients magiques dont parlait Xochipilli ici<\/a> : transitions de phase, lois de puissance et autres ph\u00e9nom\u00e8nes critiques.<\/p>\n

[1] Fredrik Liljeros et al., \u00ab\u00a0The Web of Human Sexual Contacts\u00a0\u00bb, Nature 411, 907-908 (2001) arXiv:cond-mat\/0106507<\/a> (j’aime l’id\u00e9e qu’un papier sur le sexe soit publi\u00e9 dans \u00ab\u00a0cond-mat\u00a0\u00bb, l’arXiv de mati\u00e8re condens\u00e9e)<\/em><\/p>\n

[2] Watts, Duncan J.; Strogatz, Steven H. \u00ab\u00a0Collective dynamics of ‘small-world’ networks\u00a0\u00bb. Nature 393 (1998): 440\u2013442<\/em><\/p>\n

[3] Barab\u00e1si, Albert-L\u00e1szl\u00f3; Albert, R\u00e9ka \u00ab\u00a0Emergence of scaling in random networks\u00a0\u00bb. Science 286 (1999): 509\u2013512. arXiv:cond-mat\/9910332<\/em><\/p>\n

[4] Romualdo Pastor-Satorras and Alessandro Vespignani, Epidemic Spreading in Scale-Free Networks, Phys. Rev. Lett. 86, 3200\u20133203 (2001) arXiv:cond-mat\/0010317<\/a><\/em><\/p>\n

\u00a0<\/em><\/p>\n

<\/h3>\n","protected":false},"excerpt":{"rendered":"

Comprendre comment se propagent les \u00e9pid\u00e9mies peut \u00eatre d’une importance capitale. Qu’il s’agisse de maladies ou de virus informatiques, il est utile d’analyser \u00e0 partir de quel point une \u00e9pid\u00e9mie peut s’emballer, ou bien quelle est la meilleure mani\u00e8re de traiter une population si on poss\u00e8de un antidote. Pour \u00e9tudier cela avec des simulations, on<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[4],"tags":[86,87],"class_list":{"0":"post-4199","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-mathematiques","7":"tag-reseaux","8":"tag-systemes-dynamiques"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/4199","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/comments?post=4199"}],"version-history":[{"count":0,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/4199\/revisions"}],"wp:attachment":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media?parent=4199"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/categories?post=4199"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/tags?post=4199"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}