B comme (graphe) biparti

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 est dit biparti ou 2-mode lorsqu’il représente les liens entre deux ensembles distincts de sommets. En anglais, on parle selon les cas de bipartite graph, de 2-mode network ou d’actor-event network. L’un des exemples les plus fameux de la littérature sociologique est le jeu  de données construit à partir des données récoltés par Davis dans son ouvrage Deep South : il représente 14 événements sociaux auxquels ont assisté 18  femmes.

Deux types d’analyse sont possibles sur un graphe biparti :

  • analyser le graphe non transformé ;
  • transformer le graphe de départ en graphes représentant les comportements communs au sein d’un même groupe de sommets – mathématiquement, l’opération consiste à multiplier la matrice d’adjacence de départ par sa transposée.

Cette dernière option a longtemps été la plus utilisée. Dans le cas du Davis dataset, on obtient deux graphes valués :

  • le graphe évènement – évènement où un lien entre deux sommets indique le nombre de femmes ayant assisté à ces deux évènements ;
  • le graphe femme – femme où un lien entre deux sommets indique le nombre d’évènements auxquels ont assisté ces deux femmes.

Les méthodes pour analyser les graphes bipartis sans transformation sont nombreuses aujourd’hui, qu’il s’agisse des mesures locales, globales ou des modèles statistiques. Par contre, les algorithmes de visualisation adaptés aux graphes bipartis restent rares, la représentation graphique la plus commune aligne horizontalement les deux groupes de sommets et tende de minimiser les croisements entre liens comme sur l’image ci-dessous.

Exemple de graphe biparti

Pour aller plus loin: voir la synthèse fmr L’analyse des graphes bipartis sur Hal-shs (http://halshs.archives-ouvertes.fr/FMR/halshs-00794976).

Retour au glossaire


Laisser un commentaire

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