graphes

Dans un massif montagneux, il y a des sentiers que l'on peut réduire à un point en suivant une vallée plate. Mais il existe aussi des itinéraires en boucle impossibles à contracter sans franchir une crête.

Un cartographe qui ne dessine ni montagnes ni rivières, mais les liens invisibles entre les électrons : c'est ainsi qu'on pourrait décrire ce nouveau réseau de neurones. Au lieu des coordonnées atomiques, il prend les orbitales moléculaires et trace un graphe dont les nœuds sont les orbitales et les arêtes, les mesures de leur intrication quantique.

Un cartographe qui ne dessine ni montagnes ni rivières, mais les liens invisibles entre les électrons : c'est ainsi qu'on pourrait décrire ce nouveau réseau de neurones. Au lieu des coordonnées atomiques, il prend les orbitales moléculaires et trace un graphe dont les nœuds sont les orbitales et les arêtes, les mesures de leur intrication quantique.

Un livre de recettes sans liste de courses, voilà ce que découvre un scientifique face à un schéma de réactions chimiques. Les flèches et les formules sur le papier semblent cohérentes, mais dès qu'on cherche en laboratoire des molécules qui se comporteront exactement comme prévu, la véritable chasse au trésor commence.

Un stade bondé entend pour la première fois la voix du commentateur – et aussitôt, toute la foule s’anime. Le message retentit encore et encore. Seule une poignée de spectateurs, dans les rangs voisins, réagit. C’est à peu près ainsi que se comportent les réseaux de neurones dans les organoïdes cérébraux – ces mini-cerveaux cultivés en laboratoire.

Une carte routière ordinaire avec le trafic, c'est une multitude de nombres. Les envoyer tous en entier prend trop de temps. Mais on peut réduire le volume sans perdre l'essentiel. Les chercheurs ont trouvé une solution ingénieuse : d'abord, redessiner la carte pour que les rues deviennent des points et les intersections des passerelles entre ces points.

Un enfant qui explore un appartement inconnu rampe d'un objet à l'autre et mémorise ce qu'il voit depuis chaque coin. C'est ainsi que le cerveau construit une carte mentale — un modèle interne de l'espace. L'algorithme gradCSCG fonctionne sur le même principe : il reçoit un flux vidéo d'une caméra et dessine lui-même le plan du lieu, en s'appuyant uniquement sur le changement des images.

L'analyse des données sur Internet ou dans les systèmes de capteurs a longtemps ressemblé à une tentative de diriger un orchestre où chaque musicien serait enfermé dans sa cabine, le chef ne pouvant quitter son pupitre.

L'arbre généalogique se transforme en écheveau si l'on tient compte des enfants adoptés et des remariages. L'évolution ressemble souvent à un tel écheveau : bien que le modèle standard dessine un arbre des espèces bien propre, en réalité les gènes voyagent non seulement par héritage, mais aussi directement entre organismes non apparentés.

Les systèmes de recommandation qui décident quel message vous verrez ensuite fonctionnent sur des réseaux de neurones profonds composés de milliers d'opérations — des graphes de calcul complexes (des schémas d'opérations sur les données).

7 278 601 292 779 396 715. C'est exactement le nombre de graphes cordaux différents (des graphes sans cycles induits de longueur quatre ou plus) que l'on peut construire sur vingt sommets, en considérant les structures sans noms.

Dans la salle d'audience, une chaîne de caractères est présentée en entrée. Douze jurés (les chemins de calcul) l'examinent symbole par symbole. Chacun peut déclarer « coupable » (accepter) ou « non coupable ». Pour un automate non déterministe ordinaire (NFA), un seul vote « pour » suffit.

Une immense feuille de papier est posée sur la table. Le cartographe tente d'y faire tenir tous les paysages imaginables : chaînes de montagnes, gorges enchevêtrées, plaines sans fin. Chaque paysage est un groupe de type fini, et la carte est son graphe de Cayley, le portrait graphique du groupe, où les sommets sont les éléments et les arêtes les liens entre eux.

