M comme (flux) majeur

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

Lorsque les données d’un graphe valué sont trop complexes ou nombreuses pour être représentées, ou lorsque l’on cherche à faire ressortir les éléments les plus importants d’un graphe pour les analyser, il est nécessaire de procéder à une simplification du graphe (c’est-à-dire à la sélection de certains sommets et liens). Il existe plusieurs méthodes de simplification et ce billet a pour objectif de présenter celle des flux majeurs.

Le flux majeur (largest flow) est défini, pour chaque sommet, comme le lien le plus fort (en valeur) dirigé vers un autre sommet. Il s’agit d’une simplification importante qui ne garde qu’un lien par nœud et engendre une perte d’information non négligeable.

M Majeur Matrice_1 Dans la matrice ci-dessous, les flux majeurs (en gras) ne restituent que 40% de la valeur totale des flux.

 M Majeur Graphe_1

La faiblesse de la méthode est d’ignorer les liens importants inférieurs au flux majeur. Toutefois, une solution peut être partiellement apportée en assouplissant la définition du flux majeur pour garder plusieurs flux pour chaque nœud. Il est assez fréquent de prendre en compte les x premiers flux de chaque nœuds ou les flux représentant x% de l’ensemble des flux du nœud. Il est aussi possible d’appliquer un seuil au flux retenus afin de ne garder que les flux significatifs. L’enjeu est alors de définir le bon équilibre entre l’information conservée et la lisibilité du graphe.

M Majeur Graphe_2

Les flux majeurs sont aussi utilisés pour établir une hiérarchie entre les nœuds, on parle alors de flux dominants (voir D comme (flux) dominant).

Billets liés : D comme (flux) dominant, L comme lien

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

1 réponse

  1. 12/07/2013

    […] M comme (flux) majeur M comme matrice M comme modèle M comme modularité M comme multigraphe M comme multi-niveaux […]

Laisser un commentaire

Votre adresse de messagerie 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