Mathématiques et réseaux | Origine des graphes

Carte de l’internet en tant qu’infrastructure : les nœuds sont des routeurs et les liens
des câbles entre-eux (carte obtenue par une exploration locale).

Qui parle avec qui ? Qui achète quoi ? Quelle entreprise dépend de quelles autres ? Quelle protéine réagit avec quelles autres ? Quel papillon pollinise quelles fleurs ? Quels sont les flux entre les villes ? Comment se propagent une épidémie, une idée, ou un nouveau produit ? A quoi ressemble l’internet ? Qui influence qui ? On peut multiplier ces interrogations à l’infini.

La notion de réseau est au cœur de toutes ces questions et notre planète en est recouverte : réseaux de transport (routier, ferroviaire, aérien, etc.), réseaux naturels (hydrauliques, biologiques, etc.), réseaux d’infrastructures (distribution de l’eau et de l’électricité, internet, etc.), ou encore réseaux sociaux (amitiés, collaborations, échanges commerciaux, influences, etc.)… Les réseaux sont partout ! Ils jouent un rôle clé dans le marketing, la sécurité ou encore la politique, ainsi que dans de nombreuses problématiques telles que le contrôle des épidémies, la transmission de l’information ou la compréhension et la protection de la vie.

Afin d’en étudier la structure et les propriétés fondamentales, tous ces réseaux sont souvent modélisés comme des graphes, c’est-à-dire des ensembles d’objets (appelés sommets) auxquels on adjoint les relations entre eux (appelées arêtes). Les graphes sont des objets mathématiques extrêmement classiques –dont l’origine remonte à Euler– en plein essor depuis l’avènement de l’informatique.

On pourrait penser que les graphes ainsi obtenus, modélisant des objets aussi divers que l’internet, les réactions chimiques ou la société, ne se ressemblent guère. Cependant, on a découvert à la fin des années 1990 que l’immense majorité de ces graphes avaient de nombreuses propriétés en commun, ce qui a contredit les hypothèses avancées jusqu’alors. Par exemple, ils sont le plus souvent constitués de communautés, c’est-à-dire de groupes densément connectés en interne mais faiblement interconnectés entre eux. Ainsi, si on prend deux personnes dans le monde, elles ne se connaissent probablement pas. Si on prend deux personnes ayant un ami en commun, alors la probabilité qu’elles soient elles-mêmes amies est bien plus forte.

Cette propriété, intuitive dans le cas des relations sociales, est en fait très générale. De même, on observe dans l’immense majorité des cas une très forte hétérogénéité dans le nombre de connexions. Alors que la plupart des éléments ont relativement peu de liens, certains en ont plus, d’autres bien plus, et quelques-uns encore bien davantage. La diversité règne en maître dans les réseaux réels. Il est donc hors de question de les modéliser par des ensembles d’entités relativement similaires comme on le faisait encore récemment (et peut-être même encore un peu).

Arbre de diffusion d’informations dans un
réseau social de type blog.

Mais il y a plus important encore : les questions qu’on se pose sur ces divers réseaux sont très similaires. Ainsi, la plupart de ces réseaux ne sont que partiellement connus, et la question de savoir ce qu’on peut dire sur le réseau réel à partir d’une vision partielle (et souvent biaisée et même erronée) est très transversale. La question de la description de grands réseaux est aussi générale : quels sont les bons mots, les bonnes notions permettant de décrire de façon intuitive les relations entre milliers ou millions d’entités ? Allons plus loin : comment peut-on construire des graphes ressemblant aux réseaux réels ? Répondre à cette question est crucial pour mener des simulations ainsi que pour démontrer des résultats mathématiques. Enfin, les questions de calcul sont omniprésentes dans tous ces cas : comment stocker, manipuler et exploiter de si grandes structures, comment trouver les communautés qu’elles contiennent, comment y diffuser de l’information de façon efficace ?

Les réseaux sont donc partout, mais heureusement pour nous, ils se ressemblent et soulèvent des questions similaires. Nous pouvons donc les étudier comme un tout, ce qui donne lieu à l’émergence, depuis quelques années, d’un nouveau champ de recherche, très interdisciplinaire et très actif, appelé la science des réseaux. Dans ce domaine, toutes les compétences sont utiles, des plus théoriques aux plus empiriques, car l’essentiel reste à faire et il est clair que les attentes sont extrêmement fortes, tant d’un point de vue fondamental qu’applicatif.

Brève rédigée par : Matthieu Latapy (LIP6, CNRS et Université Pierre et Marie Curie).

Pour en savoir plus :