À la recherche des structures cachés dans les réseaux aléatoires

Avec Nicolas Curien

 

Comment naissent les réseaux qui structurent nos vies, qu’ils soient naturels ou générés par l’homme ? Existe-t-il des logiques communes qui relient les réseaux sociaux, le réseau formé par une forêt ou par les cellules de notre corps ? Depuis plusieurs décennies, les mathématiciens cherchent à comprendre ce qui se passe lorsqu’un réseau se crée de manière totalement spontanée et aléatoire. Une structure ou des propriétés géométriques peuvent-elles émerger ?

 

Les structures qui émergent du hasard

Deux figures clés, Paul Erdős et Alfréd Rényi, ont mis au point le modèle d’Erdős-Rényi pour étudier ces réseaux, appelés graphes aléatoires. Dans un graphe, les sommets (ou nœuds) représentent des entités (comme des individus), tandis que les arêtes représentent les liens entre elles. Erdős et Rényi ont montré qu’au départ, quand il y a peu de connexions, le réseau est très fragmenté. Mais à mesure que les connexions se multiplient, un seuil est atteint où le réseau forme un ensemble presque totalement connecté quasi instantanément. Ce réseau dense a alors un diamètre paradoxalement petit. Cela signifie que chaque individu est relié aux autres par un faible nombre de connexions. C’est ce qu’on appelle la propriété du petit monde : on estime que nous sommes tous reliés à Cristiano Ronaldo ou Beyoncé par un maximum de six degrés de connexions.

Dans cette lignée, Nicolas Curien étudie les formes géométriques des grands graphes aléatoires en appliquant des contraintes simples, d’ordre topologique. Par exemple, on peut imposer que le graphe soit planaire, c’est-à-dire qu’on puisse le dessiner sans croisement sur une carte en deux dimensions. On peut également imposer que le graphe soit un arbre, c’est-à-dire qu’il n’y ait qu’un seul chemin possible pour aller d’un point à un autre.

À partir de ces contraintes, il analyse les propriétés des graphes qui émergent. Est-ce que ces contraintes topologiques ont changé la forme du graphe ? Quelle sera la distance maximale entre deux points ? En effet, le fait d’imposer que le graphe aléatoire soit un arbre génère, pour un même nombre de points, des réseaux beaucoup plus étendus.

 

Archéologie des connexions : retrouver les origines d’un réseau complexe

Au-delà des propriétés géométriques des graphes, Nicolas Curien et ses collaborateurs mènent une « archéologie » du réseau, tentant de déduire la formation historique du réseau à partir de sa structure actuelle. En analysant les connexions, ils cherchent à identifier un petit groupe d’individus, parmi lesquels se trouve très probablement le « fondateur » du réseau.

Cette découverte peut avoir des implications intéressantes dans des domaines aussi variés que la biologie, l’archéologie et l’informatique. Par exemple, elle peut aider des biologistes à reconstituer des réseaux d’espèces ayant vécu il y a des millions d’années, ou encore à estimer la forme des premières espèces dans un réseau évolutif. Les théorèmes développés par Nicolas Curien et d’autres chercheurs permettent ainsi aux statisticiens d’élaborer des estimations à partir de réseaux réels, applicables dans divers champs scientifiques.

 

Modéliser des liens de différentes natures

Dans un réseau, tous les liens ne sont pas toujours de même nature. Il est intéressant pour les mathématiciens d’ajouter une pondération aux arêtes reliant les points. C’est le cas dans les réseaux routiers où les routes sont pondérées en fonction de la vitesse de déplacement : autoroutes, routes nationales, départementales, chemins forestiers, etc.  Nicolas Curien, en collaboration avec Guillaume Blanc et Jonas Kahn, ont ainsi étudié un modèle de réseau autoroutier inventé par David Aldous et Wilfrid Kendall. Dans ce modèle, les autoroutes sont rares, les routes nationales plus fréquentes, les départementales encore plus, et les chemins forestiers très nombreux. Disposées de manière aléatoire dans un plan, ces routes permettent d’analyser la nature des connexions entre différents points.

Ainsi si deux points sont situés à 20 km l’un de l’autre, le trajet le plus efficace ne passera probablement par une autoroute. En revanche, pour rejoindre un point situé à 500 km du point de départ, il sera probablement nécessaire d’emprunter au moins une autoroute et une route nationale.  L’un de leurs théorèmes, le théorème Geodesics do not pause en route, démontre mathématiquement que le trajet le plus court ne subira jamais un ralentissement marqué (quasi-arrêt) en milieu de parcours. Autrement dit, entre deux points éloignés, il n’existera jamais une trajectoire du type : départementale, nationale, autoroute, nationale, départementale, chemin forestier, départementale, nationale, autoroute, nationale, départementale.

Les travaux de Nicolas Curien illustrent comment l’étude de modèles aléatoires permet de dégager des théorèmes universels. Vu la complexité des graphes, il est souvent difficile, voire impossible, de construire des exemples spécifiques pour prouver l'existence de certaines propriétés. Il est parfois plus efficace d'analyser un grand nombre de graphes générés aléatoirement. En observant les caractéristiques qui émergent fréquemment dans ces structures aléatoires, on peut dégager des propriétés générales. Cette méthode, connue sous le nom de méthode probabiliste, est utilisée dans de nombreux domaines mathématiques.

 

Nicolas Curien est un mathématicien français, membre du laboratoire d’Orsay et professeur à l'Université Paris-Saclay, spécialisé dans les probabilités et la géométrie aléatoire