La percolation

Une expérience de pensée

Imaginons une expérience, qui est d'ailleurs tout à fait réalisable si vous êtes un peu bricoleur. Construisons un parallélépipède en plexiglass ou toute autre matière isolante, transparente et facile à travailler, une espèce d'aquarium avec deux grandes faces et des cotés très peu profonds. Les cotés hauts et bas de l'engin seront conducteurs, soit en métal soit en plexiglass recouvert d'une feuille d'alu. Réunissons une quantité de billes, les unes en plastique blanc, isolantes, et les autres en métal, conductrices. L'épaisseur de notre aquarium doit être telle que l'on puisse le remplir avec une seule couche de billes.

Maintenant, mélangeons les billes isolantes et conductrices, en proportion donnée, par exemple 30% de billes conductrices et 70% de billes isolantes et remplissons notre aquarium avec ce mélange. Enfin, je branche le coté haut et le coté bas aux deux bornes d'un générateur de tension, une alimentation de labo 5V par exemple. Dans le circuit, j'insère un ampèremètre en série. Un multimètre conviendra très bien.

Je mets le circuit sous tension, et j'observe mon ampèremètre. Vois-je un courant circuler ou non ?

Le but de l'expérience est de déterminer à partir de quelle proportion de billes conductrices le courant passera dans notre aquarium...

L'expérience peut paraître simple mais les cotés pratiques sont pénibles: il faut que les billes soient de même diamètre. Il faut que les billes conductrices soient vraiment conductrices et que leur surface ne soit pas oxydée. Il faut garantir le contact entre toutes les billes. Il faut compter les billes précisément, mais on peut aussi les dénombrer en les pesant. Enfin bef, tous les tracas expérimentaux...

Aussi, je trouve préférable de faire une petite expérience numérique : faire varier la proportion des billes conductrices et isolantes sera beaucoup plus simple. Et je ne suis pas vraiment manuel...

Quelle soit réelle ou simulée, l'expérience me donnera le même résultat: en dessous d'une certaine proportion de billes conductrices, le courant électrique ne circule pas dans mon aquarium ou du moins c'est peu ou très peu probable. Et à partir d'une certaine proportion, un peu plus de la moitié, le courant passe presque à tous les coups puis à tous les coups. Pourquoi ?

Le phénomène physique en cause s'appelle la percolation, oui comme lorsque vous faites votre café dans votre machine favorite, qui n'est qu'un percolateur. D'ailleurs, percolation vient du latin "percolare" qui signifie "couler à travers". C'est un domaine de recherche passionnant, qui déborde aujourd'hui de loin la physique. On percole allègrement, et très abusivement, en économie, sociologie, psychologie et autres sciences dures ou molles. Mais d'abord, voyons de quoi il retourne.

La percolation - une petite introduction

Nature physique de la percolation

La percolation est un phénomène très répandu dans la nature, outre notre machine à café bien sur ! On le rencontre le plus souvent dans la réunion de fluides et de solides poreux ou de milieux granulaires compacts. Par exemple, lorsqu'on parle de l'infiltration des eaux de pluie dans les nappes phréatiques, on suppose que l'eau s'écoule dans la roche, mais encore faut-il que cette roche soit suffisamment poreuse pour le permettre. "Suffisamment" qu'est-ce que cela veut dire ? La théorie de la percolation répond. On retrouve la même problématique lorsqu'il est question de pétrole et de "roche-mère", sans parler de l'horrible gaz de schiste.

Le modèle théorique de la percolation est utilisé dans beaucoup d'autres domaines : la simulation de la propagation des épidémies ou des feux de forêts, mais aussi l'étude des gels ou de la polymérisation des molécules.

