Que sait-on compter sur un graphe ? Partie 1.

Des graphes du monde qui nous entoure

Piste bleue Le 9 juillet 2020  - Ecrit par  Pierre-Louis Giscard Voir les commentaires (3)

Compter les chemins sur un graphe est assez facile et nous donne accès à pléthore d’informations inattendues sur le monde qui nous entoure. Mais gare à ne pas demander des choses trop subtiles...

Qu’est-ce qu’un graphe ?

Un graphe est un objet mathématique assez simple : il s’agit d’un ensemble de points, appelés nœuds, et de traits appelés arêtes, reliant ces points. Mais, attention, la seule chose qui compte dans un graphe, c’est de savoir quels nœuds sont reliés les uns aux autres par des arêtes. En particulier, la forme des arêtes ne compte pas, ni même la position exacte des nœuds ou encore le nom que nous pourrions leur donner. On peut allonger les arêtes, les tordre, les croiser, déplacer des nœuds ici ou là et le graphe est, mathématiquement, toujours le même :

PNG - 277.5 ko
Ces deux graphes sont les mêmes, voyez-vous pourquoi ?

On peux considérer des graphes plus compliqués que celui ci-dessus. Par exemple, nous pourrions avoir plusieurs arêtes entre deux mêmes nœuds (nous aurions alors un multigraphe), plusieurs nœuds reliés dans une seule hyperarête (une hyperarête est essentiellement un « sac de nœuds »... plus sérieusement c’est un ensemble non vide de nœuds et le graphe est alors dit hypergraphe), ou bien encore des arêtes ne pouvant être empruntées que dans un sens (appelées arêtes dirigées), ou des arêtes allant d’un nœud à lui-même (appelées boucles). Mettons de côté toutes ces choses « exotiques » et concentrons-nous sur les graphes pour lesquels il y a toujours soit une soit zéro arête entre deux nœuds, ces arêtes ne sont pas dirigées et il n’y a aucune boucle. Ces graphes sont appelés graphes simples.

Des graphes dans la nature

Les graphes simples sont très utiles pour comprendre les systèmes complexes. En effet, un graphe peut naturellement modéliser des entités (représentées par des nœuds) en interaction (les arêtes). Par exemple, nous pourrions considérer le graphe social formé par des gens (un nœud représentant une personne) et leurs relations d’amitié (une arête représentant un tel lien). Ou bien encore le graphe biochimique des protéines (les nœuds) qui peuvent interagir chimiquement l’une avec l’autre dans un organisme vivant (les arêtes) ; le graphe du réseau urbain représentant les carrefours (nœuds) et les rues les connectant (arêtes), etc.

L’analyse mathématique de tels graphes a déjà porté de nombreux fruits dans divers domaines. L’idée est que l’on peut comprendre quelque chose de profond sur le système représenté par le graphe en étudiant ce dernier. Par exemple, on peut penser que la personne $P$ ayant le plus grand nombre d’amis est aussi celle qui participe le plus à la diffusion de rumeurs. Or, cette personne $P$ correspond au nœud $n_P$ du graphe social qui a le plus grand nombre de nœuds voisins $n'$, c’est-à-dire de nœuds atteignables depuis $n_P$ en utilisant une seule arête $n_P \,\bullet\!—\!\bullet\, n'$. Le nombre de voisins d’un nœud est appelé degré du nœud. De manière générale l’idée que l’entité (personne, protéine, carrefour...) la plus « importante » dans un système complexe $S$ est celle dont le nœud a le plus haut degré dans le graphe $G_S$ représentant $S$ est assez bonne. Par exemple, ce simple critère permet d’identifier les protéines essentielles d’un organisme, c’est-à-dire celles dont la désactivation (par modification d’ADN ou par voie médicamenteuse) est létale pour cet organisme.

Réseau d’interactions entre 1458 protéines chez la levure Saccharomyces cerevisiae. Ici, $13$ des $20$ protéines ayant au moins $15$ voisins sur le graphe, soit $62\%$ de celles-ci, sont essentielles à la levure, c’est-à-dire que leur désactivation provoque la mort de l’organisme.

Nous nous trouvons donc face à une mine d’or : en analysant mathématiquement le graphe représentant un système complexe, il semble que l’on puisse effectivement comprendre celui-ci et faire des prédictions a priori loin d’être évidentes. Or, compter le nombre de voisins d’un nœud sur un graphe est très simple. Nous pourrions faire bien plus et ainsi, peut être, comprendre plus en détail le système complexe $S$ qui nous intéresse.

Les triangles : des motifs simples dans les graphes

