Robustesse et émergence dans les systèmes complexes

Étude expérimentale et transition de phase

Dans cette section, nous exposons des résultats expérimentaux obtenus pour la dynamique partiellement asynchrone. Nous verrons qu’environ la moitié des automates élémentaires sont rapidement coalescents (parfois cela dépend du taux de synchronisme α), puis proposons une classification plus fine (section 4.2.1). L’une de ces classes contient les automates subissant une transition de phase quand α varie. Nous montrons alors expérimentalement que cette transition de phase est dans la classe d’universalité de la percolation dirigée (section 4.2.2).

Classification des automates vis-à-vis de la coalescence Protocole

Comme au chapitre 3, un lancer est l’orbite d’un automate lorsque tous les paramètres sont fixés : règle, nombre de cellules n, probabilité α et configuration initiale. Un lancer est stoppé lorsque les deux configurations sont identiques (ce qui est définitif), ou bien lorsqu’un nombre d’étapes fixé à l’avance est atteint. Voici les paramètres utilisés. 1. Nombre de cellules n. Pas de changement par rapport au point 1 page 31. 2. Nombre d’étapes de calcul : idem. C’est le point 2. 3. Probabilité de mise à jour α. Ici encore nous échantillonnons tout l’intervalle [0; 1] (et nous allons d’ailleurs trouver des transitions réparties sur cette intervalle). Pour 48 4. Couplage par les mises à jour chacune des 88 règles, on effectue 999 lancers : un pour chaque valeur de α de 0,001 à 0,999. Ici encore, la régularité des courbes sur les figures 4.1 page suivante et 4.2 page 50 montre qu’il n’est pas nécessaire de moyenner ρ∞(α) sur plusieurs lancers à α fixé. L’initialisation du générateur aléatoire est différente pour chaque valeur de α. L’importance de ce point est justement le sujet de cette étude : nous étudions quelle est l’influence de l’aléa dans les mises à jour. 4. La configuration initiale est aléatoire (tirage uniforme parmi toutes les configurations) et différente pour chaque valeur de α. Résultats Nous obtenons les classes empiriques suivantes. La table 4.4 donne la composition de chaque classe. Tab. 4.4 – Classification empirique des automates élémentaires selon le comportement face à la coalescence rapide. a/ pas de coalescence rapide  f/ combinaison des cas précédents 22, 30, 7 a/ Certaines règles ne coalescent pas (ou prennent pour cela un temps trop long pour que ce soit observable). On peut être un peu plus précis en traçant la densité asymptotique de cellules en désaccord ρ∞ en fonction de α. Pas de coalescence signifie que cette courbe est toujours au-dessus de zéro. Dans la plupart des cas cette courbe est horizontale, souvent autour de 0,5, légèrement bruitée (figure 4.1.a). Ce bruit montre la précision de la mesure, en comparaison avec la figure 4.1.b. Cette dernière est la courbe obtenue pour la règle 204, qui est l’identité : pour cette règle, la densité asymptotique est la même que la densité initiale, la courbe montre donc la variance due à la configuration initiale. On note que la règle 150 (figure 4.1.c) fait tendre la densité vers 0,5 : la courbe est moins bruitée. Notons au passage que ce fait semble difficile à prouver. Les figures 4.1.d et 4.1.e montrent des exemples où la courbe n’est pas une ligne horizontale. La règle 142 est un cas à part. Nous avons montré à la proposition 7 page 42 qu’elle n’est pas rapidement coalescente. Expérimentalement, il n’y a pas de densité asymptotique : la densité évolue indéfiniment. Il y a cependant des corrélations entre les deux configurations : on observe de larges zones d’accord et de larges zones de désaccord. b, c/ Certaines règles sont rapidement coalescentes. 4.2 Étude expérimentale et transition de phase 49 a. règle 28 b. règle 204 c. règle 150 d. règle 33 e. règle 36 f. règle 142 Fig. 4.1 – Densité asymptotique de cellules en désaccord ρ∞(α) pour quelques règles expérimentalement non rapidement coalescentes. L’échelle de chacun des axes est [0; 1]. Le premier cas est le cas typique.

Couplage par les mises à jour