Tous ces phénomènes physiques ont un point commun : ils présentent un comportement similaire à une transition de phase, bien connu en thermodynamique. Vous connaissez ce phénomène : on refroidit de l'eau liquide depuis la température ambiante. Rien ne se passe en apparence jusqu'à ce que l'on atteigne la température de congélation de l'eau. Et là, très rapidement et sur une étroite bande de température, l'eau passe de l'état liquide à l'état solide. Tout à fait comme lorsqu'on ajoute des billes conductrices dans notre aquarium. A partir d'un certain seuil de proportion isolant/conducteur, notre mélange change de comportement: il passe de la phase isolante à la phase conductrice. Cette notion de seuil est fondamentale en percolation, on le verra plus loin.

Brefs rappels de la théorie des graphes

La théorie mathématique de la percolation, que l'on doit à John Hammersley en 1957 (grande année ...), repose sur deux domaines des mathématiques : les probabilités et la théorie des graphes. La théorie des graphes intervient dans la description du milieu où a lieu la percolation. Les probabilités interviennent dans la progression du phénomène percolant dans le milieu, dans notre exemple la conduction électrique et la constitution d'un chemin conducteur.

Qu'est-ce qu'un graphe ?

Prenons une feuille de papier, un plan donc... Sur cette feuille, traçons quelques points, puis relions les points entre eux par des traits. Nous venons de construire un graphe ! Les points sont les sommets de notre graphe et les traits ses arêtes. En fait, un graphe G est un couple formé par un ensemble de sommets et un ensemble d'arêtes, que l'on note G(S,A). On dit que le graphe est orienté si le sens de parcours des arêtes est déterminant, sinon il est dit non orienté. Le graphe peut être fini, un nombre fini d'arêtes et de sommets, ou infini. Les résultats théoriques de percolation sont obtenus sur des graphes infinis, histoire de pouvoir utiliser dans les conditions "nominales" les lois de probabilité. Mais évidemment, en simulation, on utilisera des graphes finis et même de taille relativement réduite, avec les conséquences qu'on verra plus loin.

Autre notion très importante : deux sommets sont adjacents lorsqu'ils sont reliés directement par une arête. Ils sont aussi qualifiés de "voisins".

Il faut aussi définir une marche et un chemin. Une marche est une séquence quelconque de sommets et d'arêtes. Un chemin est une marche dont tous les sommets sont distincts. Pour illustrer le concept, parrcourons le graphe que nous venons de tracer sur la feuille en partant d'un sommet et en allant vers un autre sommet éloigné, sans passer deux fois par le même sommet : nous venons de parcourir un chemin. On dit qu'un graphe est connexe lorsqu'il existe un chemin entre chaque sommet du graphe.

Pour étudier la percolation, nous allons nous intéresser à un certain type de graphe, ceux dont la distance entre deux sommets, c'est à dire la "longueur" de l'arête est égale à l'unité. On dit que ces graphes sont de type \( \mathbb{L}^n \), et dans notre cas, en nous limitant au plan, de type \( \mathbb{L}^2 \).

Voilà l'exemple d'un graphe dont les sommets sont disposés sur une grille de maillage carré. C'est ce type de graphe que je vais utiliser pour la modélisation de mon aquarium.

Exemple de graphe non orienté
La percolation de lien et de site

Il existe deux types de mécanismes de percolation : la percolation de lien et la percolation de site. La percolation de lien concerne les phénomènes qui se déroulent sur les arêtes du graphe. La caractéristique de percolation (conducteur/isolant, actif ou mort, etc.) affecte les arêtes, les liens. On retrouve ce modèle de percolation dans l'étude des réseaux de communication par exemple.

Dans la percolation de site, la caractéristique de percolation est affectée aux sommets. C'est le cas dans notre expérience, où chaque bille est un sommet du graphe.

Du point de vue théorique, les deux modèles produisent des résultats qui différent un peu, mais les modèles sont très proches.

L'espace de probabilité sur un graphe

