Didacticiel :
Analyse de réseaux : du degré des noeuds aux centralités

Le deuxième article sur la représentation du métabolisme et son analyse!

Pour rappel, le premier volet est ici!


Un grand nombre de phénomènes biologiques peuvent être représentés sous la forme d'un réseau. Qui n'a jamais entendu parler de réseaux d'intéraction protéine-protéine (fameux réseaux "PPI"), de réseaux de gènes ou encore de réseaux métaboliques? En fait, dès qu'il s'agit de représenter des connexions ou des intéractions entre des entités, que ce soit en biologie ou dans un autre domaine. Je pourrais citer, entre nombreux autres, la sociologie - pensez aux réseaux sociaux d'intéractions de personnes entre elles, la physique - notamment les réseaux électriques et ceux d'intéraction de différentes particules (sub)atomiques, la chimie - par exemple une molécule qui peut être représentée comme un réseau d'intéraction des atomes qui la constituent... et j'en passe! Pensez aussi aux réseaux que vous utilisez tous les jours, comme les réseaux routiers, les réseaux de transport, internet.... vous imaginez bien qu'il y a des gens qui se sont spécialisés dans l'analyse de réseaux! On parle d'ailleurs de plus en plus de "network science", qui cherche à rassembler les développements autour des réseaux réalisés dans différents domaines.

Buzz est d'accord avec moi! (Meme généré avec https://memegenerator.net/)

Tout ce qui va suivre dans cet article est applicable à peu près à n'importe quel type de réseau. Mais bon, ici, on est sur un blog de bioinfo, donc imaginons tous ensemble qu'on veut analyser un réseau métabolique (je dis ça car je travaille sur des réseaux métaboliques). Ou un réseau PPI. Ou encore un réseau de gènes. Comme vous voulez!

Voici donc une introduction à l'analyse des caractéristiques topologiques d'un réseau

On peut imaginer qu’il existe une corrélation entre la structure d’un réseau biologique et les fonctions biologiques retrouvées dans ce dernier. Le défi consiste alors à retrouver des structures topologiques intéressantes d’un point de vue biologique (et oui, car nous somme là pour analyser la biologie d'un organisme, non?) dans les réseaux métaboliques.Afin de faire ça, nous allons confronter des analyses informatiques de graphes (ce type d’analyses est notamment très utilisé pour analyser des réseaux sociaux, domaine qui nous dépasse un peu sur l'analyse de ce type de données) avec des données biologiques diverses. Ici, je vais parler de deux types d’analyses topologiques, les « classiques » et les centralités de graphes.

C'est parti!

Analyses topologiques classiques

Ici je vais juste vous faire un petit résumé des différents métriques de graphes, qui peuvent s'avérer très utiles lorsque l'on veut faire connaissance avec cette chose. Alors, n'ayez pas peur des petites formules que je vais mettre ici, elles sont en fait très très simples!

Alors, imaginons un graphe, tout simple. Avec des noeuds (vertices ou nodes en anglais) et des arêtes (edges). Et appellons-le G (oui, G comme "Graphe", très original, héhé).

Voici G(V,E)

Voici G(V,E) (Tous ensemble : "Bonjour G(V,E)!")

 

Soit G(V,E) un graphe tel que E contient l’ensemble des arêtes du graphe et V contient l’ensemble de ses nœuds. Appelons, très classiquement, v un nœud du graphe G tel que v  V.

La première métrique, la plus simple est le degré d(v) d’un nœud v. Il s'agit du nombre d’arêtes qui le lient à d’autres nœuds du même graphe. Dans le cas d’un graphe orienté, on pourra distinguer le degré sortant d+(v) (« out degree » en anglais) qui est le nombre d’arcs ayant le nœud comme source et le degré entrant d-(v) (« in degree ») qui correspond au nombre d’arcs qui ont le nœud comme cible.

Dans notre exemple, d(Node3)=4, d+(Node 3)=2 et d-(Node 3) =2.

Si on augmente la taille des noeuds proportionellement à leur degré total, ça donne ça:

G(V,E) - la taille est la couleur des noeuds sont proportionnels à leur degré

G(V,E) - la taille est la couleur des noeuds sont proportionnels à leur degré

Ensuite, il y a d'autres métriques :

  • La distance entre deux nœuds dans un graphe, qui est la longueur du (ou des) plus court(s) chemin(s) entre ces deux nœuds.
  • Le rayon du graphe, qui correspond à la plus petite distance à laquelle puisse se trouver un nœud de tous les autres nœuds du graphe. Cette mesure correspond à l’excentricité minimale des nœuds du graphe.
  • Le diamètre d’un graphe, qui représente la distance maximale parmi les distances entre toutes les paires de nœuds dans le graphe. Le diamètre correspond à l’excentricité maximale du graphe.
  • Le centre d’un graphe correspond à l’ensemble non-nul des nœuds d’excentricité minimale.

 

A cette liste je voudrais aussi ajouter le coefficient d'agglomération (ou de « clustering » pour faire un anglicisme) qui est la mesure de regroupement de nœuds dans un réseau. Concrètement, pour un nœud, ce coefficient mesure à quel point le voisinage de ce nœud est connecté. Explication par l'image :

G(V,E) - les noeuds les plus gros et les plus rouges ont le coefficient d'agglométation le plus élevé

G(V,E) - les noeuds les plus gros et les plus rouges ont le coefficient d'agglométation le plus élevé

 

Comme vous pouvez le constater, les deux métriques de graphes illustrées mettent en valeur des noeuds différents. Il est donc important de savoir ce que l'on souhaite voir dans le réseau avant de se lancer dans le calcul des différentes analyses! Et c'est pas fini! Car je vais maintenant vous parler de métriques un peu plus complexes, mais d'autant plus utiles pour analyser la topologie d'un graphe! Je vous présente...

Les centralités

Durant ma thèse j'ai pas mal étudié le sujet, je pourrais donc en parler pendant des heures et des heures... mais ce n'est pas le but ici! Alors si le topic vous interesse, je vous renvoie à la littérature, notamment l'excellent livre en accès libre "Network analysis" où plusieurs chapitres y sont consacrés. Je vais entre temps survoler le sujet, en présentant les centralités les plus courantes et les plus utiles.

Mais tout d'abord, qu'est ce qu'une centralité?