Nous pourrions compter par exemple, pour chaque nœud, le nombre de triangles auxquels celui-ci participe dans le graphe $G_S$ ou simplement le nombre total de triangles. S’il y a sensiblement plus de triangles que ce à quoi nous pourrions nous attendre dans des graphes aléatoires—obtenus en tirant des nœuds et des arêtes au hasard—alors c’est que les triangles jouent bel et bien un rôle particulier dans le système complexe $S$. Dans de tels cas, nous parlons de motifs dans le graphe. De tels motifs ont effectivement été découverts, par exemple dans les réseaux sociaux qui comportent beaucoup plus de triangles que les graphes aléatoires de même taille ou bien dans les réseaux biologiques où des motifs correspondent à des complexes protéiniques.

Considérons par exemple le réseau formé par les relations entre 16 tribus de l’Est de la Chaîne Centrale de la Papouasie Nouvelle-Guinée, étudiées par l’anthropologue Kenneth Read au début des années 1950 :

Réseau d’interaction entre tribus de Nouvelle-Guinée

Ici, chaque tribu est représentée par un nœud portant le nom de la tribu. Deux tribus en interaction directe sont reliées par une arête. Celle-ci est ${\color{red}{\text{rouge}}}$ s’il y a conflit et ${\color{blue}{\text{bleue}}}$ si au contraire il s’agit d’une alliance. Une analyse de ce graphe montre que seulement $9$ des $68$ triangles du graphe (soit $\sim13\%$) comportent une arête rouge (conflit) et deux arêtes bleues (alliances) : on fait donc rarement la guerre contre l’ami d’un ami. Au contraire, on trouve beaucoup de triangles avec deux arêtes rouges et une bleue.

Voyez-vous ce que cela veut dire ?

Prenons le triangle visible à droite du graphe, avec les tribus Ove, Alika et Gavev.
L’arête bleue signifie que les tribus Ove et Alika sont alliées. Les deux autres arêtes, rouges, du triangle indiquent que ces deux tribus sont en guerre contre un ennemi commun, ici Gavev. En d’autres termes, « l’ennemi de mon ennemi est mon ami » !

Remarquez que trouver les 68 triangles du graphe est loin d’être évident, nous verrons ceci plus en détails dans les parties 2 et 3. En tout cas, une fois ce travail fait, nous avons pu en tirer des observations anthropologiques intéressantes. Remarquablement, ceci est souvent vrai : le simple décompte de motifs dans un graphe donne tant d’informations que l’on peut, par exemple, s’en servir pour prédire si une molécule provoque des mutations dans le corps humain. Concrètement, on compare les motifs de la molécule à ceux de molécules dont on connaît déjà la mutagénicité, c’est-à-dire dont on sait si elles provoquent des mutations ou non. L’idée est qu’une molécule toxique doit être structurellement similaire à une autre molécule toxique déjà identifiée. En dépit de la simplicité déconcertante de cette idée, ce processus donne la bonne réponse plus de 9 fois sur 10 ! Voici le genre de molécules dont on peut déterminer la mutagénicité par cette méthode :

Structures chimiques de la digitonine (à gauche) et de la sterigmatocystine (à droite). La digitonine n’est pas toxique mais la sterigmatocystine est toxique et provoque des mutations. On la trouve dans des moisissures, notamment dans des fromages pas trop frais...

Ce que l’on sait compter

Pour arriver à compter des objets comme des triangles et trouver des motifs, étendons un peu le problème. Essayons d’abord de compter toutes les façons d’aller sur un graphe $G$ d’un nœud $n$ à un nœud $n'$ (qui pourrait être le même que $n$) en empruntant exactement $\ell$ arêtes. Une telle trajectoire empruntant une succession d’arêtes contiguës est appelée chemin sur le graphe et $\ell$ est la longueur du chemin. Un chemin qui part d’un nœud $n$ et se termine également en $n$ est appelé cycle. En général un chemin peut passer et repasser par n’importe quel nœud du graphe, du moment que les arêtes le permettent.

Compter tous les chemins de longueur $\ell$ allant de $n$ à $n'$ sur $G$ est en fait assez aisé. Pour cela, reconsidérons par exemple le graphe vu plus haut :

Nous avons donné des noms aux nœuds—ces noms étant simplement des entiers—afin de pouvoir parler plus précisément de chemins sur ce graphe. Considérons par exemple un chemin $w$ de longueur $\ell=5$ allant du nœud $1$ au nœud $3$, en écrivant $w$ comme la succession des nœuds qu’il visite, $w=132453$, ce qui donne :

On observe qu’après avoir emprunté $\ell-1=4$ arêtes, le chemin arrive sur le nœud $5$ qui est un voisin du nœud $3$ dans le graphe. Clairement, cette observation se généralise très bien : pour aller d’un nœud $n$ à un nœud $n'$ en empruntant exactement $\ell$ arêtes, il faut aller de $n$ à un voisin de $n'$ en exactement $\ell-1$ arêtes, la dernière arête étant forcément utilisée pour finir en $n'$ ! Réciproquement, n’importe quel chemin qui va de $n$ à un voisin de $n'$ en $\ell-1$ étapes donne naissance à exactement un et un seul chemin allant de $n$ à $n'$ en $\ell$ étapes.

