thumb|right|300px|Exemples de A) Centralité d'intermédiarité, B) Centralité de proximité, C) Centralité de vecteur propre, D) Centralité de degré, E) Centralité harmonique et F) Centralité de Katz sur le même graphe.
En théorie des graphes et en théorie des réseaux, les indicateurs de centralité sont des mesures censées capturer la notion d'importance dans un graphe, en identifiant les sommets les plus significatifs. Les applications de ces indicateurs incluent l'identification de la ou des personnes les plus influentes dans un réseau social, les nœuds clés dans une infrastructure comme internet ou un réseau urbain, et encore des foyers d'infection, qu'ils soient de nature nosocomiales ou superinfecteurs, pour certaines maladies. Des exemples plus ponctuels incluent les relations de coopération dans les réseaux professionnels, comme les travaux scientifiques menés en commun ou, dans l'industrie cinématographiques, les acteurs ayant joué dans les mêmes film.
Les concepts et notions autour de la centralité ont été d'abord développés pour l'analyse des réseaux sociaux, et la plupart des termes utilisés pour mesurer la centralité reflètent cette origine sociologique.. De nombreuses mesures de centralité ont été développées depuis, et la liste la plus complète de ces mesures est disponible dans le catalogue en ligne CentralityZoo.
Définition et caractérisation des indices de centralité Les indices de centralité se veulent des réponses à la question « Qu'est-ce qui caractérise un sommet important ? ». La réponse est donnée en termes d'une fonction réelle sur les sommets d'un graphe, où les valeurs produites sont censées fournir un classement qui identifie les nœuds les plus importants... Le qualificatif « important » a un grand nombre d'interprétations variées, conduisant à de nombreuses définitions différentes de la centralité.
Deux schémas de catégorisation ont été proposés:
L'« importance » peut être conçue en relation avec un certain type de flux ou de transfert à travers le réseau. Cela conduit à classer les centralités selon le type de flux considéré comme important. L'« importance » peut aussi être vue comme le degré de participation à la cohésion du réseau. Cela conduit à classer les centralités en fonction de la façon dont elles mesurent cette cohésion..
Ces deux approches divisent les mesures de centralité en catégories distinctes. Une conséquence normale en est qu'une notion de centralité qui est appropriée pour une des catégories peut mener à des conclusions contraires à l'attente et en contradiction avec les autres, lorsqu'elle est employée à une catégorie différente.
Les indices de centralités qui mesurent la cohésion d'un réseau font, pour la plupart, partie d'une même catégorie. Ainsi, les centralités qui mesurent le nombre de chemins à partir d'un sommet donné ne diffèrent que par la nature des chemins qui sont pris en compte. Restreindre l'examen à ce groupe de mesures permet une caractérisation souple qui étale les centralités sur un spectre allant des chemins de longueur un (centralité de degré) à des chemins infinis (centralité de vecteur propre)..
Le fait que beaucoup de mesures de centralités partagent des définitions proches explique aussi les corrélations étroites que l'on peut relever entre ces indices.
Caractérisation par un flux de réseau
Un réseau peut être considéré comme une description de voies le long desquelles circulent des données. Cela conduit à une caractérisation basée sur le type du flux et sur le type de chemins appréhendés par la centralité. Un flux peut être basé sur des transferts, où chaque élément indivisible chemine d'un nœud à un autre, comme une livraison de colis qui va de l'entrepôt au domicile du client. Un autre cas est la duplication en série, lorsque c'est une réplique de l'élément qui chemine vers le nœud suivant, de sorte à la fois la source et la cible en possèdent un exemplaire. Un exemple est la propagation de l'information par commérages, où les informations se propagent d'une manière cachée et où la source et les nœuds cibles ont tous deux connaissance de l’information à la fin du processus de transmission. Un dernier cas est la diffusion en parallèle, où la donnée est dupliquée sur plusieurs liens en même temps, comme une émission de radio qui fournit la même information à de nombreux auditeurs simultanément.
À la nature du cheminement s'ajoute le choix du vecteur de cheminement, en d'autres termes la nature des chemins qui sont pris en compte dans le réseau. Le type de chemins peut être contraint à être seulement du type des géodésiques ou plus courts chemins, ou des chemins élémentaires (ne passant pas deux fois par le même sommet), ou des chemins simples (ne passant pas deux fois par la même arête), ou enfin des chemins sans contrainte, pouvant passer plusieurs fois par un même sommet ou une même arête.
Caractérisation par la structure de chemins Une autre classification peut être déduite de la manière dont la centralité est construite. Elle se divise encore en deux classes. Les centralités sont « radiales » ou « médianes ». Une centralité radiale dénombre des chemins qui débutent ou finissent en un sommet donné. Les centralités de degré et de vecteur propre sont des exemples de centralités radiales, comptant le nombre de chemins de longueur un respectivement de longueur infinie. Une centralité médiane compte le nombre de chemins qui passent par un sommet donné. L'exemple canonique est la centralité d'intermédiarité (« betweenness centrality ») de Freedman qui compte le nombre de plus courts chemins passant par un sommet donné.
De même, le décompte peut capturer ou bien le « volume » ou bien la « longueur » des chemins. Par « volume », on entend le nombre total de chemins du type donné. Les trois exemples du paragraphe précédent sont de cette catégorie. La « longueur » mesure la distance entre le sommet donné et autres sommets dans le graphe. La centralité de proximité (« closeness centralité ») de Freedman qui est la distance géodésique totale à partir d'un sommet donné à tous les autres sommets, est l'exemple le plus connu. Il convient d'observer que cette classification est indépendante du type de chemins dénombré (chemin généraux, élémentaires, simples, géodésiques).
Borgatti et Everett considèrent que cette typologie (centralités radiales ou médianes, volumiques ou de longueur) facilite la comparaison des mesures de centralité. Les centralités qui sont placés dans un même groupe dans ce classement 2 × 2 sont suffisamment semblables pour être des alternatives plausibles ; on peut raisonnablement comparer laquelle est la mieux adaptée pour une application donnée. Des mesures qui se trouvent dans des groupes différents sont par contre de catégories distinctes. Toute évaluation de leur aptitude comparée n'a de sens que dans le cadre de détermination préalable de la catégorie qui est la plus applicable, rendant la comparaison formelle.
Centralités radiales volumiques
La caractérisation par la structure des chemins montre que presque toutes les centralités qui sont beaucoup utilisées sont des mesures à la fois radiales et volumiques. Celles-ci codent l'hypothèse que la centralité d'un sommet est une fonction de la centralité des sommets qui lui sont associés. Les centralités se distinguent entre elles par la façon dont l'association est définie.
Bonacich a montré que si l'association est définie en termes de chemins, une famille de centralités peut être définie par la longueur du chemin considéré . La centralité de degré compte les chemins de longueur un, la centralité de vecteur propre compte les chemins de longueur infinie. D'autres définitions de l'association sont également raisonnable. Ainsi la centralité alpha permet aux sommets de prendre en compte une source d'influence externe. La centralité de sous-graphe d'Estrada propose de ne compter que les circuits (triangles, carrés, ...).
L'essence de ces mesures réside dans l'observation que les puissances de la matrice d'adjacence du graphe fournissent le nombre de chemins de longueur donnée par cette puissance. De même, l'exponentielle de la matrice est aussi étroitement liée au nombre de chemins d'une longueur donnée. Une transformation préalable de la matrice d'adjacence permet de définir les différents types de chemins dénombrés. Dans les deux approches, la centralité d'un sommet peut être exprimé par une somme infinie, soit
pour des puissances de matrices, soit
pour une exponentielle de matrices. Dans ces formules,
est la longueur du chemin, est la matrice d'adjacence transformée, et est un paramètre de réduction qui assure la convergence de la somme.
La famille de mesures de Bonacich ne transforme pas la matrice d'adjacence. La centralité alpha remplace la matrice d'adjacence par sa résolvante. La centralité de sous-graphe remplace la matrice par sa trace. Une conclusion surprenante est que, indépendamment de la transformation initiale de la matrice d'adjacence, toutes ces approches ont un comportement limite commun.
Lorsque tend vers zéro, les indices convergent vers le degré de centralité. Quand s'approche de sa valeur maximale, les indices convergent vers la centralité du vecteur propre.
Limitations importantes
Les indices de centralité ont deux limites importantes, l'une qui est évidente et l'autre plus subtile. La limitation évidente est qu'une centralité qui est optimale pour une application n'est souvent que sous-optimale pour une application différente. En effet, s'il en était autrement, on n'aurait pas besoin de tant de notions différentes de centralité.
La limitation plus subtile est l'erreur communément commise qui pense que la valeur numérique de la centralité des sommets indique l'importance relative des sommets. Les indices de centralités sont explicitement conçues pour produire uniquement un classement qui permet d'obtenir des indications sur les sommets les plus importants. Ils le font bien, sous réserve de cette limitation. L'erreur est double.
D'abord, un classement ordonne seulement les sommets par ordre d'importance, il ne quantifie pas la différence d'importance entre les différents valeurs du classement. Ceci peut toutefois être corrigé par l'application de la centralisation de Freeman à la mesure de centralité en question, qui fournit un aperçu de l'importance de nœuds en fonction des différences de leurs scores de centralisation.
Deuxièmement, les caractéristiques qui identifient correctement les sommets les plus importants dans un réseau ou dans une application donnée ne s'étendent pas nécessairement aux autres sommets. Pour la majorité des autres nœuds du réseau les classements peuvent être dénuée de sens. Cela explique par exemple pourquoi, dans une recherche d'images de Google, seuls les premiers résultats apparaissent dans un ordre raisonnable.
Alors que l'impossibilité de généraliser les indices de centralité au reste du réseau peut à première vue sembler contre-intuitive, elle découle directement de la définition donnée plus haut.
Les réseaux complexes ont une topologie hétérogène. Comme la mesure optimale dépend de la structure du réseau des sommets les plus importantes, une mesure qui est optimale pour ces sommets est sous-optimale pour le reste du réseau.
Centralité de degré