Les indices de centralité quantifient le sentiment intuitif que dans la plupart des réseaux, certains nœuds ou arêtes sont plus importants (ou plus centraux) que d’autres. Logique, hein? Beaucoup d’indices de centralité relatifs aux nœuds ont été introduits à partir des années 1940, comme la centralité de degré ("degree centrality" - il s'agit en fait tout simplement du degré de chaque noeud) ou la centralité feedback. Depuis, des dizaines de nouveaux indices de centralités ont été publiés, car toutes les centralités ne représentent pas la même chose, et il faut adapter cette mesure à chaque application.

L’importance des nœuds et des arêtes dans un graphe est évaluée selon des valeurs réelles qui y sont associées, et ces valeurs dépendent uniquement de la structure de ce graphe. Aussi, une centralité doit rester invariante dans le cas de graphes isomorphiques (qui ont la même topologie).

Les indices de centralité peuvent être classés dans plusieurs catégories :

Centralités de distances et de voisinage

Les centralités liées au voisinage des nœuds et aux distances qui les séparent évaluent l’accessibilité d’un nœud. Dans un réseau, ces mesures permettent de classer les nœuds en fonction du nombre de leurs voisins et/ou du coût nécessaire pour atteindre tous les autres nœuds. La centralité basée sur la notion de voisinage est l’indice le plus basique. On a déjà parlé précédemment du degré d'un nœud, et bien en fait c'est aussi une centralité!

La centralité de degré est une mesure locale car sa valeur pour un nœud donné est simplement déterminée par le nombre de ses voisins. Les centralités impliquant la notion de distances dans un graphe sont des mesures globales de centralité. Généralement ces mesures sont assimilées aux problèmes de localisation des établissements (« Facility Location Problems »), car elles servent à trouver le ou les nœuds les plus accessibles à partir de tous les autres nœuds du graphe. La mesure de l’excentricité, par exemple, peut être assimilée à la recherche du nœud qui minimise la distance maximale jusqu’à tous les autres emplacements dans le réseau. Pour illustrer cette mesure, il faut imaginer que l’on veut trouver l’endroit optimal pour un hôpital dans une ville, où le temps de trajet jusqu’à cet hôpital soit optimisé quel que soit le point de départ :

 G(V,E) - les noeuds les plus gros sont les plus centraux selon la centralité d'excentricité

G(V,E) - les noeuds les plus gros sont les plus excentriques - c'est donc sur les noeuds où ce coefficient est le plus faible qu'on voudra installer des établissements importants pour une ville

Centralités des plus courts chemins

Les indices de centralité basés sur les ensembles de plus courts chemins dans un réseau sont aussi des centralités globales. Soit deux nœuds u et v dans un graphe. Le plus court chemin entre u et v est une séquence de nœuds connectés par des arêtes tel que u et v soient aux extrémités de ce chemin, et que le nombre de nœuds intermédiaires soit minimal. Il s’agit en fait, de la distance entre u et v. Pour calculer les centralités basées sur cette notion, une étape de pré-calcul des plus courts chemins pour toutes les paires de nœuds du graphe est nécessaire.

Ici je ne présenterai que la centralité appellée "betweenness", mais sachez aussi que la centralité de stress (stress centrality) peut aussi s’avérer aussi très utile.

La centralité betweenness consiste à compter le nombre relatif de plus courts chemins qu'il existe entre chaque paire de nœuds. Ceci peut être interprété comme une mesure dans laquelle un nœud v contrôle la communication entre une paire de nœuds s et t.

Soit la fraction de tous les plus courts chemins entre s et t qui contiennent le sommet v :

est le nombre total de plus courts chemins entre s et t, tels queet. Cette fraction peut être considérée comme la probabilité que v est impliqué dans la communication entre s et t. La centralité betweennessdu nœud v est alors donnée par :

Pour dire les choses simplement, pour chaque paire de noeuds dans le graphe, on va compter tous les plus courts chemins. Ensuite, pour chaque noeud, on va compter combien de chemins passent par ce noeud parmi tous les plus courts chemins, et ce, pour chaque paire de noeuds.

Ainsi, cette centralité met en valeur les noeuds par lesquels passe le plus d'information. Dans notre exemple du graphe G(V,E), les noeuds 5 et 9 sont à l'intersection de ses trois parties. Si on regarde de plus près, on est obligé de passer par au moins un de ces deux noeuds pour aller d'une partie du graphe (du noeud 12 par exemple) vers une autre partie du graphe (vers le noeud 6 ou 2). La centralité betweenness sera donc très élevée pour ces deux noeuds.

Pour résumer, la centralité betweenness va être très élevée pour les nœuds par lesquels passent beaucoup de chemins du graphe, ces noeuds étant ceux qui font les ponts entre tous les autres noeuds :

G(V,E) - les noeuds les plus gros ont la centralité betweenness la plus élevée. Ce sont donc les noeuds par lesquels passe le plus grand flux d'information dans ce graphe!

G(V,E) - les noeuds les plus gros ont la centralité betweenness la plus élevée. Ce sont donc les noeuds par lesquels passe le plus grand flux d'information dans ce graphe!

 

Feedback

La centralité dite "feedback" (ou de "retour d’information") est basée sur le principe d’influence du voisinage : plus un nœud a de voisins, plus il est central, et plus il est central, plus ses voisins le sont aussi. On pourra aussi représenter ça d'une façon plus imagée, en prenant l'exemple sur l'importance des gens en politique, ou dans tout autre groupe social : plus une personne a des amis importants, plus elle est importante; et plus une personne est importante, plus ses amis deviennent importants.

Ce type de centralités, plus complexes que celles présentées précédemment, est très utilisé dans l’analyse de réseaux internet, de réseaux sociaux, et, moins, pour l’instant, dans les réseaux biologiques. Parmi les centralités "feedback" les plus connues, on retrouve l’indice de Katz , la centralité de vecteurs propres de Bonacich , l’indice de Hubbell, PageRank (utilisée jadis par Google) et SALSA (le coeur de Wolfram). Les notions de « hubs » et « d’autorités » sont très importantes dans ces centralités. Un hub est un nœud qui pointe vers beaucoup de bonnes autorités, et une autorité est un nœud pointé par beaucoup de bons hubs.

Ici je ne vous parlerai que de la centralité PageRank. Elle a, pendant très longtemps, été un des ingrédients principaux du célèbre moteur de recherche Google (qui l'a depuis replacé par des algorithmes encore plus complexes qu'efficaces portant plein de noms d'animaux - Panda, Penguin et Hummingbird). L’idée principale de cet algorithme est de marquer une page internet en tenant compte de ses propriétés topologiques (c’est à dire de sa position dans le réseau). Il s’agit bien d’une centralité feedback, car ici le score d’une page web dépend du nombre et des scores de ses pages voisines. Cette centralité peut être considérée comme « semi-globale », car elle permet de calculer des centralités par zones d’influence de nœuds très autoritaires, qui définissent des régions autour d’eux. L'image suivante représente bien le fonctionnement de cette centralité :

PageRank expliqué par des smileys 🙂 Image sous la licence libre de Wikipedia Commons

 

Sur cette image, la couleur et la taille des smileys dépend de importance selon Page Rank. Par exemple, beaucoup de noeuds pointent sur le noeud jaune, donc il est très très central. Et il a la capacité de partager cette centralité avec le seul noeud vers lequel il pointe (le gros rouge). En effet, même si ce smiley rouge n'est pointé que par un seul autre smiley, il est quand même grand, car son voisin est très grand et partage un peu de son importance avec lui.

 

Et notre petit G(V,E), vu par PageRank :

G(V,E) selon PageRank - "si mes voisins sont nombreux et importants, je suis important. Et plus je suis important, plus je rayonne mon importance sur mes voisins!"

G(V,E) selon PageRank - "si mes voisins sont nombreux et importants, je suis important. Et plus je suis important, plus je rayonne mon importance sur mes voisins!"

 

C'est la fin de cet article sur les métriques dans les réseaux... mais on reparle des réseaux très bientôt!


Quelques commentaires pour la fin (quand même):

  • Les indices de centralité peuvent aussi s'appliquer aux arêtes d'un graphe, exactement de la même façon que sur ses noeuds.
  • Presque toutes les images de cet article ont été réalisées avec Cytoscape 3.
  • J'ai prévu de faire un troisième article sur l'analyse de réseaux (métaboliques ou non), donc si vous avez des envies particulières, n'hésitez pas!

 


Un grand merci aux relecteurs pour leurs suggéstions et discussions : Mathurin, HedJour et tadaima !

  • À propos de
  • Actuellement postdoc en bioinformatique au CECAD (http://cellnet.cecad.uni-koeln.de) à Cologne (Allemagne). J'ai fait ma thèse en bioinformatique à l'Université Paris-Saclay, au Genoscope (http://www.genoscope.cns.fr/agc/blog/microscope/), après avoir fait le master BIBS à l'Université Paris-Sud sur le campus d'Orsay. Ma spécialité principale est l'analyse du métabolisme et de tout ce qui y touche (réseaux métaboliques, activités enzymatiques, structure des métabolites).

Catégorie: Didacticiel | Tags: ,

Un commentaire sur “Analyse de réseaux : du degré des noeuds aux centralités

  1. Hello et un grand merci pour ce super site !! Une petite question ; je dispose de données HiC pour un ensemble de gènes, et je souhaite étudier le clustering de ces gènes à partir de ces données. Pensez-vous qu\'il est pertinent de créer un réseau pondéré avec en valeur les données HiC et d\'évaluer/comparer le clustering dans différentes conditions en utilisant les centralités ?

    Merci d\'avance pour le coup de main, Raph

Laisser un commentaire