Il suit que le nombre total $\mathcal{N}_{n\to n'}(\ell)$ de chemins de $n$ à $n'$ empruntant exactement $\ell$ arêtes est égal à la somme totale du nombre de chemins $\mathcal{N}_{n\to m}(\ell-1)$ allant de $n$ à n’importe quel voisin $m$ de $n'$ en exactement $\ell-1$ étapes. C’est un bon progrès car nous avons réduit le problème du dénombrement des chemins de longueur $\ell$ à celui du dénombrement de chemins plus courts, de longueur $\ell-1$. En principe, il nous suffit de recommencer pour exprimer les quantités $\mathcal{N}_{n\to m}(\ell-1)$ elles-mêmes en termes de chemins de longueur $\ell-2$ allant de $n$ aux voisins de $m$, et de continuer jusqu’à remonter à des chemins de longueur 1 sur le graphe, qui sont les arêtes.

Remarque : Mathématiquement, nous pouvons synthétiser cette procédure en encodant le graphe dans un tableau de chiffres, appelé matrice. Ceci nous amènera à une belle formule, compacte et simple à évaluer pour compter les chemins que nous présentons dans la troisième partie de cette article, « Partie 3. Des matrices et des chemins ».

Les longs cheminements de notre recherche Google

Maintenant que l’on sait compter tous les chemins d’un graphe, cela nous donne déjà de nombreux outils d’analyse des réseaux. Par exemple, dans un graphe simple, le degré d’un nœud $n$ est égal au nombre de cycles de longueur 2 partant de $n$ puisque ces cycles sont chacun un aller-retour sur une arête. Nous retrouvons donc immédiatement l’information du nœud qui a le plus grand nombre de voisins.

Puisque nous avons tous les chemins, nous pouvons aller voir plus loin que les voisins. Par exemple il se pourrait qu’un nœud n’ait pas le plus grand nombre de voisins mais ait tout de même le plus grand nombre de 2ème ou de 3ème voisins (atteignables en empruntant 2 ou 3 arêtes) et de fait, soit important au fonctionnement du réseau qu’on cherche à analyser.

Mais pourquoi s’arrêter là ? Une idée est donc de considérer des cycles très très longs, beaucoup plus longs que la taille du graphe, pour qu’ils aient eu le temps de voir et revoir tous les nœuds puis de revenir au point de départ. On compare alors parmi tous les nœuds, celui qui donne naissance au plus grand nombre de cycles de longueur $\ell$ quand $\ell$ tend vers l’infini, ce que l’on dénotera $\ell\to\infty$. Cette procédure aboutit à un classement sur les nœuds identique à celui produit par l’algorithme PageRank que Google utilise pour classer les résultats de vos recherches internet. PageRank traite internet comme un graphe où les nœuds sont les sites webs et les arêtes sont des liens hypertextes entre sites.

Ici les nœuds 5 et 8 ont le plus grand nombre de voisins, mais 5 est plus important que 8 selon PageRank [1]. Et vous, ne trouvez-vous pas que 5 est plus « central » que 8 sur le graphe ?

Dans la seconde partie « Partie 2. Motifs et polygones », nous essaierons d’utiliser notre connaissance des chemins pour trouver et compter les motifs d’un graphe. Mais gare à ne pas trop en demander...

Post-scriptum :

Je remercie Shalom Eliahou et Bruno Martin qui m’ont proposé d’écrire un article dans Images des mathématiques et m’ont aidé lors de sa rédaction. Merci également aux relecteurs nathmel et Xanthopoulos pour leurs observations et questions !

Article édité par Shalom Eliahou

Notes

[1Voici le classement complet de l’importance des nœuds dans ce graphe selon PageRank, du plus important au moins important. Le signe = signifie que les nœuds sont ex-æquo : $5 > 8 > 1 > 16 = 17 > 18 = 6 = 7 > 9 =12= 14 = 13 = 11 = 10 > 4 = 2 = 3 = 15$.

Partager cet article

Pour citer cet article :

Pierre-Louis Giscard — «Que sait-on compter sur un graphe ? Partie 1.» — Images des Mathématiques, CNRS, 2020

Commentaire sur l'article

Voir tous les messages - Retourner à l'article

  • Que sait-on compter sur un graphe ? Partie 1.

    le 21 juin à 12:04, par Pierre-Louis Giscard

    Bonjour, merci de m’avoir signalé le soucis ! Je viens de refaire l’image, celle-ci devrait apparaître correctement d’ici quelques temps, lorsque l’éditeur aura eu le temps de l’approuver.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?