I comme indice(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).

Un graphe n’est pas qu’une représentation visuelle d’interactions sous forme de nœuds et de liens, c’est aussi un objet d’analyse sur lequel il est possible de faire de nombreuses mesures. Ce billet a pour objectif de présenter les indices “classiques” de la théorie des graphes. La formalisation mathématique des indices est présentée dans la synthèse fmr “Les mesures globales d’un réseau“. On peut également se référer directement aux articles de Karl Kansky, un des pères de la théorie des graphes.

Les indices de la théorie des graphes peuvent être classés en deux grands groupes :

  • des indices topologiques, c’est à dire basés sur le nombre de nœuds, de liens et de cycles. Ces mesures sont applicables aux graphes planaires et non planaires (moyennant une adaptation).
  • des indices plus “géographiques”, qui prennent en compte la longueur des liens ou les flux sur le réseau. Ces mesures ont été élaborées initialement pour l’analyse des réseaux de transport (planaires et spatiaux).

Les indices topologiques : alpha, beta et gamma

L’indice α (alpha index) correspond au nombre de cycles présents dans le graphe par rapport au nombre maximum de cycles possibles, il est égal à 0 lorsque le graphe est un arbre et à 1 pour un graphe complet. On peut l’interpréter comme la propension d’un réseau à offrir des chemins alternatifs entre deux points.

L’indice β (beta index) correspond au nombre de liens sur le nombre de sommets. Il permet de mesurer la complexité d’un réseau. β est inférieur à 1 pour les arbres et de graphes non connexes, égal à 1 pour les graphes ne possédant qu’un seul cycle et supérieur à 1 pour les graphes plus complexes.

L’indice γ (gamma index) correspond au nombre de liens par rapport au nombre maximum de liens possibles.  Il peut être vu comme une version standardisée de l’indice β. Dans un graphe planaire, il permet de mesurer le degré de connectivité du réseau (voir C comme connectivité). Dans un réseau social, cette mesure renvoie à la densité du réseau (voir D comme densité).

L’illustration ci dessous présente la valeur des trois indices pour différents graphes de plus en plus complets

I Indice 1

Les indices alpha, beta et gamma ont comme avantage d’être faciles à calculer mais comme inconvénient d’être basés uniquement sur la topologie. Deux graphes avec des morphologies différentes peuvent ainsi avoir des résultats identiques. Cependant, les indices alpha, beta et gamma sont intéressants pour rendre compte de l’évolution d’un réseau dans le temps (l’évolution du réseau RER en Ile de France, par exemple).

Les indices spécifiques aux réseaux spatiaux: eta, pi, iota et theta

Les indices η (eta index) et π (pi index) expriment la longueur totale du réseau (en distance, temps…) par rapport aux liens qui le compose. L’indice η correspond ainsi à la longueur totale du réseau rapportée au nombre de liens. Il exprime la longueur moyenne d’un lien.

L’indice π correspond à la longueur totale du réseau rapportée à son diamètre. Une faible valeur de π est liée à un réseau peu développé (comme un corridor par exemple), a l’inverse une forte valeur de π revoit à un réseau plus développé (comme comme un réseau de villes connectées). Le graphique ci dessous pressente la valeur de π dans des réseaux de plus en plus développés (le chemin en rouge représente le -ou l’un des- diamètre du réseau).

I Indice 2

L’indice θ (theta index) correspond au trafic total du réseau rapporté au nombre de sommets. Il exprime le trafic moyen d’un sommet. Il est aussi possible d’appliquer la mesure aux liens qui composent le réseau, ce qui donne la charge moyenne du réseau.

L’indice ι (iota index) mesure un ratio entre la longueur du réseau et le nombre de sommets, pondérés par leur importance. Il est utilisé lorsque les données de trafic sont indisponibles ou pour comparer deux réseaux topologiquement identiques. Cet indice est basé sur le postulat qu’un sommet avec un fort degré peut capter des flux importants et que, par conséquent un réseau avec de nombreux nœuds importants sera plus efficace. Plus ι est faible, plus le réseau est efficace. Toutefois cet indice est peu repris dans la littérature.

Le graphique ci dessous présente l’indice ι dans trois graphes ayant la même topologie et ayant une longueur de 50. Les chiffres en blanc renseignent sur le poids des nœuds (qui est égal au double du degré pour les nœuds avec un degré supérieur à 2 ou au degré pour les autres sommets).

I Indice 3

De nombreux autres indicateurs existent pour l’analyse des graphes (centralité, densité, connexité…) et peuvent être consultés, par thème, à partir de la page de sommaire du glossaire.

 Billets liés : C comme connectivité, D comme densité

Retour au glossaire

Matthieu Drevelle

Doctorant en Géographie-Aménagement à l'Université Paris 1, UMR Géographie-cités, équipe CRIA - Transamo

More Posts


Vous aimerez aussi...

2 réponses

  1. Monsieur Monsieur dit :

    Merci !

  2. Laurent Beauguitte dit :

    Qualifier Kansky “d’un des pères de la théorie des graphes” me paraît abusif. Qu’il soit l’un des fondateurs de l’analyse géographique des réseaux, sans aucun doute. Et c’est déjà beaucoup.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search