Histoire des mathématiques Discipline

théorie des graphes évolutionnaire

Discipline

approche pour étudier comment la topologie affecte l'évolution d'une population

domaine
biomathématique · théorie des graphes · Théorie des probabilités

Pour comprendre

La théorie des graphes évolutionnaire est une approche qui étudie comment la topologie affecte l'évolution d'une population. Elle met ainsi en relation la topologie et cette évolution.

Ce qu'elle étudie

Elle examine le rapport entre cette organisation et l'évolution d'une population. Son objet est donc l'effet de la topologie sur cette évolution.

Où elle se place

Elle appartient à la théorie des probabilités, à la théorie des graphes et à la biomathématique.

Cas d’usage

Suivons une population de \(N\) individus sur les sommets d'un graphe, des points reliés entre eux. À chaque pas, un individu se reproduit et sa copie remplace un voisin au hasard. Son aptitude mesure sa chance d'être choisi. Un mutant a l'aptitude \(r\), les autres \(1\). La théorie calcule sa probabilité d'occuper toute la population : la fixation.

Dans un graphe complet, chacun est voisin de tous. Avec \(N=10\) et \(r=2\), le processus de Moran donne :

$$\frac{1-1/r}{1-1/r^N}=\frac{1/2}{1-1/1\,024}$$
$${}=\frac{512}{1\,023}\approx0{,}5005$$

Le mutant a donc environ une chance sur deux de s'imposer. Sans avantage, \(r=1\), la fixation vaut \(1/N=0{,}1\). Avec un avantage de \(10\,\%\), \(r=1{,}1\), elle vaut environ \(0{,}148\). Pour \(N=100\) et \(r=2\), elle vaut \(0{,}5\) à \(10^{-20}\) près.

Plaçons maintenant les mêmes individus en étoile : un centre relié à \(9\) feuilles, chacune reliée au seul centre. On suit \(20\) états : centre mutant ou non, et de \(0\) à \(9\) feuilles mutantes.

Pour \(r=2\), les probabilités arrondies sont \(0{,}136\) au centre et \(0{,}711\) sur une feuille. Le centre est vite remplacé ; une feuille ne l'est que si le centre la choisit parmi ses neuf voisines. Pour un mutant placé au hasard, la moyenne pondère les neuf feuilles :

$$\frac{0{,}136+9\times0{,}711}{10}$$
$${}\approx0{,}653$$

La fixation dépasse celle du graphe complet, arrondie à \(0{,}500\). Pour \(r=1\), elle reste \(0{,}1\) : l'étoile amplifie l'avantage. Pour une très grande étoile, elle se rapproche de \((1-1/r^2)/(1-1/r^{2N})\), qui tend vers \(0{,}75\) pour \(r=2\).

Disposons enfin les \(N\) individus en ligne, chacun ne remplaçant que son voisin de droite. Personne ne remplace le premier. Un mutant apparu là envahit toute la ligne à coup sûr ; ailleurs, il finit remplacé. Pour une position initiale au hasard, la fixation vaut \(1/N=0{,}1\) avec \(N=10\), quelle que soit l'aptitude. Le même mutant passe ainsi d'environ une chance sur deux à une chance sur dix selon les liens du graphe.

Sources