E comme équivalence

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).

Dans un graphe, deux sommets sont dits équivalents lorsqu’ils possèdent des propriétés relationnelles communes, c’est-à-dire qu’ils émettent et reçoivent des liens vers le même type de sommets. Trois formes d’équivalence sont classiquement distinguées : l’équivalence structurale (structural equivalence), automorphique (automorphic equivalence) et régulière (regular equivalence). Les mesures d’équivalence sont utilisées dans les méthodes de blockmodeling pour partitionner les graphes en se basant uniquement sur les propriétés relationnelles des différents acteurs (voir B comme blockmodel).

Deux sommets sont dits structurellement équivalents lorsqu’ils ont les mêmes liens avec les mêmes sommets au sein d’un graphe. Il s’agit de la définition la plus stricte de l’équivalence, de fait l’équivalence structurale est relativement rare.

L’équivalence automorphique est plus souple que l’équivalence structurale. Il n’est en effet pas nécessaire, pour que deux sommets soient équivalents, qu’ils partagent les mêmes relations avec les mêmes sommets mais qu’ils aient la même structure de relations. En d’autres termes, deux sommets automorphiquement équivalents peuvent être interchangés sans modifier la structure du graphe, dans la mesure où ils possèdent les mêmes caractéristiques structurelles (degré, centralité, excentricité…). Cette définition plus souple rend possible l’équivalence automorphique de deux sommets appartenant à deux sous-graphes différents.

La définition de l’équivalence régulière est la plus souple. Elle regroupe les sommets qui ont le même type de liens avec le même type de sommets. On compte quatre positions de base des sommets : les isolés (isolate), les émetteurs (source, transmitter), les récepteurs (sink, receiver) et les intermédiaires (carrier).

En regroupant les sommets équivalents, on obtient un graphe réduit (reduced graph) qui résume les sommets à leur position. Ce graphe réduit correspond à la matrice bloquée du graphe (voir B comme blockmodel).

Dans le graphe ci-dessous, les couples de sommets {HI} et {EF} sont les seuls à être structuralement équivalents. On compte trois groupes de sommets concernés par l’équivalence régulière : {AB} ; {CD} ;  {EFGHI}. Si le graphe représentait un organigramme d’entreprise, l’équivalence régulière renverrait à un statut hiérarchique (directeurs, contremaitres, ouvriers) tandis que l’équivalence structurale renverrait à une même position dans l’entreprise (contremaitre sous les ordres de A, ouvriers travaillant sous les ordres de D…).

E equivalence 1

Dans le graphe ci-dessous, les différentes couleurs représentent des sommets automorphiquement équivalents : ils ont la même structure (degré, excentricité, centralité…) sans pour autant partager les mêmes liens avec les mêmes nœuds.

E equivalence 2

Pour aller plus loin : Synthèse du groupe FMR “Blockmodeling et équivalences”, disponible sur Halshs.

Billet lié : B comme blockmodel

Retour au glossaire



Citer ce billet
Matthieu Drevelle (2013, 2 juillet). E comme équivalence. groupe fmr (flux, matrices, réseaux). Consulté le 27 mai 2024, à l’adresse https://doi.org/10.58079/p82s

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...

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