Analyse de réseaux (3): s’il vous plaît… dessine-moi un réseau

” – Dessine-moi un mouton.” Alors j’ai dessiné. Il regarda attentivement, puis: “- Non! Celui-là est déjà très malade. Fais-en un autre.” Je dessinai : […] “- Tu vois bien… ce n’est pas un mouton, c’est un bélier. Il a des cornes…” Je refis donc encore mon dessin. Mais il fut refusé, comme les précédents […] Alors, faute de patience, comme j’avais hâte de commencer le démontage de mon moteur, je griffonnai ce dessin-ci. […] “- C’est tout à fait comme ça que je le voulais !”

                      Le Petit Prince, Antoine de Saint-Exupéry, Chapitre II

Après avoir exploré très succinctement quelques possibilités et limites de l’analyse des réseaux, nous commençons une série d’articles consacrée au travail sur sa propre base de données.

En supposant que la base de données soit déjà créée et bien ordonnée, la première étape du travail est la visualisation de réseaux. C’est une étape cruciale pour comprendre ses données, mais aussi un enjeu important pour la diffusion de sa recherche, et qui comporte plus de risques qu’il n’y paraît. Des dessins radicalement différents peuvent correspondre au même graphe: lequel choisir ?

Il est parfois tentant d’adopter une démarche un brin naïve face à la représentation de notre réseau. Se contenter de choisir l’affichage par défaut minimise la peine, à défaut d’être toujours adéquat. Choisir le plus beau rendu visuel est également un travers séduisant.

Mais le risque le plus grave est ce que j’appellerai le “syndrome du Petit Prince”: demander à ce que le dessin soit fait et refait, jusqu’à ce qu’il apparaisse sous les traits dont nous rêvions, ou jusqu’à qu’il laisse assez de place à notre imaginaire pour qu’il puisse être interprété comme nous le voulions.

Il est toujours tentant, quand une multiplicité de représentations graphiques est possible, de sélectionner celle qui semble le plus manifestement aller dans le sens de nos hypothèses de départ, celle qui ressemble le plus à l’idée que nous nous étions faites de nos données.

Pour éviter tous ces écueils, nous livrons ici quelques éléments importants pour la construction d’une représentation graphique compréhensible, attrayante, mais avant tout fidèle à nos données.

PARENTHESE TECHNIQUE: LE LOGICIEL GEPHI

  • Pourquoi Gephi ?

Nous choisissons de présenter ici un logiciel développé depuis 2008 à l’université technologique de Compiègne (UTC), et dont l’usage s’impose de plus en plus dans la recherche française et internationale ces dernières années: Gephi. Relativement facile à prendre en main, ce logiciel offre néanmoins de vastes possibilités, en particulier en termes de visualisation.

Il traite tous les types de réseaux, dirigés, non dirigés ou mixtes, et est compatible avec Windows, Linux et Mac OS. C’est de surcroît un logiciel libre, publié sous licence CDDL + GNU GPL 3.

Attirons l’attention sur la version de Gephi utilisée: les changements intervenus entre Gephi 0.8.2 et Gephi 0.9.1 (celle dont nous parlerons) n’ont pas été sans conséquences, notamment en ce qui concerne les plugins. Certains tutoriaux et cours produits pour les versions antérieures ne sont donc plus toujours valables – les suivre à la lettre pouvant provoquer quelques bugs mineurs.

  • Travailler ses données sous Gephi

Gephi supporte des données à différents formats. Le GEXF (Graph Exchange XML Format) est le format développé depuis 2007 par l’équipe Gephi,

Une base de données au format gexf – exemple des la base “Les Misérables”

Notons que ce format permet de décrire explicitement dès l’encodage le caractère dirigé ou non des liens, d’assigner des labels, et d’attribuer des pondérations.

Mais le logiciel accepte bien d’autres formats: GraphML, GraphViz DOT, Netdraw VNA, PajekNET, GDF, GML, Tulip TLP, UCINET DL.

