2.7 Centralité de sommets

Les sommest d’un graphe ne jouent pas tous le même rôle ou n’ont pas tous la même importance dans le graphe. Différents indicateurs définis dans cette section permettend d’identifier des noeuds centraux d’un réseau, qui sont les plus influents ou des éléments clés d’un réseau.

Definition 2.10 L’indicateur de centralité le plus simple est la centralité de degré ou degree centrality, aussi appelée centralité de prestige, qui coïncide avec le degré du noeud \(i\): \[C_D(i) =d_i.\]

Intuitivement, un noeud très connecté aux autres est très important dans un graphe et on l’appelle un hub.

Au lieu d’analyser les connexions directes, on peut analyser comment le noeud est relié à tous les autres sommets.

Definition 2.11 La centralité de proximité ou closeness centrality du noeud \(i\) est défini par \[C_P(i) = \left(\sum_{j\in V}\ell_{ij}\right)^{-1}.\]

La centralité \(C_P(i)\) d’un noeud \(i\) est élevé, quand sa distance à tous les autres noeuds est faible. Le noeud le plus central est “proche” de toute l’information dans le graphe.

On peut également mesurer à quel point un noeud est important pour connecter deux autres noeuds dans le graphe.

Definition 2.12 La centralité d’intermédiarité ou $*betweenness centrality** du noeud \(i\) est défini par \[C_B(i)=\sum_{j,k:j\neq k\neq i} \frac{g_{jk}(i)}{g_{jk}},\] où \(g_{jk}\) est le nombre de plus courts chemins de \(j\) à \(k\), et \(g_{jk}(i)\) le nombre de plus courts chemins de \(j\) à \(k\) qui passent par \(i\).

La centralité \(C_B(i)\) d’un noeud est élevé, s’il est un point de passage sur un grand nombre de chemins les plus courts entre deux autres noeuds. Autrement dit, la plupart de la communication dans le graphe passe par lui.

Une autre façon de déterminer l’importance d’un sommet et de regarder à quel point la suppression du noeud modifie les caractéristiques du graphe.

Definition 2.13 Un point d’articulation ou cutpoint est un sommet qui, si on le supprime du graphe, augmente le nombre de composantes connexes.

Retirer un point d’articulation d’un graphe implique que certains noeuds ne peuvent plus communiquer entre eux.

Aux points d’articulation avec une centralité d’intermédiarité élevée, le graphe est très vulnérable en terme de communication.

De la même façon on peut analyser l’importance des arêtes d’un grpahe.

Definition 2.14 Un pont ou bridge est une arête qui, si on la retire du graphe, augment le nombre de composantes connexes.