Previous Up Next
© 2001 - Stéphane PAJOT   [ Percolation et économie ]

1.2  Les modèles théoriques fondamentaux

Pour illustrer les différents modèles, on peut prendre l'exemple d'un réseau de communication en montagne (Roussenq, 1992, p. 838). Sur chaque sommet, un opérateur (site) peut envoyer des signaux optiques à ses voisins. Lorsque le temps est clair, la visibilité est parfaite, on considère que toutes les liaisons entre les opérateurs sont efficaces. Formellement, ceci correspond à un taux d'activité des liens de 100 %. Si dans ces conditions tous les opérateurs sont attentifs, c'est-à-dire que le taux d'activité des sites est de 100 %, il est alors possible de transmettre une information à grande distance à travers le réseau (figure 1.4).

Figure 1.4: Système de communication en montagne

À partir de ce modèle idéal, la baisse de vigilance des opérateurs et la dégradation des conditions météorologiques peuvent rendre la communication plus complexe. Trois situations peuvent s'envisager.

Figure 1.5: Dégénérescence du système de communication

(a) Percolation de sites (b) Percolation de liens (c) Percolation mixte
     
Dans le premier cas, le temps est clair (liens efficaces à 100 %) mais on suppose que certains opérateurs dorment (taux d'activité des sites variable). L 'aléa porte uniquement sur les sites. Le problème correspond alors au modèle de percolation de sites (figure 1.5 (a)). Dans le deuxième cas, les opérateurs sont tous attentifs (sites efficaces à 100 %) mais le temps est nuageux. Les liaisons optiques entre les opérateurs deviennent aléatoires (taux d'activité des liens variable). L'aléa porte uniquement sur les liens. Le problème se rapporte alors au modèle de percolation de liens (figure 1.5 (b)). Enfin, dans le cas où à la fois les opérateurs et leurs liaisons ont une activité aléatoire, on parle de percolation mixte également appelée modèle de percolation sites-liens (figure 1.5 (c)).

Afin de voir les caractéristiques des modèles de percolation évoqués ci-dessus, nous allons revenir en détails sur chacun d'entre-eux dans le cadre des réseaux réguliers.

1.2.1  Percolation de sites

Après une description formalisée du problème de percolation de sites, plusieurs types de réseaux courants liés au modèle seront exposés.

Définition

Dans un graphe, c'est-à-dire un ensemble de sommets (ou sites) et d'arêtes (ou liens), on dit que deux sommets sont plus proches voisins s'ils sont reliés par une arête. Reprenant le cadre de Clerc et alii (1983), nous nous limiterons à l'étude de « 1-graphes infinis symétriques », c'est-à-dire de graphes composés d'un nombre infini de sommets et d'arêtes, dans lesquels deux sommets quelconques sont reliés par au plus une arête non orientée3. De ce graphe, on peut élaborer un labyrinthe aléatoire en affectant aux sommets l'un des deux états possibles : 1 ou 0, actif ou inactif, conducteur ou isolant, occupé ou vide, etc. Chaque site est conducteur avec la probabilité ps et isolant avec la probabilité qs = (1 – ps).

Soit Lij la liaison entre deux sites plus proches voisins Si et Sj. Il existe un chemin conducteur entre deux sites actifs Si et Sn, si et seulement si il existe une suite Si, Sj, ..., Sm, Sn de sites actifs reliés par des arêtes Lij, Lj., ..., L.m, Lmn conductrices. On dit de deux sites qu'ils appartiennent au même amas s'il existe au moins un chemin conducteur entre ces deux sites. Pour résumer, le modèle de percolation de sites considère que tous les liens sont actifs mais que les contacts entre les liens sont contrôlés par les sites.

De façon intuitive, on peut comprendre que la valeur pc du seuil de percolation est sensible à la connexité du réseau et à la dimension de l'espace4. Ainsi, plus le nombre de sites « plus proches voisins » augmente, plus la valeur critique nécessaire à la formation d'un amas infini est faible. C'est ce que nous observerons dans plusieurs types de réseaux.

Réseau carré et réseau cubique

Une structure de graphe fréquemment utilisée en dimension deux est celle que les physiciens appellent réseau carré (square lattice) et dont la collection des sites est dénotée Z2 par les mathématiciens. Elle peut se représenter de deux façons équivalentes (figure 1.6).

Figure 1.6: Représentations du réseau carré de sites

(a) Sites sur les cases   (b) Sites aux intersections
 
Source : adapté de Stauffer et Aharony (1992), p. 2
Ces deux représentations sont similaires car chaque site possède exactement quatre plus proches voisins. Dans le type (a), le site se confond avec la case. Le point noir représentant un site actif est situé au centre de la case. Si le site est inactif, elle reste vide. Dans ce contexte, un amas se définit par un ensemble de cases contenant un site actif et ayant un côté en commun. Dans le type (b), le site se trouve à l'intersection des lignes. Là encore, si le site est actif il est représenté par un point noir sinon l'intersection reste inoccupée. Dans ces conditions, un amas est constitué par les intersections ayant un site actif (les points noirs) dont une liaison est commune. Sur chacune des représentations, les amas composés d'au moins deux sites ont été grisés.

La représentation de type (b) a l'avantage de mettre en évidence les liaisons entre sites. Elle est surtout utile pour analyser le modèle de percolation mixte (voir § 1.2.3, p. ??). La mise en évidence des liens a l'inconvénient de surcharger la figure lorsque la taille du réseau est importante. Pour une plus grande clarté, on peut alors représenter le modèle de percolation de sites dans un réseau carré, en colorant les cases selon leur état. La distinction des amas devient alors immédiate puisque les sites contigus fusionnent. La figure 1.7 illustre cette méthode à différentes échelles.

Figure 1.7: Réseau carré de sites à différentes échelles

(45 % de sites noirs)
(a) (10 × 10) sites (b) (25 × 25) sites (c) (50 × 50) sites
     
En rajoutant une dimension on passe du réseau carré au réseau cubique qui correspond à Z3. La figure 1.8 (a) illustre le réseau qui se représente par un empilement de cubes.

Figure 1.8: Représentations de la structure cubique

(a) Vue pleine   (b) Vue par transparence
 
Ceci est mis en évidence par la figure 1.8 (b), extrait de la figure 1.8 (a), où la transparence permet de visualiser l'intérieur de la structure.

On distingue trois sortes de réseaux : le cubique simple, le cubique centré et le cubique faces centrées5.

Figure 1.9: Réseaux cubiques : simple, centré, faces centrées

(a) Réseau cubique simple   (b) Réseau cubique centré   (c) Réseau cubique faces centrées
   
Dans la structure de la figure 1.8, le réseau cubique simple possède ses sites aux sommets des cubes (figure 1.9 (a)). Le réseau cubique centré possède un site au milieu du cube en plus des sites aux sommets (figure 1.9 (b)). Enfin, le cubique faces centrées ajoute au réseau cubique simple, un site au centre des six faces de chaque cube (figure 1.9 (c)). Ces différentes formes de réseaux cubique se retrouvent notamment dans des structures moléculaire comme par exemple le cristal.

Réseau triangulaire et réseau nid d'abeille

En dimension deux, le réseau triangulaire et le réseau nid d'abeille (honeycomb lattice) sont fréquemment évoqués. La structure de base est la même pour les deux réseaux, mais le positionnement des sites diffère sur le maillage.

Le réseau triangulaire s'obtient, comme sur la figure 1.10 (a), en plaçant les sites sur chaque intersection des lignes qui divisent R2 en triangles équilatéraux (Kesten, 1982, p. 14).

Figure 1.10: Réseau triangulaire de sites

(a)    (b)    (c) 
   
Chaque site possède six plus proches voisins. On peut représenter le réseau triangulaire de deux manières. La première consiste à mettre en évidence les relations entre le site et ses six plus proches voisins (figure 1.10 (b)). La seconde occulte la représentation des liens et représente le site par une figure géométrique avec six côtés, c'est-à-dire un hexagone (figure 1.10 (c)).

Pour représenter un modèle de percolation de sites dans un réseau triangulaire de taille importante, il est préférable d'utiliser la seconde méthode pour une plus grande lisibilité. Les amas se distinguent ainsi de façon automatique, car les sites contigus ayant le même état fusionnent. Le réseau triangulaire apparaît alors comme un assemblage d'hexagones (figure 1.11).

Figure 1.11: Réseau triangulaire de sites à différentes échelles

(45 % de sites noirs)
(a) (5 × 5) sites (b) (15 × 15) sites (c) (25 × 25) sites
     
Sur la même structure qui divise R2 en triangles équilatéraux, si l'on place à présent les sites au centre des triangles, on obtient un réseau nid d'abeille 6.

Figure 1.12: Réseau nid d'abeille de sites

(a)    (b)    (c) 
   
Sur la figure 1.12 (a), on constate que les sites possèdent trois plus proches voisins. Dans la figure 1.12 (b), pour mieux faire ressortir la forme hexagonale du nid d'abeille, les lignes de la structure en triangles sont effacées au profit des liens entre les trois voisins d'un site. Ceci est le premier moyen de représenter un réseau nid d'abeille. La seconde méthode consiste encore une fois, à occulter les liens et à représenter chaque site par une figure géométrique dont le nombre de côtés est égal au nombre de plus proches voisins. Dans le réseau nid d'abeille, on représente alors les sites par des triangles (figure 1.12 (c)).

Pour faciliter la lecture d'un graphe, la représentation du réseau nid d'abeille de sites se fait de préférences, selon la deuxième méthode. Ainsi, la structure des amas émerge de façon mécanique puisque les sites contigus qui ont un même état fusionnent. Le réseau nid d'abeille se présente alors comme un mélange de triangles (figure 1.13).

Figure 1.13: Réseau nid d'abeille de sites à différentes échelles

(45 % de sites noirs)
(a) (6 × 9) sites (b) (8 × 17) sites (c) (14 × 29) sites
     

Autres réseaux

Pour leur caractéristiques remarquables, deux autres réseaux réguliers méritent d'être évoqués. Le premier est le réseau de Bethe (Bethe lattice) appelé aussi arbre de Cayley (Cayley tree). Sa structure est une arborescence sans boucle où chaque noeud possède un nombre constant de branches. Autrement dit, chaque site a un même nombre z de plus proches voisins (figure 1.14).

Figure 1.14: Réseau de Bethe

(a) z = 3   (b) z = 4
 
Source : Stauffer et Aharony (1992), p. 27.   Source : Lesne (1996), p. 321.
Le deuxième graphe a lui aussi une structure particulière. Il s'agit du réseau Kagomé, dont une représentation est proposé à la figure 1.15.

Figure 1.15: Réseau Kagomé

Source : Clerc et alii (1983), p. 12
Sur cette structure, chaque site a quatre plus proches voisins. Le réseau Kagomé se caractérise par le fait d'être le « graphe de couverture » (covering graph) du réseau nid d'abeille. Cette relation entre les deux graphes permet quelques correspondances sur lesquelles nous reviendrons par la suite (voir § 1.2.2, p. ??).





Après avoir décrit le modèle de percolation de sites et la façon dont il se représente pour les réseaux réguliers les plus fréquemment utilisés, le paragraphe suivant s'intéresse à présent au modèle de percolation de liens.

1.2.2  Percolation de liens

La présentation formalisée du problème de percolation de liens sera suivie d'un exposé sur les réseaux courants liés au modèle.

Définition

De nouveau, plaçons nous dans le cadre des « 1-graphes infinis symétriques » où deux sommets sont reliés par au plus une arête non orientée. Pour modéliser la percolation de liens, la création d'un labyrinthe se fait en affectant aux arêtes l'un de deux états possibles : 1 ou 0, actif ou inactif, conducteur ou isolant, occupé ou vide, etc. Chaque lien est actif avec la probabilité pb et inactif avec la probabilité qb = (1 – pb).

Soit Lij la liaison entre Si et Sj, deux sites plus proches voisins. Dans le problème de percolation de liens, il existe un chemin conducteur entre deux sites actifs Si et Sn si et seulement si, il existe une suite Si, Sj, ..., Sm, Sn de sites conducteurs reliés par des arêtes Lij, Lj., ..., L.m, Lmn actives. On dit que deux liens appartiennent au même amas, s'il existe au moins un chemin conducteur entre les trois sites ainsi reliés. Pour résumer, le modèle de percolation de liens postule que tous les sites sont actifs, mais que les contacts entre sites sont contrôlés par les liens.

De même que nous l'avions indiqué pour la percolation de sites, la valeur pc du seuil de percolation dans le modèle de liens est d'autant plus faible que la connexité du réseau est importante. Plus le nombre de liens par site augmente et plus la valeur critique nécessaire au développement d'un amas infini est faible.

Réseau carré

Tout comme en percolation de sites, le réseau carré est l'un des plus familiers. Les figures 1.16 (a) et 1.16 (b) montrent respectivement le maillage en pavé pour un réseau dont tous les liens sont actifs, et un exemple de réseau dont une partie seulement des liens sont actifs.

Figure 1.16: Réseau carré de liens

(a) Maillage en pavé   (b) Exemple de percolation de liens
 
Source : Clerc et alii (1983), p. 56
Sur la figure 1.16, on distingue des amas isolés ainsi qu'un gros amas qui relie les droites (AB) et (CD), que nous pourrions appeler « électrodes » par analogie avec un réseau de résistances. Cet amas (en gras sur le schéma) est appelé amas infini, puisqu'il relie un côté à l'autre dans la représentation. L'examen de l'amas infini nous permet de distinguer trois sortes de liens (Clerc et alii, 1983, pp. 55-56) : Dans la majorité des cas, la représentation des modèles de percolation de liens s'effectue sans que les sites ne soient dessinés. La lecture du graphe s'en trouve alors facilitée quelle qu'en soit l'échelle (figure 1.17).

Figure 1.17: Réseau carré de liens à différentes échelles

(45 % de liens actifs)
(a) (10 × 10) sites (b) (25 × 25) sites (c) (50 × 50) sites
     
180 liens max. 1 200 liens max. 4 900 liens max.
Le nombre de liens qui seraient présents si 100 % d'entre-eux étaient actifs a été précisé sous chaque figure. Dans un réseau carré, le calcul de ce nombre de liens maximum est trivial. Pour un réseau de taille (n × n) sites, il existe au plus 2 n (n – 1) liens.

Réseau triangulaire et réseau nid d'abeille

Comme en percolation de sites, le modèle de percolation de liens est couramment utilisé dans des réseaux triangulaires ou nids d'abeille. Là aussi, les sites et les liens inopérants sont masqués, les liens actifs étant généralement les seuls a être représentés.

Sur le réseau triangulaire, les sites ont six plus proches voisins. En conséquence, au maximum six liens peuvent être matérialisés par sites. Ceci peut s'observer sur la figure 1.18 qui illustre le problème de percolation de liens dans des réseaux triangulaires de tailles différentes.

Figure 1.18: Réseau triangulaire de liens à différentes échelles

(45 % de liens actifs)
(a) (9 colonnes × 14 lignes) (b) (15 colonnes × 26 lignes) (c) (25 colonnes × 42 lignes)
     
63 sites ; 158 liens max. 195 sites ; 530 liens max. 525 sites ; 1 484 liens max.
Dans les configurations triangulaire et nid d'abeille, il n'est pas possible d'indiquer la taille par le nombre de sites au bord du réseau car les liens ne sont, par définition, pas orthogonaux. Pour cette raison, la taille est notée en nombre de colonnes et de lignes. Le nombre de sites et le maximum de liens possibles ont été indiqués sous chaque figure.

Pour le réseau nid d'abeille, il existe au plus trois liens par sites. La figure 1.19 donne quelques exemples de percolation de liens dans des réseaux de tailles différentes.

Figure 1.19: Réseau nid d'abeille de liens à différentes échelles

(45 % de liens actifs)
(a) (10 colonnes × 6 lignes) (b) (20 colonnes × 12 lignes) (c) (35 colonnes × 22 lignes)
     
60 sites ; 75 liens max. 240 sites ; 329 liens max. 770 sites ; 1 099 liens max.

De la percolation de liens à la percolation de sites

Une forte similitude ressort des modèles de percolation de sites et de percolation de liens. En fait, même si qualitativement il existe une différence indéniable, il est possible de transformer un réseau de liens en un réseau de sites. C'est M.E. FISHER7 qui démontra qu'en plaçant un site sur chaque lien du réseau initial, puis en traçant des lignes entre les sites qui sont sur des liens voisins, on pouvait toujours convertir un problème de liens en un problème de sites (Kesten, 1982, p. 36 ; Domb, 1983, p. 21 ; Smythe, 1983, p. 481). Le problème de sites se trouve alors posé sur un réseau différent du réseau initial : le graphe de couverture.

Pour comprendre le mécanisme de passage entre les deux modèles, la première illustration montre la transformation d'un réseau carré de liens en un réseau différent de sites (figure 1.20).

Figure 1.20: D'un réseau carré de liens à un réseau de sites

(a) (b) (c)
     
Au milieu de chaque lien du réseau carré, on place un point noir représentant un site (S1 au milieu de AB, S2 au milieu de AC, etc.). Le lien AB étant relié aux liens AC, AD et AE d'un côté, et aux liens BF, BG et BH de l'autre, on relie alors S1 à S2, S3 et S4 puis à S5, S6 et S7. Sachant qu'il existe également des liaisons entre AC–AE, AC–AD, AD–AE, HB–BF, BF–BG et BG–BH, on trace les liens de S2 à S4, S2 à S3, S3 à S4, S7 à S5, S5 à S6 et S6 à S7. En réitérant l'opération sur toutes les autres cellules du maillage, on voit alors que les sites S se trouvent aux sommets d'un autre réseau qui correspond au graphe de couverture du réseau carré.

La seconde transformation (figure 1.21) est plus complexe : d'un réseau nid d'abeille de liens on passe à un réseau Kagomé de sites.

Figure 1.21: D'un réseau nid d'abeille de liens à un réseau Kagomé de sites

Source : Clerc et alii (1983), p. 13
Comme nous l'avions déjà évoqué (voir § 1.2.1, p. ??), ces deux graphes entretiennent une relation géométrique particulière puisque le réseau Kagomé est le graphe de couverture du réseau nid d'abeille (Kesten, 1982, pp. 36-37). Selon la même méthode, on place un point noir représentant un site (S1 au milieu de AB, S2 au milieu de AC, etc.) au milieu de chaque lien. Le lien AB étant relié aux liens AC et AD d'un côté, et aux liens BF et BE de l'autre, on relie alors S1 à S2 et S4 puis à S3 et S5. En renouvelant l'opération sur toutes les autres cellules du nid d'abeille, on voit alors que les sites S se trouvent aux sommets d'un réseau Kagomé.

De cette manière, il est toujours possible de construire le graphe de couverture d'un réseau donné, mais chaque réseau n'est pas intrinsèquement un graphe de couverture. En conséquence, chaque problème de percolation de liens correspond à un problème de percolation de sites dans un réseau différent, mais tous les problèmes de sites n'ont pas obligatoirement de contrepartie sous forme de percolation de liens (Domb, 1983, p. 22).

Cette correspondance entre percolation de liens et percolation de sites a de nombreuses conséquences, comme par exemple de mesurer la taille d'un amas par le nombre de sites ou le nombre de liens. Un amas de taille deux du point de vue des sites, est équivalent à un amas de taille un du point de vue des liaisons. Cette transformation permet aussi d'obtenir des valeurs exactes pour le seuil de percolation. Ainsi le seuil de percolation pc pour le réseau Kagomé de sites est égal à celui du réseau nid d'abeille de liens (voir tableau 1.5, p. ??).





L'exposé des problèmes de percolation de sites et de percolation de liens a permis de mettre en évidence leurs caractéristiques propres. En réalité, la distinction des deux modèles est artificielle car ce sont deux cas particuliers d'un modèle plus général : le modèle de percolation mixte.

1.2.3  Percolation mixte

La présentation formelle du modèle de percolation mixte sera suivie d'une illustration dans le réseau carré.

Définition

Pour définir le modèle générique de percolation, c'est-à-dire le modèle de percolation mixte, nous allons analyser le problème de la propagation d'une maladie (Hammersley et Welsh, 1980, pp. 594-596).

Soit G, un graphe de taille finie ou infinie, formé d'un ensemble de sites connectés les uns aux autres par des liens. Dans G, un chemin du site S1 au site Sn est une séquence finie de la forme {S1, L12, S2, ... , L(n – 1)n, Sn }, où Lij représente un lien connectant Si à Sj. On suppose que chaque site S de G est « ouvert » à la propagation avec la probabilité ps ou « fermé » avec la probabilité qs = 1 – ps. De façon équivalente, chaque lien Lij est « ouvert » avec la probabilité pb ou « fermé » avec la probabilité qb = 1 – pb. Dans le cas de la propagation d'une maladie, l'ouverture ou la fermeture des sites et des liens s'interprète comme la possibilité ou l'impossibilité de transmettre la maladie. Les deux paramètres ps, pb peuvent respectivement se comparer à la vulnérabilité des personnes et à la virulence de la maladie8. De manière plus explicite, on peut considérer qu'une proportion ps de la population est vulnérable face à la maladie alors qu'une proportion 1 – ps est immunisée. Concernant les liens de G qui connectent les paires de sites voisins, le modèle suppose qu'une personne atteinte a une probabilité pb de contaminer un voisin s'il est vulnérable. Ainsi, P(ps, pb ; I, G) est la probabilité qu'une maladie initialement présente dans l'ensemble I des sites instigateurs devienne une épidémie.

Dans le cas où I et G sont fixés, si G est de taille infinie alors le modèle de percolation mixte se note P(ps, pb). Les modèles de percolation de sites P(ps, 1) et de percolation de liens P(1, pb) apparaissent alors comme des cas particuliers du modèle de percolation mixte (tableau 1.3).

Table 1.3: Le modèle générique : la percolation mixte P(ps, pb)

Virulence (liens)
pb Î [0, 1[ pb = 1
Vulnérabilité (sites)   ps Î [0, 1[   Percolation mixte « pure » : P(ps, pb) Percolation de sites : P(ps, 1)
ps = 1 Percolation de liens : P(1, pb) –
Les problèmes de percolation de sites et de percolation de liens ont l'avantage de limiter à un le nombre de paramètres du modèle. Toutes choses égales par ailleurs, l'action n'est alors possible que sur le paramètre variable du modèle en question : ps pour la percolation de sites et pb pour la percolation de liens. En randomisant à la fois l'activité des sites et celle des liens, il devient possible d'agir sur un ou sur deux facteurs à la fois, pour influencer le résultat global.

Percolation mixte sur un réseau carré

La représentation d'un problème de percolation mixte exige qu'à la fois les sites et les liens soient dessinés. Cette double information surcharge les illustrations et la recherche « manuelle » des amas se complexifie lorsque la taille du réseau augmente. La figure 1.22 montre quelques représentations du problème mixte dans un réseau carré à différentes échelles.

Figure 1.22: Réseau carré mixte à différentes échelles

(45 % de liens et de sites actifs)
(a) (10 × 10) sites (b) (25 × 25) sites (c) (50 × 50) sites
     
Sur ces représentations, les proportions d'activité des sites (ps) et des liens (pb) sont égales mais ceci n'est pas obligatoire. La valeur des deux paramètres est indépendante.





La présentation des modèles théoriques fondamentaux a permis de préciser leurs ressemblances et leurs différences respectives. Quelques propriétés géométriques ont été développées sur différents réseaux, dont notamment le mécanisme de passage d'un problème de liens à un problème de sites. La réciproque de cette transformation n'étant pas toujours vérifiée, le caractère plus fondamental du modèle de percolation de sites par rapport à celui de liens a ainsi été mis en évidence (Domb, 1983, p. 22). Par suite, la percolation mixte (système générique des autres modèles) est apparue plus riche que les problèmes élémentaires de sites et de liens, les deux paramètres d'efficacité (ps et pb) pouvant y varier simultanément. En conséquence, de nouvelles problématiques apparaissent. La plus intéressante concerne la question de l'efficacité relative des actions sur les sites par rapport aux actions sur les liens. La réponse à cette question et à d'autres, exige un approfondissement d'une notion essentielle au modèle qu'il soit mixte, de sites ou de liens : le seuil de percolation.

Previous Up Next