Plus simplement encore il est possible d’importer des fichiers .csv créés sous Excel, OpenOffice Calc ou autre tableur standard. Un simple tableau à deux colonnes – première colonne nœud d’origine, deuxième colonne nœud d’arrivée du lien – peut donc être exploité pour modéliser son réseau dirigé ou non.

  • Manipulations esthétiques et d’étiquetages

Via le menu du bas, minimisé par défaut, on peut appliquer la plupart des variations simples.

Dans l’onglet “global”, on permet de changer le zoom ou la couleur du fond. Dans les onglets suivants, on peut modifier les options d’affichage des nœuds et des liens (leur couleur, leur forme, leur épaisseur etc.). Gephi permet par ailleurs d’étiqueter chacun des nœuds – une option activable et configurable sur le même menu.

CHOISIR LA MISE EN FORME DE SON RÉSEAU: LA SPATIALISATION

Une étape cruciale est le choix de la spatialisation, (en anglais du “layout”) c’est à dire de la manière dont l’ordinateur va organiser les points dans l’espace.

Plusieurs options sont proposées dans GEPHI, et doivent être choisies en fonction de ses données et de l’usage que l’on veut faire de la représentation graphique. Nous présentons ici quelques options usuelles, installées par défaut ou accessibles via des plugins spécifiques.

Pour illustrer la grande variété des représentations graphiques, nous utiliserons systématiquement la même base de données (une base de données exemple de Gephi, retranscrivant les liens unissant entre eux les personnages des Misérables de Victor Hugo – son contenu est parfaitement indifférent pour notre propos du moment, nous ne commenterons bien sûr pas les résultats…).

Rapport d’import renvoyé par GEPHI à chaque importation d’une nouvelle base de données – ici pour la base de données exemple “misérables.gexf”

Une base de données de taille particulièrement modeste, qui permet d’appliquer aisément tous les traitements que nous voulions présenter.

Tout répartir au hasard ?

  • Spatialisation aléatoire

Une possibilité pour ne pas “projeter” son interprétation sur ses données, de ne pas imposer de vues au lecteur du graphique, pourrait être de demander à ce que les points soient répartis “au hasard” sur le graphique.

C’est ce que propose l’option “spatialisation aléatoire”. On n’y définit que la taille de l’espace alloué à la représentation graphique (plus l’espace défini est petit, plus le dessin apparaîtra “compact”).

Notre réseau exemple spatialisé avec l’algorithme Spatialisation aléatoire

Si séduisante puisse-t-elle paraître d’un certain point de vue, cette option aboutit cependant à des graphiques souvent impossibles à interpréter, en particulier lorsque la taille du réseau augmente.

Représenter un réseau ayant une “réalité” géographique:

Le cas le plus simple intervient quand le réseau que l’on veut représenter correspond à une réalité physique en général, géographique en particulier. Dans ce cas, les distances entre points sont une fonction de la distance physique séparant chaque point du réseau. Comme toujours en cartographie, le choix de la projection peut bien sûr influer su le regard.

  • Geo Layout

Demande l’installation du plugin GeoLayout.

On entre une base de données dans laquelle les nœuds sont définis par leurs coordonnées géographiques (longitude/latitude). Les points sont alors positionnés en fonction de ces points – les projections les plus usuelles, comme Mercator, étant bien sûr envisageables.

La faible complexité de cette opération permet l’usage de très grandes bases de données (jusqu’à 1.000.000 de nœuds).

  • Map of countries

Demande l’installation du plugin Map of Countries.

Reprenant une grande partie du fonctionnement du plugin précédent, Map of countries permet sans surprise de représenter son réseau sur une carte incluant les tracés des frontières nationales ou régionales.

Mettre en avant les complémentarités: les algorithmes basés sur les forces

La plupart des algorithmes proposés par GEPHI sont des algorithmes de dessin basés sur les forces (Force-directed ou Force-based algorithms).