Posons nous dans l'hypothèse de la percolation de site, puisque c'est l'objet de notre expérience. Il convient d'attribuer à chaque sommet, chaque site du graphe, la caractéristique ISOLANT ou CONDUCTEUR, et ce selon une loi de probabilité bien choisie. Je vais donc créer un espace de probabilité sur mon graphe \( \mathbb{L}^2 \).

L'état de chaque sommet est indépendant de l'état des sommets voisins. Je vais définir une loi de probabilité de Bernoulli en posant que la probabilité que chaque bille soit à l'état CONDUCTEUR est égal à p, et que la probabilité que son état soit ISOLANT soit 1-p. En fait, cela revient à fixer la proportion p de billes conductrices par rapport aux billes isolantes.

Notion de cluster

On parle aussi d'amas en français, mais n'en déplaise à Monsieur Toubon, je conserverai la dénomination de cluster qui est bien plus répandue chez les physiciens... Cette notion se comprend intuitivement : c'est un paquet de sommets de même nature, conducteur par exemple, adjacents, ou dit autrement dans un cluster, tous les sommets de même nature sont voisins. Dans le cas de notre aquarium, c'est l'ensemble des billes conductrices qui se touchent, et qui donc permettent le passage du courant électrique.

Voici, schématiquement, un exemple de cluster :

Exemple de cluster

Pour qu'il y ait percolation dans notre aquarium, il faut que le cluster soit suffisamment étendu pour relier le haut et le bas de l'aquarium. Nous verrons plus loin comment quantifier le "suffisamment". En théorie, sur un graphe infini, pour qu'il y ait percolation, il faut que le cluster soit infini. Vous lirez donc souvent dans la littérature "cluster infini", même dans le cas de modèle physique, c'est qui est bien sur un abus de langage !

Un cluster percolant ressemble à ça :

Exemple de cluster percolant

Seuil de percolation

Sur un graphe infini de dimension donnée, il existe un seuil théorique, souvent noté \( p_c \), qui dépend de la dimension du graphe. Si la probabilité p est inférieure à ce seuil, il n'y a jamais percolation et si elle est supérieure à ce seuil, il y a toujours percolation. Cette propriété est démontrable théorique, mais c'est assez délicat. En pratique, on peut approcher la valeur théorique de ce seuil critique, c'est d'ailleurs le but de notre simulation.

Pour fixer les idées, le seuil critique de percolation de site sur \( \mathbb{L}^2 \) est de 0.592746. En percolation de lien toujours sur \( \mathbb{L}^2 \), le seuil critique vaut 0.5. Sur \( \mathbb{L}^3 \), le seuil de percolation de site vaut 0.3116 et celui de lien vaut 0.2488. il est donc plus facile d'obtenir une percolation dans un solide volumique que sur un réseau de dimension 2. Pour l'anecdote, ces valeurs sont calculables à l'aide du théorème de Kesten.

Attention, il s'agit de valeurs théoriques, calculées pour des graphes infinis. Les valeurs mesurées sur des modèles physiques ou simulés sont un peu différentes.

Comment simuler numériquement notre expérience

Les hypothèses de base

Dans notre cas, celui de billes en contact, nous pouvons choisir les deux types de percolation, liens ou sites. Parce que c'est plus simple, je choisis le modèle de la percolation de sites.

Il me faut déterminer les règles de percolation, c'est à dire de formation des clusters. Ce qui revient à définir les règles de calcul de voisinage. On va faire simple : une bille possède quatre billes voisines : celle au dessus, en dessous, à gauche, à droite. Ce sont les billes immédiatement adjacentes. Je considère qu'il y a conduction et donc percolation qu'entre billes immédiatement adjacentes. Deux sites (billes) qui sont adjacents par un sommet ne sont pas considérés comme appartenant à un même cluster. C'est réducteur mais cela simplifie le programme...

Enfin, je ne me préoccupe pas de la géométrie de la bille et je vais travailler sur \( \mathbb{L}^2 \).

La simulation de mon aquarium et de son remplissage