À l'intérieur d'un cristal se déroule un ballet invisible : les moments magnétiques des atomes, tels des danseurs, tantôt s'alignent à l'unisson, tantôt se dispersent en opposition de phase. La chorégraphie est dictée par l'échange quantique — une musique sensible à la géométrie des liaisons.

Un neurone ressemble à un circuit électrique avec des piles et des résistances variables. Le rôle des résistances est joué par les canaux ioniques — des pores protéiques dans la membrane qui s'ouvrent et se ferment, laissant passer des particules chargées.

Les détecteurs de rayons X fonctionnent comme un nid d'abeilles : dans les alvéoles hexagonales, des particules scintillent de temps en temps. Les algorithmes classiques étirent ces alvéoles sur une grille carrée, ce qui fait apparaître de faux fantômes de polarisation.

Chercher la bonne molécule parmi des milliards de possibilités, c'est un peu comme chercher un grain de riz dans un sac de riz. Pour ne pas tout éplucher à la main, les chimistes font de plus en plus appel aux réseaux de neurones. Mais les grands modèles exigent des ordinateurs puissants, et les petits manquent souvent de vision d'ensemble.

Une éponge de cuisine imbibée de sirop : à certains endroits, il y a plus de sirop, et le doigt colle immédiatement ; à d'autres, il effleure à peine. C'est à peu près ainsi qu'est faite la surface d'un catalyseur. Les molécules ne réagissent pas partout, mais en des points particulièrement collants — les sites actifs.

Concevoir des machines, c'est un peu comme faire de la pâtisserie : il faut savoir exactement où la pâte va se déchirer. Les anciens calculs informatiques vérifient chaque point de la pièce pendant des heures — comme si on mesurait toute la casserole pour être sûr que l'anse ne se détache pas.

L'espace-temps est souvent imaginé comme un tissu lisse. Mais à l'échelle microscopique, ce tissu pourrait ne pas être continu, mais constitué d'« atomes » individuels — des événements reliés par la causalité. Cette vision du monde s'appelle la théorie des ensembles causaux.

Un réseau social ressemble à une ville : il y a des quartiers géants et des ruelles minuscules. Quand un algorithme y cherche des groupes soudés, il sort souvent deux ou trois énormes ensembles et beaucoup de petits fragments. Mais le client — par exemple, une municipalité — a besoin de quartiers à peu près de la même taille pour répartir équitablement les cliniques ou les écoles.

La ville respire et se nourrit, son sang circule dans les routes. Mais tandis que les ingénieurs tracent des lignes droites, la nature peaufine depuis des millions d'années le réseau idéal : les rivières trouvent infailliblement leur chemin vers la mer, la feuille est parcourue de nervures sans un seul vaisseau superflu.

À une fête, les invités ne discutent pas seulement en tête-à-tête, ils se rassemblent en petits cercles selon leurs centres d'intérêt : trois discutent cinéma, quatre parlent sport. Un schéma d'amitiés classique, comme la liste de contacts d'un téléphone, ne peut pas capturer cela — il ne voit que les liens « un à un ».

Après une partie de Scrabble, le plateau ressemble à une mosaïque : les lettres sont éparpillées mais forment un motif connecté — des îlots de mots au milieu d'une mer de cases vides. Un tel motif peut être décrit mathématiquement, mais cela nécessite généralement des règles complexes.

Chaque atome de carbone dans une molécule porte un passeport : l'énergie avec laquelle ses électrons les plus profonds restent sur leurs orbites. Cette énergie réagit finement à l'environnement : qu'un oxygène ou une double liaison apparaisse à proximité, et le chiffre du passeport change.

Étudier la naissance des galaxies nécessite de simuler des milliards d'années de croissance de la matière noire et de formation d'étoiles — même les superordinateurs s'y attellent lentement.

Chaque contraction du cœur peut être représentée par un point sur une feuille de papier. Des milliers de points se fondent en un nuage. L'algorithme Mapper transforme ce nuage en réseau : il relie les points dont le comportement est similaire et les colore en fonction de la force du flux sanguin.