L’intuition sous-jacente à ces algorithmes est simple: les points reliés entre eux sont attirés les uns envers les autres, tandis que les points isolés sont repoussés. Un mode de pensée inspiré de la physique de l’électro-magnétisme.

  • ForceAtlas:

C’est un des algorithmes “maison” de Gephi, créé par Mathieu Jacomy en 2007.

Il est pensé pour mettre en valeur les réseaux “petit monde” (pour un rappel sur ces réseaux, voir notre premier billet de cette série), et de manière plus générale, les réseaux invariants d’échelle (“scale-free network”).

Notre réseau exemple spatialisé avec l’algorithme ForceAtlas, paramètres par défaut sauf “force de répulsion = 2000.0”

On prendra garde à la configuration précise de l’algorithme, notamment à celle des forces d’attraction et de répulsion. Une force de répulsion trop faible (ou une force d’attraction trop grande) risque d’aboutir à des superpositions malvenues, et de rendre le graphique illisible.

Notre réseau exemple spatialisé avec l’algorithme ForceAtlas, paramètres par défaut – en particulier avec  “force de répulsion = 200.0”

L’auteur recommande un usage pour des données ne dépassant pas 10.000 nœuds, du fait de la complexité quadratique de l’algorithme, et du temps de calcul qu’elle engendre.

  • Yifan hu proportionnal

Pour traiter de plus grandes bases de données, on pourra se tourner vers l’option “Yifan Hu proportionnal”, du nom d’un chercheur de Yahoo! research qui a produit des travaux remarquables sur la visualisation de grands réseaux, dont on utilise ici un algorithme de 2005. On se référera par ailleurs avec bonheur à sa récente revue de littérature co-écrite avec Lei Shi [2015] pour mieux comprendre l’état actuel des débats sur la visualisation de grands réseaux.

Cet algorithme permet l’exploitation de réseaux allant jusqu’à 100.000 nœuds

Notre réseau exemple spatialisé avec l’algorithme Yifan Hu proportionnel

On note également Force Atlas 2, un autre algorithme spécifique à Gephi, qui utilise certains mécanismes d’approximation similaire pour traiter de très grandes bases de données.

  • Fruchterman Reingold

Pour une base de données peu importante, on pourra choisir l’option “Fruchterman Reingold” d’après l’algorithme de ces deux auteurs [1991].

Notre réseau exemple spatialisé selon l’algorithme de Fruchterman & Reignold (1991) sous Gephi

Une visualisation devenue classique, mais un algorithme d’une complexité importante, qui la disqualifie pour l’étude de grands réseaux.

Une barre d’attente à laquelle il faut s’habituer lorsque l’on utilise cet algorithme avec des données un peu conséquentes…

Insister sur les divisions:

  • Open ord

Open Ord est un algorithme pensé pour décrire des réseaux qui ne seraient pas des petits mondes, et dont on voudrait mettre en avant les différents groupes (clusters) constituant. S’inspirant de Fruchterman-Reingold, qui devient ici un cas particulier des traitements possibles, l’algorithme cherche aussi à s’affranchir de la complexité quadratique inhérente aux modèles “force-based” que nous venons d’évoquer.

Une idée maîtresse pour cet algorithme est de permettre de couper certains liens les plus longs (dans la représentation graphique s’entend) – ce qui augmente l’allure “découpée” du dessin. Le paramétrage de l’option “edge-cut” permet de définir à partir de quelle longueur il est tolérable de couper. La valeur est comprise entre 0, ce qui donnerait dans ce cas le même résultat qu’avec Fruchterman-Reingold, et 1 (niveau qui maximisera le partitionnement visuel des données).

Notre exemple de réseau spatialisé avec Open Ord – edge cut: 0.20

Faire varier cette valeur donne évidemment des graphiques significativement différents.

Notre exemple de réseau spatialisé avec Open Ord – edge cut: 0.95