Pour simuler mon aquarium, je vais définir une matrice carrée NxN, dont chaque élément symbolisera une bille. Dans la fonction Grid() dont le code est rappelé ci-dessous (attention, les indentations ne sont pas respectées), c'est le rôle de ma première instruction.

Il me faut maintenant simuler le remplissage de ma matrice avec mon mélange de billes isolantes et conductrices, dans une proportion p. En fait, cela revient à dire que pour un site quelconque, un élement (i,j) de la matrice grid, la probabilité que la bille (l'élément (i,j)) soit conductrice est inférieure à p. Je vais donc parcourir tous les éléments de la matrice et pour chacun d'entre eux, je vais tirer un nombre aléatoire compris entre 0 et 1. Si ce nombre est inférieur à p, alors je déclare la bille conductrice. Ce traitement est fait dans la double boucle, en utilisant la fonction rand() de Python pour générer les nombres aléatoires.

def Grid(n,p):

   grid = zeros((n,n))

   for i in range(n):

       for j in range(n):>

           if rand() < p:

             grid[i][j] = CONDUCTEUR

return grid

Finalement, la fonction Grid() me retourne mon aquarium rempli de billes, simulé par la matrice grid.

L'algorithme de percolation

C'est le coeur du problème et de mon script : comment détecter qu'il existe au moins un chemin qui mène du haut vers le bas de mon aquarium, qui permet le passage du courant électrique ?

C'est l'objet de la fonction Percolate(), qui va déterminer si la matrice passée en paramètre grid percole ou non, i.e. s'il existe au moins un chemin du haut de la matrice vers le bas. Je vous passe les instructions "utilitaires" qui recopie la matrice et détermine sa dimension.

Tout d'abord, il faut s'assurer qu'il existe au moins une bille conductrice qui touche le haut de mon aquarium, un début pour le chemin qui nous conduira en bas de l'aquarium... C'est le rôle des deux instructions suivantes:

for j in range(n):

    if pgrid[0][j] == CONDUCTEUR:

       chemin.append((0,j))>

       pgrid[0][j] = PERCO

L'algorithme parcoure toute la ligne supérieure de la matrice (indice 0) en cherchant un élément conducteur (etat == CONDUCTEUR). S'il en trouve un, il note ses coordonnées dans la liste chemin[] que j'ai crée en début de fonction, par la méthode append(). Il déclare aussi que cet élément appartient à un chemin possible en le passant à l'état PERCO.

Comment procéder maintenant pour poursuivre notre chemin ? Et bien, il suffit d'examiner le voisinage de chaque élément repéré comme élément ou début de chemin, consigné dans la liste chemin[], et ce tant qu'il y a des éléments consignés dans cette liste.

Je commence donc par une boucle while, qui va tourner tant qu'il y aura un élément dans la liste chemin []

while len(chemin) > 0:

première action, j'extrais de la liste les coordonnées du dernier élément de la liste, c'est à dire le dernier élement du chemin identifié :

(i,j) = chemin.pop()

puis je teste ses quatre voisins, haut, bas , gauche et droit. Si un de ses voisins est conducteur, je l'ajoute à la liste et je l'identifie comme élément possible d'un chemin (etat = PERCO).

if i > 0 and pgrid[i-1][j] == CONDUCTEUR:

chemin.append((i-1,j))

pgrid[i-1][j] = PERCO

if i < n-1 and pgrid[i+1][j] == CONDUCTEUR:

chemin.append((i+1,j))

pgrid[i+1][j] = PERCO

if j > 0 and pgrid[i][j-1] == CONDUCTEUR:

chemin.append((i,j-1))

pgrid[i][j-1] = PERCO

if j < n-1 and pgrid[i][j+1] == CONDUCTEUR:

chemin.append((i,j+1))

pgrid[i][j+1] = PERCO

Vous noterez qu'en cherchant les voisins, je me préoccupe quand même de ne pas sortir de mon aquarium ! J'ai choisi une topologie plane fermée, classique en simulation de percolation, alors que dans les simulations d'automates cellulaires, la topologie est plutôt torique (PBC ou Periodic Boundary Conditions comme on dit dans la littérature anglo-saxonne).

Et je répète cette recherche de proche en proche. Chaque fois que je trouve un élément (i, j) conducteur, je cherche à savoir si ses voisins le sont. Je construis ainsi des clusters d'éléments conducteurs.

Lorsque la liste chemin[] est vide, c'est à dire que tous les éléments conducteurs adjacents ont été identifiés, la fonction Percolate() retourne la matrice percolée.

Est-ce que le courant passe ?

Comment savoir si le courant est passé, s'il y a eu percolation ? C'est assez simple : je parcours la ligne la plus basse de la matrice percolée, de mon aquarium, et je teste l'état de chaque élément, de chaque bille. Appartient-il à un cluster (état = PERCO), la bille est-elle sous tension ? S'il existe au moins un élément de la ligne dans cet état, alors le courant passe entre les deux cotés de l'aquarium, il y a percolation. Il existe au moins un cluster qui réunit le haut et le bas de mon aquarium.

Cette logique toute simple est programmée dans la fonction IfPercolate() ci-dessous:

def IfPercolate(grid):

n,n = grid.shape

for j in range(n):

if grid[n-1][j] == PERCO:

return True

return False

IfPercolate() retourne la valeur True s'il y a eu percolation sur au moins un chemin et False dans le cas contraire.

Visualiser les résultats

C'est de la technique pythonesque ! Outre les classiques instructions pour définir les figures, j'utilise la fonction imshow() pour afficher simplement mes matrices. Chaque élément de la matrice prend une couleur en fonction de son état, couleur que je définis avec la fonction ListedColormap(). Les éléments isolants sont blancs, les élements conducteurs sont rouges et les éléments conducteurs appartenant à un cluster sont verts.

La matrice affichée à gauche est la matrice aléatoire d'origine et celle de droite est la matrice après application de l'algorithme de percolation.

axe1.imshow(mat, origin='upper', interpolation='nearest',cmap=ListedColormap(['white','green','red']))

axe2.imshow(pmat, origin='upper', interpolation='nearest',cmap=ListedColormap(['white','green','red']))>

Le script Python

Il s'agit du script SeuilPercolation.py, disponible dans le package Percolation (voir à la fin de la page). A son lancement, il vous demandera de lui indiquer la probabilité de répartition conducteur/isolant, un flottant variant entre 0.0 et 1.0. 0.0 indique aucune bille conductrice et 1.0 toutes les billes conductrices.

A la fin de l'exécution, il vous indiquera s'il y a eu percolation et vous affichera les deux matrices : à gauche avant percolation, à droite après. Pour mémoire, les sites en blancs sont isolants, les sites en rouge sont conducteurs et les sites en vert font partie d'un cluster conducteur.

Les résultats

Je fais l'expérience sur une matrice carrée de 50x50 et avec plusieurs valeurs de p.

Sans percolation

J'exécute le script de simulation avec une proportion de billes conductrices de 30% (p = 0.3) :

p=0.3 percolation de sites

A vue, vous pouvez constater que les amas de billes conductrices (en rouge) sont de petite taille et surtout ne sont pas adjacents. L'algorithme de percolation le confirme: il n'y a pas percolation.

Vous pouvez néanmoins distinguer sur la matrice de droite, quelques éléments en vert dans le haut de la matrice, qui constituent des amorces de chemin. Mais les chemins ont vite rencontrés des billes isolantes !

Avec percolation

J'exécute le script de simulation avec une proportion de billes conductrices de 70% (p = 0.7) :

p=0.7 percolation de sites

Cela se passe de commentaire ! Les clusters de billes conductrices sont beaucoup plus nombreux et donc ont une chance plus grande de joindre le haut et le bas de l'aquarium. Et donc, nous avons percolation !

Faites varier p entre 0.4 et 0.7 en faisant plusieurs essais

Que constatez-vous ? Avec p = 0.4, vous n'obtenez presque jamais de percolation. De même vers 0.5. Entre 0.5 et 0.6, la percolation se produit une fois sur deux environ. Et pour p > 0.7, la percolation est quasiment systématique. Nous observons un effet de seuil. Mais comment déterminer ce seuil ? C'est l'objet du chapitre suivant.

Déterminer le seuil de percolation

Comment le déterminer

Nous savons que le phénomène de percolation est aléatoire. Pour une probabilité de répartition isolant/conducteur p donnée, il faut donc faire plusieurs essais, et de préférence beaucoup, pour vérifier si oui ou non, il y a percolation.

D'autre part, nous avons constaté ci-dessus que la probabilité de percolation dépendait de p, avec un effet de seuil entre 0.5 et 0.6. Nous pouvons imaginer de faire varier p, en faisant plusieurs essais pour chaque valeur de p. Appelons \( \theta(p) \) la probabilité de percolation en fonction de p.

L'objet principal de ce script est de calculer et de tracer la courbe de variation de la fonction \( \theta(p) \), en fonction de p,la probabilité de répartition conducteur/isolant, ce qui est traduit par les instructions suivantes:

px = arange(0.0,1.0,PasProba)

y = [DPM(p) for p in px]

La fonction DPM() calcule la densité de probabilité médiane de percolation :

def DPM(p):

d = 0.0>

for i in range(NbEch):

mat = Grid(N,p)

pmat = Percolate(mat,N)

d += PercolateDensity(pmat,N)

densite = d/NbEch

return densite

Pour une probabilité p donnée, qui varie entre 0.0 et 1.0 par pas PasProba (qui vaut 0.01 dans mon script), la fonction DPM() créé la matrice aléatoire et applique l'algorithme de percolation. Puis elle calcule le rapport de sites appartenant à un cluster sur le nombre de sites conducteurs à l'aide de la fonction PercolateDensity :

def PercolateDensity(grid,n):

a,b = 0.0,0.0

for i in range(n):

for j in range(n):

if grid[i][j] == PERCO:

a += 1.

elif grid[i][j] == CONDUCTEUR:

b += 1.

if a+b > 0:

return a/(a+b)

else:

return 0

La fonction DPM() retourne effectue ces calculs sur un échantillon de taille NbEch (40 dans mon script) et calcule la valeur moyenne de la densité de percolation pour la probabilité d de répartition.

Enfin, le script trace la courbe y = DPM(p)

Les résultats

En faisant varier la probabilité p avec un pas de 0.01, et en faisant 40 essais pour chaque probabilité, j'obtiens la courbe suivante, qui trace la variation de DPM en fonction de p :

Courbe d'évolution de la percolation en fonction de p

C'est une magnifique sigmoïde, qui montre bien l'effet de seuil autour de \( p_c \), et qui permet même de situer \( p_c \) vers 0.59, soit très près de la valeur théorique de seuil qui est de 0.5927 pour la percolation de site sur \( \mathbb{L}^2 \).

D'ailleurs, pour le vérifier, j'ai fait appel à une fonction de Python qui permet de faire de la régression avec une fonction donnée, ici une sigmoïde, que j'ai tracé en rouge sur le schéma. Vous noterez la coïncidence, et aussi la valeur de a, qui donne l'abscisse du point d'inflexion, soit 0,589.

Les scripts Python

Les scripts Python étudiés dans cette page sont disponibles dans le package Percolation.zip :


Contenu et design par Dominique Lefebvre - www.tangenteX.com janvier 2017   Licence Creative Commons    Contact : PhysiqueX ou

Cette œuvre est mise à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Pas de Modification 3.0 France.