Le cas trivial est celui où la règle converge vers un point fixe unique. On peut alors considérer les deux configurations indépendamment et attendre qu’elles aient chacune atteint ce point fixe. Il y a alors coalescence. c/ Il y a cinq règles expérimentalement non nilpotentes et coalescentes. Parmi elles, la règle 19 converge particulièrement lentement pour α petit. d/ Certaines règles combinent les comportements précédents, selon la valeur de α (figure 4.2). 6, 18, 26, 106, 146 combinent a/ et b/ ; 50 combine b/ et c/ ; 1, 9, 11, 27, 57, 62, 110, 126 combinent a/ et c/ (voir figure 4.4 page 52) ; 58 combine a/, b/ et c/. règle 106 règle 110 règle 57 règle 58 Fig. 4.2 – Densité asymptotique de cellules en désaccord ρ∞(α) pour quelques règles rapidement coalescentes ou non selon α. Le premier cas est le cas le plus courant (50 % des règles). Ces règles, qui subissent une transition de phase, sont étudiées plus avant à la section 4.2.2. e/ Sept règles convergent vers soit l’accord total entre les deux configurations, soit un désaccord total, selon la configuration initiale et les mises à jour. La courbe ρ∞(α) devrait donc être constituée de deux lignes droites, l’une en ρ∞ = 0 et l’autre en ρ∞ = 1. Mais ces règles mettent un temps plus long que les autres à atteindre leur comportement asymptotique, c’est pourquoi la figure est peu précise (figure 4.3 page suivante). Nous avons vérifié que ce comportement décrit est bien celui observé pour quelques valeurs de α. Ces règles prennent un temps encore plus long (peut-être même arbitrairement long) à l’approche d’une certaine valeur de α, d’où la figure en « nœud de papillon » (figure 4.3.b). Plus α est proche d’une certaine valeur critique, plus la convergence 4.2 Étude expérimentale et transition de phase 51 à partir de ρ = 0,5 est lente. Différentes valeurs critiques de α sont observées : faible α (figure 4.3.a), α ≃ 0,5 (figure 4.3.b) ou ailleurs (figure 4.3.c). a. règle 184 b. règle 178 c. règle 43 Fig. 4.3 – Densité asymptotique de cellules en désaccord ρ∞(α) pour quelques règles convergeant vers accord ou désaccord total, selon α. f/ Les règles 22 et 30 combinent le point précédent (pour α petit) avec le point a/ ; la règle 7 le combine (pour α petit) avec c/. On peut noter que la règle 30 montre également une densité asymptotique qui varie quand elle effectue une transition entre les points a/ et e/. Mais à cause des difficultés mentionnées au point e/, cette densité n’a pas été mesurée. 

Percolation dirigée dans ce modèle

Nous nous concentrons maintenant sur les règles du point d/, qui ont la particularité de coalescer rapidement ou non suivant α. Nous étudions maintenant cette transition de phase. La percolation dirigée a été présentée à la section 2.2. Les sites actifs sont ici les cellules où les deux configurations sont en désaccord. La densité de tels sites est notée ρ(α, t), ou ρ∞(α) pour la densité asymptotique. L’ensemble absorbant est constitué des paires de configurations identiques. La transition (coalescence rapide ou non) apparaît en variant α, voir figure 4.4 page suivante. Le but est donc d’identifier δ puis β sous l’hypothèse ρ∞(α) ∝ |α − αc| β pour un certain αc. Noter qu’il n’y a pas a priori de relation directe entre le taux de synchronisme α et la probabilité qu’un lien soit ouvert p dans le modèle de percolation dirigée. 52 4. Couplage par les mises à jour Fig. 4.4 – Règle 110, n = 200. Le temps va de bas en haut, pendant 200 mises à jour. Les sites où les deux configurations sont en désaccord sont sombres, ceux où les deux sont en accord sont clairs. (il y a deux couleurs claires, blanc pour l’état 0, l’autre pour l’état 1). Gauche : régime sous-critique (α = 0,47 < αc ≃ 0,566), les branches meurent. Droite : régime sur-critique (α = 0,65 > αc), les sites actifs se propagent. Il nous faut introduire une notation. En effet, certaines règles (9, 58, 110, 126) subissent deux transitions de phase, une pour α petit, que nous noterons par un ℓ (pour low) en indice comme dans 9ℓ , une autre pour α grand, notée par un h (high) en indice comme dans 9h. Mesure de αc Pour mesurer β, nous utilisons la méthode décrite dans [Hinrichsen (2000)] qui recommande de mesurer d’abord αc avant de faire une régression linéaire pour mesurer β, au lieu de faire la régression en ajustant α et β en même temps. Pour mesurer αc, il s’agit de tracer ρ(α, t) en fonction de t sur une échelle doublement logarithmique et d’ajuster α pour obtenir une ligne droite (pour α < αc, la densité ρ(α, t) tombe à zéro plus rapidement qu’une ligne droite, pour α > αc, elle rejoint une asymptote horizontale strictement positive.). La pente de la ligne est δ. Les mesures de δ sont portées dans le même tableau que celles de β (table 4.6 page 54). Concernant les paramètres, la configuration initiale est aléatoire (uniformément distribuée) et l’on vérifie donc entre deux lancers qu’elle n’a pas d’influence. Pour atteindre la précision actuelle, jusqu’à n = 106 cellules et 107 étapes ont été nécessaires. Les résultats sont dans la table 4.5 page ci-contre. On peut remarquer que αc pour les règles 1 et 126ℓ , de même que pour 9ℓ et 110ℓ , sont très proches, et sans doute égaux. Noter aussi la nécessité d’échantillonner α le plus largement possible, en effet le seuil αc pour les règles 6 et 11 est proche de 0 ou 1.