C comme centralité(s)
Ces billets visent à définir le plus clairement et le plus précisément possible des termes clés en analyse de réseau. Ils s’adressent à un public débutant et évitent autant que possible toute formalisation mathématique (pour cette dernière, voir les synthèses fmr sur Hal-Shs).
La centralité d’un sommet dans un graphe renvoie à la place de ce sommet par rapport aux autres sommets du graphe. La centralité d’un sommet peut être calculée de plusieurs manières afin de répondre à des logiques différentes de centralité : nombre de voisins, proximité par rapport aux autres sommets, point de passage important…
Mesures de centralité de “voisinage”
Un certain nombre de mesures estiment la centralité d’un sommet par rapport à ses voisins immédiats.
La mesure de centralité la plus simple est le degré du sommet (degree), c’est à dire le nombre de liens ayant le sommet comme extrémité (ou le nombre de voisins du sommet). Le degré peut être entrant, sortant ou pondéré (voir D comme degré pour plus de détails). La mesure du degré renseigne sur l’importance d’un sommet au sein du graphe. Un sommet ayant un degré élevé est considéré comme central puisqu’il est relié directement à nombre élevé de sommets du graphe, il a donc un potentiel d’interactions directes avec les autres sommets plus important qu’un sommet ayant un degré plus faible.
La centralité de vecteur propre (eigen-vector centrality) mesure de quelle manière un nœud est connecté aux autres sommets fortement connectés du graphe. Cet indice est basé sur le principe qu’un lien avec un sommet peu connecté “vaut” moins qu’un lien avec un sommet très connecté. C’est en sorte une extension de la centralité de degré, dans laquelle le poids des nœuds voisins est dépendant de leur centralité.
Dans le graphe de centralité de degré, le sommet rouge est le plus central, il possède 5 voisins directs. Dans le graphe de centralité de vecteur propre, le sommet rouge et, dans une moindre mesure, les sommets oranges sont centraux car ils sont fortement connectés à des sommets fortement connectés.
La centralité peut aussi être mesuré en identifiant des autorités (authorities) et des hubs. Les autorités sont des sommets qui possèdent un nombre important de liens entrants. Les hubs sont des sommets qui ont de nombreux liens sortants vers des autorités. Ces mesures sont notamment utilisées pour le classement des pages internet par les moteurs de recherche.
Mesures de centralité prenant en compte l’ensemble des sommets
L’excentricité d’un sommet (eccentricity), correspond au nombre de liens nécessaires pour relier le sommet le plus distant. Plus l’excentricité est importante, moins le nœud est central.
L’indice de Shimbel (Shimbel distance, farness) est la somme des longueurs des plus courts chemins permettant de relier tous les autres sommets. Il permet de déterminer les sommet les plus centraux en identifiant ceux qui sont le plus proches de l’ensemble des sommets du graphe. La centralité de proximité (closeness centrality) est l’inverse de l’indice de Shimbel, il correspond à la normalisation entre 0 et 1 de l’indice, où 1 correspond à une centralité importante. Ces deux indices sont aussi utilisés pour mesurer l’accessibilité dans un graphe (voir A comme accessibilité).
Dans le graphe d’excentricité, le sommet jaune est le plus central. Il ne faut parcourir que 2 liens au maximum pour atteindre n’importe quel sommet du graphe depuis celui-ci. Dans le graphe de proximité, les sommets en rouges sont les plus proches de l’ensemble des sommets du graphe. Les sommets jaunes sont particulièrement éloignés de l’ensemble des autres sommets
La centralité d’intermédiarité (betweenness centrality) correspond au nombre de plus courts chemins du graphe passant par chaque sommet. Cette mesure peut aussi être appliquée aux arcs du graphe. Un niveau élevé de centralité d’intermédiarité n’est pas forcement corrélé avec un degré important du sommet : un nœud avec un faible degré faisant le lien entre deux groupes de sommets aura une centralité d’intermédiarité élevée. Les nœuds avec une forte centralité d’intermédiarité sont des “points de passages importants” pour relier rapidement deux sommets du graphes.
Dans ce graphe, le sommet rouge est central. Grâce à sa position intermédiaire entre la partie gauche et la partie droite du graphe, un grand nombre de plus courts chemins passent par ce sommet.
Billets liés : A comme accessibilité, D comme degré.
OpenEdition vous propose de citer ce billet de la manière suivante :
Matthieu Drevelle (19 juin 2013). C comme centralité(s). groupe fmr (flux, matrices, réseaux). Consulté le 4 octobre 2024 à l’adresse https://doi.org/10.58079/p82n
Merci bien Matthieu, votre méthode de synthétiser et de simplifier la théorie des graphes m’a plu beaucoup et m’a aidé énormément dans ma thèse sur la centralité et l’accessibilité à l’échelle de l’agglomération de Constantine (Algérie).