Ces visualisations ont pour intérêt une certaine clarté, et une bonne capacité à traiter des grandes bases de données. Elles sont toutefois à manier avec précaution.

L’accroissement des distances physiques entre les points donnent l’illusion que certains sont très éloignés, quand la distance qui les sépare dans le graphe est en réalité assez courte. Elles sont par conséquent à réserver à des cas où la séparation du réseau en différents clusters très distincts est véritablement nette et significative.

Privilégier l’ordonnancement des individus selon un critère d’intérêt

Plus qu’au tracé du réseau lui-même, on peut s’intéresser aux places relatives de chacun des nœuds selon un critère particulier. Peu m’importe qui échange avec qui, je m’intéresse ici à qui échange le plus avec les autres, ou qui est le plus central dans les échanges entre individus de mon réseau.

Ces options permettent des visualisations relativement spectaculaires – et c’est bien là leur valeur. En dehors de tout petits réseaux, le tracé du réseau devient illisible. L’information véhiculée par le graphique n’excède alors plus celle qu’aurait donné un tableau ordonnant les individus selon le critère d’intérêt.

  • Circular

Demande l’installation du plugin Circular Layout.

La logique globale de cet algorithme est plutôt simple: on trace un cercle, sur lequel on projette chacun des nœuds, en les ordonnant selon un critère défini par l’utilisateur: du plus haut au plus bas degré par exemple, ou du plus central au moins central…

Notre exemple de réseau spatialisé avec Circular, en choisissant d’ordonner les nœuds par degrés décroissant.

  • Radial Axis

Demande l’installation du plugin Circular Layout.

Là encore, un définit un critère d’intérêt (degré, centralité…), mais au lieu de représenter les nœuds sur le cercle, on les représente sur des axes qui “rayonnent” autour du cercle. Sur chaque axe, on regroupe les individus possédant au même niveau le critère d’intérêt (même degré, même centralité, etc.).

Notre exemple de réseau spatialisé avec Circular, en choisissant d’ordonner les nœuds par degrés décroissant.

Ces deux algorithmes sont d’une complexité limitée (0(n)) , et permettent donc le traitement de grandes bases de données.

VERS UNE ANALYSE MATHÉMATIQUE 

Les possibilités de visualisation d’un réseau sont extrêmement larges, et les graphiques obtenus fondamentalement différents. Il convient donc de se poser les bonnes questions quant à la conception d’un graphique, pour faciliter sa lecture et non la manipuler. Et il convient surtout de passer, une fois la visualisation faite, à une autre étape: celle de l’analyse à proprement parler, qu’aucun graphique ne peut remplacer. Ce sera bien sûr le thème du prochain billet de cette série.

Bibliographie

BASTIAN M., HEYMANN S., JACOMY M. (2009). “Gephi: an open source software for exploring and manipulating networks”International AAAI Conference on Weblogs and Social Media.

FRUCHTERMAN, Thomas M. J,  REINGOLD, Edward M. (1991), “Graph Drawing by Force-Directed Placement”, Software – Practice & Experience, Wiley, 21 (11): 1129–1164

MARTIN S., BROWN W.M., KLAVANS R., BOYACK K., (2011)  “OpenOrd: An Open-Source Toolbox for Large Graph Layout“, SPIE Conference on Visualization and Data Analysis, 2011

HU Yifan, LEI Shi, “Visualizing Large Graphs“, (2015)  Wiley Interdisciplinary Reviews: Computational Statistics, Volume 7, pages 115-136.

Florian CAFIERO

Ancien élève de l'Ecole Normale Supérieure Paris-Saclay et diplômé de l'Ecole nationale des chartes, Florian Cafiero est ingénieur de recherche en mathématiques appliquées aux sciences humaines et sociales au CNRS. Il enseigne les méthodes quantitatives appliquées aux sciences humaines à l'Ecole nationale des chartes.

More Posts - Website

Follow Me:
TwitterLinkedIn