23 sept. 2019 · 17 min
Graphes expanseurs : le paradoxe des réseaux sobres
Dans cet épisode audio, suivez les étapes d’un paradoxe : comment un réseau peu dense peut rester robuste, puis découvrez ses usages en géométrie.
Collections de cet épisode (8)
Un contenu original Tangente, adapté en podcast avec l’aide de l’IA et validé par notre rédaction. Comment ça marche ?
Transcription
Afficher la transcriptionMasquer la transcription
Transcription automatique
Intervenant 1
Bienvenue dans le podcast du magazine Tangente et bienvenue à tout le monde pour cette nouvelle exploration mathématique. Pour démarrer, j'aimerais qu'on pose un scénario un peu étrange.
Intervenant 2
Bonjour.
Intervenant 1
Ouais, un scénario mental, c'est toujours une bonne porte d'entrée.
Intervenant 2
Voilà, alors on peut imaginer une compagnie aérienne qui fonctionnerait avec un budget vraiment microscopique. Chaque aéroport ne propose des vols directs que vers, disons, quatre ou cinq autres villes au maximum.
Intervenant 1
D'accord, donc une économie d'infrastructures vraiment totale.
Intervenant 2
C'est ça. Mais, et c'est là que ça devient fou, si une tempête géante frappe le continent et annule purement et simplement un vol sur dix, au hasard, aucun passager ne se retrouve bloqué.
Intervenant 1
Ah oui, le réseau tient bon. Exactement. Tout le monde peut encore atteindre sa destination finale. Le réseau ne se brise jamais en deux entités isolées. Et c'est un peu le paradoxe au cœur de notre sujet du jour, qui est tiré d'une conférence d'Emmanuel Kowalski sur les graphes expanseurs.
Intervenant 2
Ouais, l'anomalie est assez frappante en effet. Mais pour décrypter ce comportement géométrique inhabituel, je pense qu'il faut d'abord revenir à l'unité de base, c'est-à-dire le graphe.
Intervenant 1
Le graphe mathématique, oui.
Intervenant 2
Voilà. En mathématiques, la définition est d'une grande sobriété en fait. Un graphe, ça se résume simplement à un ensemble de points, qu'on appelle des sommets, qui sont connectés par des lignes qu'on va appeler des arêtes.
Intervenant 1
Et pour notre plongée d'aujourd'hui, on précise que ces arêtes ne sont pas orientées, hein ?
Intervenant 2
Tout à fait. Elles agissent un peu comme des routes à double sens où l'information ou l'énergie circulent librement dans les deux directions.
Intervenant 1
Et ce qui est intéressant, c'est que ces structures abstraites, elles modélisent littéralement notre quotidien. Dans les textes qu'on a épluchés, on voit des applications super tangibles.
Intervenant 2
Oui, il y a pas mal d'exemples très concrets.
Intervenant 1
Bah oui, genre le réseau de tramway de Zurich ou même le maillage du métro parisien avec toutes ses correspondances. Et on peut même modéliser un arbre généalogique comme ça.
Intervenant 2
C'est vrai.
Intervenant 1
Il y a aussi ce cas d'étude biologique, le réseau neuronal du ver Caenorhabditis elegans. C'est, si je ne dis pas de bêtises, le seul organisme dont on a cartographié l'intégralité du système nerveux, connexion par connexion.
Intervenant 2
Ouais, c'est un peu plus de 300 euros pour le coup. Le graphe, c'est vraiment le langage universel des réseaux. Mais la catégorie spécifique des graphes expanseurs, elle a longtemps été perçue comme une espèce de chimère mathématique.
Intervenant 1
Une chimère, carrément ?
Intervenant 2
De nombreux chercheurs pensaient que ces autres gènes ne pouvaient tout simplement pas exister parce qu'ils exigent la coexistence de deux propriétés qui logiquement s'opposent.
Intervenant 1
D'accord, décortiquons un peu tout ça. C'est quoi la première propriété ?
Intervenant 2
La première, c'est une robustesse structurelle à toute épreuve. On garantit qu'il est toujours possible de trouver un chemin rapide entre deux sommets, même après la destruction massive et arbitraire d'une grande partie des connexions.
Intervenant 1
D'accord. Sauf que, intuitivement, pour avoir un réseau indestructible, on se dit qu'il faut multiplier les câbles partout.
Intervenant 2
Voilà, c'est ce que dicte le bon sens.
Intervenant 1
Il faudrait relier chaque point à presque tous les autres pour anticiper les pannes.
Intervenant 2
Eh bien, c'est précisément là qu'intervient la seconde propriété, celle qui défie la logique. Le coût matériel de ces graphes est en fait dérisoire.
Intervenant 1
C'est-à-dire ?
Intervenant 2
Chaque sommet n'est connecté qu'à un nombre très restreint de points. Par exemple, un maximum de 6 arêtes par sommet. Et c'est ça le plus fort, cette limite reste fixée à 6, que le réseau global comporte 1000 points, 1 million ou même des milliards de sommets.
Intervenant 1
C'est complètement contre-intuitif. Donc le réseau est presque vide, très clairsemé, mais il reste inébranlable.
Intervenant 2
Exactement, c'est le paradoxe de l'expenseur.
Intervenant 1
D'où mon analogie de la compagnie aérienne low-cost du début. Mais comment on fait mathématiquement pour chiffrer cette solidité ? Il doit bien y avoir un point de rupture, non ?
Intervenant 2
Oui, tout à fait. L'outil de mesure décisif pour ça, ça s'appelle la constante de Shager. On la note H2G.
Intervenant 1
H2G, d'accord.
Intervenant 2
En gros, la méthode consiste à soumettre le graphe au pire scénario de rupture envisageable. On prend la totalité des sommets, disons un nombre n, et on cherche à les diviser en deux groupes distincts de tailles à peu près égales.
Intervenant 1
On coupe purement et simplement le réseau en deux moitiés, donc le groupe A et le groupe B.
Intervenant 2
C'est ça. Et ensuite, on compte le nombre d'arrêtes qui franchissent cette frontière, donc les ponts qui lient encore la moitié A à la moitié B. On va appeler ce nombre M.
Intervenant 1
Ok, je suis suis. On a notre nombre de ponts restants.
Intervenant 2
Et en divisant ce nombre de ponts par la taille de la moitié du réseau, on obtient un ratio. La fameuse constante de Shager, c'est le ratio le plus faible possible parmi absolument toutes les découpes qu'on pourrait imaginer.
Intervenant 1
Hein, je vois. C'est l'identification chirurgicale de la plus grande faiblesse du réseau, en fait. La ligne de faille optimale.
Intervenant 2
C'est une excellente façon de le formuler.
Intervenant 1
Du coup, si je prends un graphe hyper vulnérable, disons un grand cercle de points, juste connectés les uns à la suite des autres. Comme un anneau.
Intervenant 2
Ouais, le cercle parfait.
Intervenant 1
Pour isoler une moitié de cet anneau, il suffit de couper seulement deux petites arêtes, une de chaque côté. Donc, là, la constante doit être minuscule. Proche de zéro, non ?
Intervenant 2
Absolument. La fragilité est totale. Pour un cercle de n sommets, la constante est de l'ordre de 1 sur n. Ce qui veut dire que plus le cercle s'agrandit, plus la solidité tend vers zéro.
Intervenant 1
D'accord.
Intervenant 2
Mais pour un graphe expanseur, la règle bascule complètement. La constante de Scheiger ne s'effondre jamais. Elle reste bloquée à une valeur planchée strictement positive, disons 1 dixième.
Intervenant 1
Attends, ça veut dire quoi concrètement ce 1 dixième ?
Intervenant 2
Ça signifie qu'il est mathématiquement impossible de scinder le réseau en deux parties égales sans devoir trancher, au minimum, 10% de la totalité des
Intervenant 1
câbles.
Intervenant 2
Et ce seuil de 10% se maintient même si le réseau grossit pour atteindre des milliards de sommets.
Intervenant 1
C'est là que ça devient vraiment fascinant pour le coup. Parce que si ce comportement défie à ce point notre intuition géométrique, l'histoire de sa découverte doit être assez spéciale, non ? On ne tombe pas là-dessus par hasard.
Intervenant 2
Ah ça c'est clair. Et l'histoire est même mouvementée. Pendant des décennies, on a attribué la naissance de cette théorie à Marc Pinsker en 1973. Il s'en
Intervenant 1
servait pour des problèmes naissants en informatique théorique, c'est ça ?
Intervenant 2
C'est ce qu'on croyait, ouais. Mais récemment, le mathématicien Larry Guth a bouleversé cette version officielle. Il a redécouvert un article, largement ignoré, qui avait été publié en 1967, donc six ans avant Pinsker.
Intervenant 1
Oh d'accord, et qui sont les auteurs ?
Intervenant 2
Yanis Bardin et le très célèbre Andrei Kolmogorov. Dans ce papier, il pose les fondations exactes de l'expansion et il prouve que ces structures paradoxales sont géométriquement possibles.
Intervenant 1
Attends, une petite seconde. L'informatique théorique dans les années 60, surtout en plein air soviétique avec Kolmogorov, c'était vraiment les tout premiers balbutiements. Pourquoi des pointures comme lui s'intéressaient à l'optimisation de réseaux informatiques qui n'existaient même pas encore ?
Intervenant 2
Eh bien, c'est justement là le rebondissement. La motivation première de Kolmogorov, ce n'étaient pas du tout les télécommunications ou l'informatique.
Intervenant 1
Ah bon ? C'était quoi alors ?
Intervenant 2
La neurobiologie spatiale.
Intervenant 1
La neurobiologie spatiale, tu veux dire le cerveau à le rire.
Intervenant 2
Exactement. Barzoudine a confirmé plus tard que Kolmogorov cherchait à résoudre un vrai casse-tête anatomique humain. Quand on regarde un cerveau, on remarque que presque tout le volume interne est occupé par la substance blanche.
Intervenant 1
Donc les longs axones, le câblage quoi.
Intervenant 2
Voilà. Et les processeurs de calcul, donc les neurones, la substance grise, ils sont expulsés vers l'extérieur, sur la toute fine pellicule du cortex.
Intervenant 1
Le matériel de calcul est relégué à la surface pour laisser toute la place au câblage à l'intérieur.
Intervenant 2
C'est ça. Et Kolmogorov s'est dit que ce n'était pas un hasard de l'évolution, mais une contrainte physique implacable de la géométrie en trois dimensions. Il pressentait que le cerveau était en fait un graphe expanseur naturel.
Intervenant 1
Donc un réseau robuste, mais économe. C'est génial de voir d'où vient l'idée. Mais comment Barsdin et Kolmogorov ont-ils fait pour transformer cette intuition biologique en une vraie preuve mathématique ?
Intervenant 2
En imposant des règles de physique très basiques. Imagine qu'on modélise ce réseau dans la réalité. On remplace chaque sommet par une bille rigide d'un centimètre de rayon.
Intervenant 1
Ok, j'ai les billes en
Intervenant 2
tête. Et chaque arête devient un tuyau physique, de la même épaisseur. La seule règle, c'est que ces tuyaux sont faits de matière solide, donc ils ne peuvent pas se traverser les uns les
Intervenant 1
autres. Logique, ils ont un vrai volume.
Intervenant 2
Voilà. Et la question qu'ils se sont posées, c'est quelle est la taille minimale de la boîte, disons un cube de côté R, pour arriver à tasser tout ce bazar dedans ?
Intervenant 1
Sur le papier, vu que chaque bille n'est reliée qu'à six autres tuyaux, on pourrait se dire qu'on peut tout compacter super facilement. On a l'habitude de voir des pelotes de laine bien serrées.
Intervenant 2
Eh bien, notre intuition nous trompe complètement ici. Leur démonstration, qui s'appuie sur l'argument de la coupe spatiale, prouve qu'un expanseur est impossible à tasser au-delà d'une certaine limite.
Intervenant 1
C'est-à-dire ?
Intervenant 2
Le côté du cube, donc la longueur R, doit obligatoirement grandir de manière proportionnelle à la racine carrée du nombre total de sommets. Pour faire simple, dès que le réseau devient grand, le volume requis devient gigantesque.
Intervenant 1
Alors, qu'est-ce que ça signifie concrètement ? Je pense qu'on peut utiliser une image pour vulgariser cette preuve de la coupe spatiale.
Intervenant 2
Vas-y, je t'écoute.
Intervenant 1
Imaginons notre cube géant rempli de billets de tuyaux et on vient le trancher pile en son milieu avec une immense lame de verre.
Intervenant 2
D'accord, la lame sépare l'espace en deux.
Intervenant 1
Exactement. Elle sépare le réseau en deux moitiés égales. Si on retire la lame et qu'on regarde la surface de verre, qu'est-ce qu'on y voit ?
Intervenant 2
On verrait plein de petits disques.
Intervenant 1
Ouais, les sections des tuyaux qu'on vient de trancher.
Intervenant 2
C'est ça. Et c'est là que la constante de Shager, dont on parlait tout à l'heure, entre en jeu. Comme c'est un expanseur, la constante nous certifie qu'on a dû sectionner une énorme proportion de tous les câbles du réseau.
Intervenant 1
Une quantité massive de câbles, au moins un dixième.
Intervenant 2
Voilà. Et comme chaque tuyau a une vraie épaisseur physique, l'air total de tous ces petits cercles étalés sur la lame, elle devient gigantesque.
Intervenant 1
Le mécanisme se referme ici. Parce que la lame de verre elle-même, elle doit rentrer dans le cube de côté R, non ? Tout à fait. Donc si la surface de la lame doit être immense pour accueillir toutes ces sections de câbles, la lame doit être géante. Et donc le cube, le fameux côté R, doit être énorme aussi. On ne peut pas avoir assez de surface de coupe dans une petite boîte.
Intervenant 2
C'est une démonstration brillante, simple et totalement implacable. La conclusion, c'est qu'un réseau qui exige peu de connexion mais garde une forte cohésion nécessite un espace de déploiement faramineux.
Intervenant 1
Ça valide complètement l'hypothèse de Kolmogorov sur le cerveau du coup.
Intervenant 2
Absolument. L'évolution a dû reléguer les neurones en périphérie parce que le volume généré par le croisement des câbles exigeait toute la place au centre.
Intervenant 1
Le mystère anatomique résolu par les géométries spatiales. Mais il y a quand même une zone d'ombre dans cette histoire. Bardzin, Kolmogorov et même Pinsker plus tard, ils ont prouvé que ça prenait de la place, ils ont prouvé que ça existait.
Intervenant 2
Mais ils n'en ont jamais dessiné un seul.
Intervenant 1
Ben oui.
Intervenant 2
Comment on en fabrique un, en vrai ?
Intervenant 1
C'est le détail ironique. Leurs preuves reposaient entièrement sur les probabilités. Ce qu'on appelle une construction sans réfléchir.
Intervenant 2
Sans réfléchir.
Intervenant 1
C'est-à-dire ?
Intervenant 2
Ils ont démontré que si tu prends un tas de points et que tu tires les connexions au sort, complètement au hasard, la probabilité que ça donne un graphe expanseur frôle la certitude absolue.
Intervenant 1
Ouais, alors ça soulève une question fondamentale. Moi, si je suis ingénieur réseau et que le gouvernement me demande de fibrer le pays, Et c'est ce grand classique de la tension mathématique entre l'existence probabiliste et la construction déterministe. Savoir
Intervenant 2
que l'objet existe grâce
Intervenant 1
au hasard ne nous aide pas à le construire. Et donc, qui a trouvé la solution ?
Intervenant 2
Grégory Margulis, en 1973. C'est le premier à avoir formulé une méthode de construction totalement explicite. Pas de tirage au sort, pas de hasard.
Intervenant 1
On est passé du hasard à la rigueur pure.
Intervenant 2
Exactement. Il a utilisé des outils très pointus en algèbre et en géométrie pour forcer l'existence de ces réseaux parfaits. Mais ce qui est fou, c'est que cette capacité à forcer l'existence d'un expanseur a ouvert des portes dans des domaines qu'on n'imaginait même pas.
Intervenant 1
C'est pour moi la transition la plus élégante de la conférence. Si Margulis peut forcer un graphe discret à exister, on s'est demandé si on pouvait imposer cette même complexité à un objet physique continu.
Intervenant 2
Comme un simple fil emmêlé dans l'espace.
Intervenant 1
Ce Mikhail Gromov dans les années 80.
Intervenant 2
Oui, la théorie des nœuds, c'est l'étude de ces boucles fermées, ces fils sans bout qui s'entrelacent. Et le défi de Gromov, c'était de trouver comment mesurer la complexité d'un nœud. Il a inventé le concept de distorsion.
Intervenant 1
J'adore l'image qu'ils utilisent pour ça. Pour bien visualiser la distorsion, il faut imaginer deux fourmis sur un nœud géant et hyper complexe.
Intervenant 2
Ouais, vas-y, explique-nous ça.
Intervenant 1
La première fourmi, la pauvre, elle doit marcher le long du fil. Elle se tape chaque boucle, chaque repli, elle suit toute la corde laborieusement.
Intervenant 2
Le chemin long, en gros.
Intervenant 1
C'est ça. La deuxième fourmi, par contre, elle a des ailes. Elle décolle et rejoint le même point direct en ligne droite à vol d'oiseau, en ignorant la corde. Un
Intervenant 2
nœud de cauchemar en fait. Ouais. Un nœud tellement retort que peu importe comment on essaye de le détendre, de l'étirer ou de le masser dans l'espace, il y aura toujours des points très proches à vol d'oiseau, mais séparés par des kilomètres de fils.
Intervenant 1
Un nœud dont la complexité ne peut pas être défaite.
Intervenant 2
Et pour prouver l'existence d'un tel monstre, Gromov, aidé de Larry Goss, ne sont pas allés chercher dans la théorie classique des courbes. Ils ont carrément importé l'architecture des graphes expanseurs.
Intervenant 1
Mais, et c'est la question que se posent tous ceux qui nous écoutent, comment on fait le pont ? Un graphe, c'est discontinu, ce sont des points et des lignes. Un nœud, c'est un flux continu, un seul fil refermé sur lui-même.
Intervenant 2
La technique est géniale. Ils ont modélisé le graphe expanseur avec des tuyaux dans l'espace, un peu comme l'expérience de la boîte de tout à l'heure.
Intervenant 1
OK, le réseau de tuyaux. Et
Intervenant 2
ils ont pris un seul et unique fil et ils l'ont fait voyager à l'intérieur de ces tuyaux. Ils ont tissé la corde en suivant méthodiquement les arêtes superconnectées du graphe, jusqu'à repasser partout et refermer la boucle.
Intervenant 1
Ils ont littéralement coulé un nœud continu dans le moule d'un graphe expanseur. Et comme on sait, grâce à l'analogie de la lame de verre, que le moule lui-même refuse d'être compressé ou simplifié, la boucle qui est à l'intérieur hérite de cette propriété.
Intervenant 2
Exactement, le réseau discret verrouille la complexité du nœud continu. Il devient impossible à démêler. C'est l'unité éclatante des mathématiques en action.
Intervenant 1
C'est fou de se dire qu'une idée née de la densité de notre cerveau blanc a servi à optimiser des réseaux informatiques pour finir par résoudre un casse-tête sur les nœuds géométriques. La boucle est vraiment bouclée.
Intervenant 2
C'est une très belle synthèse. Mais si l'on relie tout ça à une perspective un peu plus actuelle, un retour à la réalité informatique, il y a un dernier détail assez troublant.
Intervenant 1
Ah oui, le mur computationnel.
Intervenant 2
C'est ça, on sait construire ses graphes avec Margulis, on connaît leur géométrie, mais si on te donne un réseau naturel inconnu et qu'on te demande de vérifier formellement avec un supercalculateur si c'est un expanseur parfait, c'est un cauchemar.
Intervenant 1
Parce qu'il faut calculer cette fameuse constante de Shiger exact et donc examiner toutes les manières possibles de le couper en deux.
Intervenant 2
Voilà, et pour un réseau de N sommets, le nombre des découpes à tester, c'est 2 à la puissance N.
Intervenant 1
C'est exponentiel.
Intervenant 2
C'est une inefficacité brutale. Avec juste quelques centaines de points, le calcul demande plus d'opérations que ce que tous les ordinateurs de la planète pourraient faire depuis le Big Bang.
Intervenant 1
C'est juste impossible en fait. Et ça amène une réflexion finale que je trouve assez provocatrice, sur laquelle on peut laisser notre audience méditer. Vas-y, je t'écoute. Si vérifier mathématiquement ce niveau d'optimisation demande un temps incalculable, combien de graphes expanseurs d'une perfection absolue se cachent à cet instant même tout autour de nous ? Je veux dire, sous nos yeux.
Intervenant 2
Ouais, dans les structures naturelles, je veux dire.
Intervenant 1
Ben oui, que ce soit les immenses réseaux mycorhiziens sous les forêts, les courants océaniques ou même les synapses qui s'activent pour nous permettre d'avoir cette discussion, la nature regorge probablement de ses chefs-d'œuvre de robustesse géométrique. Mais nos ordinateurs manquent tout simplement de puissance pour les identifier.
Intervenant 2
Le monde naturel est sans doute le plus grand ingénieur d'expenseurs au monde. Et on n'a juste pas les moyens algorithmiques de le prouver.
Intervenant 1
Eh bien, merci d'avoir suivi cette plongée au cœur des articles du magazine Tangente avec nous. On espère que cette exploration des graphes expanseurs continuera de stimuler la curiosité de quiconque nous écoute.
Intervenant 2
Merci, et gardez l'esprit ouvert aux mathématiques qui nous entourent.
Intervenant 1
Restons attentifs à ces architectures invisibles qui tissent silencieusement les structures de notre monde. À très bientôt.
À écouter ensuite
Des épisodes qui partagent une playlist, une figure ou un domaine avec celui-ci.
23 sept. 2019 · 20 min
18 août 2025 · 14 min
18 août 2025 · 10 min
21 avr. 2023 · 21 min
21 avr. 2023 · 16 min
9 avr. 2024 · 14 min