Plan d'une ville : les intersections sont les nœuds, les rues les connexions. Pour que l'algorithme comprenne la structure, chaque nœud doit être étiqueté. L'approche classique — modèle standard — attribue des étiquettes simples, comme des numéros de maisons.

Un grain de beauté sur la peau ressemble à une mosaïque de morceaux colorés. Chaque morceau est une petite zone de l'image où la couleur et la texture ne changent presque pas. On appelle ces morceaux des superpixels. Si on les relie par des lignes, on obtient un réseau semblable à un plan de métro : les stations sont les morceaux, et les lignes sont les connexions entre eux.

Frappez un diapason : il émet une note pure. Mais si le diapason tremble et que des gens parlent autour, le son n'est plus parfait. Il en va de même pour les molécules : chacune absorbe une couleur de lumière spécifique, mais à cause de ses propres vibrations et des bousculades de ses voisins, cette couleur s'élargit légèrement.

Un réseau de connaissances dense : chacun est lié à presque tout le monde, et dans cette toile, il est difficile de comprendre qui est vraiment important. Trop de fils — l'ordinateur s'étouffe, la modélisation patine. Des chercheurs ont trouvé comment éclaircir ces réseaux sans perdre l'essentiel. L'idée est de supprimer les connexions qui ne participent pas aux chemins les plus courts.

Les particules dans un accélérateur peuvent osciller dans deux directions transversales à la fois, et ces oscillations ne sont pas toujours indépendantes. Si vous poussez un pendule dans une direction et qu'il se met à osciller aussi latéralement, ce sont des oscillations couplées.

La maladie d'Alzheimer ressemble à un écheveau de fils emmêlés : des milliers de gènes s'entrecroisent, et il est difficile de savoir lesquels se rompent en premier. Autrefois, les scientifiques cherchaient les gènes importants en comptant simplement le nombre de connexions de chaque nœud dans le réseau.

À l'intérieur de chaque cellule, le travail ne s'arrête jamais : les protéines communiquent, les gènes s'activent et se désactivent, et les dysfonctionnements de ce système mènent à des maladies.

Une ville peut être étudiée de différentes manières : l'un cartographie les rues, un autre les flux de voitures, un troisième la densité de population. Les cartes ne coïncident pas, mais elles décrivent le même lieu.

La mouche à fruits, ou drosophile, est une créature minuscule avec un cerveau de la taille d'une graine de pavot. Il contient environ cent mille cellules nerveuses, et les scientifiques en ont déjà dressé une carte complète des connexions – comme un plan de métro urbain, où les stations sont les neurones et les lignes, les connexions entre eux.

Une marche quantique ressemble à un homme ivre qui tourne au hasard à chaque intersection. Mais au lieu de rues, il y a des nœuds de graphe, et au lieu de pas, des transitions quantiques. Les scientifiques ont découvert que cette marche possède une mesure cachée : la complexité de Krylov.

Une carte de ville où, au lieu des rues, on aurait les vitesses des voitures, et au lieu des immeubles, la teneur en métaux des étoiles. Avec une telle carte, on peut repérer le centre et les périphéries sans connaître les distances exactes. C'est précisément cette approche qu'ont adoptée les astronomes pour notre Galaxie, en utilisant les diagrammes « longitude–vitesse » (ℓ–v).

Le cortex cérébral ressemble à une feuille de papier froissée : il a une épaisseur, des courbures et une profondeur de plis. Avec l'âge, cette feuille se modifie de manière inégale – par endroits elle s'amincit, par endroits elle perd la netteté de ses courbures. Autrefois, les médecins évaluaient l'âge du cerveau dans son ensemble, comme s'ils regardaient la feuille de loin.

Deux graphes sont considérés comme identiques si leur « relief » correspond. Deux cartes avec des montagnes et des vallées : même si le dessin diffère, les hauteurs et les pentes peuvent être les mêmes.