Cours - Visualisation de graphes et réseaux sociaux

Supports complémentaires :

[Diapositives du cours : 2 par page] [Diapositives du cours : 1 par page]

Introduction

Le contenu de ce cours s’inspire en partie d’une présentation de Peter Eades, professeur émérite de l’université de Sydney, spécialiste reconnu du domaine.

Modéliser un système sous la forme d’un graphe permet de l’analyser avec des outils algorithmiques (centralités, communautés, distances, etc.), comme nous l’avons vu dans des chapitres précédents. Mais puisqu’un graphe se compose de nœuds et d’arêtes, il est naturel de vouloir le représenter visuellement. On espère ainsi accéder directement à sa structure : zones de forte densité, nœuds isolés, ponts entre communautés, hubs influents.

Pour un petit graphe, le positionnement peut être fait manuellement ou retouché après un premier placement automatique. Dès que le nombre de nœuds dépasse quelques dizaines, il est nécessaire d’employer des algorithmes capables de produire des visualisations lisibles sans intervention humaine.

Fig. 96 Placement aléatoire des sommets d’un graphe dans Gephi

Fig. 97 Visualisation travaillée (couleurs, placement) des communautés professionnelles d’un utilisateur (LinkedIn Maps)

Les paramètres visuels accessibles sont, pour les nœuds, la position, la taille, la couleur et la forme, et pour les arêtes la forme (droite, courbe, brisée), la position (chevauchements, angle), l’épaisseur et la couleur.

La discipline s’est concentrée historiquement sur le positionnement des nœuds et la forme des arêtes, les autres paramètres relevant davantage de la sémiologie graphique générale (voir le cours Visualisation d’information).

Planarité et critères esthétiques

Un graphe est dit planaire s’il est possible de lui trouver une représentation dans le plan sans croisement d’arêtes. Il est non planaire si toutes ses représentations comportent au moins un croisement.

Fig. 98 Le graphe de 4 sommets représenté est planaire, alors que le graphe de 5 sommets ne l’est pas.

La notion de planarité a bénéficié d’un grand intérêt au XX^e siècle. Elle a été introduite en visualisation à la fin des années 1970, avec l’intuition qu’une représentation planaire serait plus facile à interpréter. Des travaux expérimentaux ont effectivement montré une corrélation significative entre le nombre de croisements (et de brisures) d’arêtes et les erreurs de compréhension commises par des utilisateurs humains [P97].

Fig. 99 Les erreurs de compréhension augmentent avec le nombre de brisures (bends) et de croisements (crossings) [P97]

Cependant, la planarité a rapidement montré ses limites comme guide pratique :

• beaucoup de graphes réels ne sont pas planaires ;

• minimiser les croisements ne garantit pas une bonne lisibilité ; pour un graphe communautaire, il est souvent plus utile de regrouper spatialement les communautés que d’éliminer les croisements inter-communautaires ;

• les algorithmes reposant sur la planarité souffrent de résolution sommitale limitée (poor vertex resolution) : des nœuds peuvent se retrouver très proches, rendant ainsi la représentation illisible.

En pratique, aujourd’hui presque aucun algorithme commercial de spatialisation ne repose sur la planarité. Ce sont les méthodes orientées forces qui dominent.

L’algorithme de Tutte : fondation historique

La discipline naît véritablement en 1963 avec l’article de William Tutte, How to draw a graph [T63]. Tutte, mathématicien anglais qui avait contribué au déchiffrement des codes allemands à Bletchley Park, propose un algorithme barycentrique : chaque nœud non fixé est placé au barycentre de ses voisins.

Formellement, pour un graphe \(G = (V, E)\), on choisit un sous-ensemble \(A \subset V\) de nœuds dont on fixe la position \(p(a)\). Pour chaque nœud libre \(u \in V \setminus A\) :

\[p(u) = \frac{1}{k(u)} \sum_{v \in N_A(u)} p(v)\]

\(N_A(u)\) étant l’ensemble des voisins de \(u\) qui sont dans \(A\) (donc fixés) et \(k(u)\) le degré du nœud \(u\). Nous obtenons deux systèmes d’équations linéaires, sous forme matricielle \(\mathbf{M}\mathbf{x} = \mathbf{c}\) et \(\mathbf{M}\mathbf{y} = \mathbf{d}\). Pour le i-ème nœud libre \(u_i\), \(x_i = x(u_i)\), \(y_i = y(u_i)\), \(c_i = \sum_{v \in N_A(u_i)} x(v)\) et \(d_i = \sum_{v \in N_A(u_i)} y(v)\). \(\mathbf{M}\) est la matrice laplacienne du graphe restreinte aux seuls nœuds libres. Résoudre les deux systèmes linéaires revient à inverser cette matrice.

Interprétation énergétique. L’algorithme équivaut à minimiser l’énergie élastique d’un système de ressorts de longueur naturelle nulle, un ressort par arête :

\[E(p) = \sum_{(u,v) \in E} d^2(u,v) = \sum_{(u,v) \in E}\left[(x_u - x_v)^2 + (y_u - y_v)^2\right]\]

Le positionnement de chaque nœud libre dans le barycentre de ses voisins fixés correspond précisément à l’état d’équilibre de ce système.

L’algorithme de Tutte possède plusieurs qualités : emploie des lignes droites, produit une représentation planaire pour les graphes planaires, présente une complexité théorique de \(O(n^{1.5})\) pour les graphes planaires.

Cet algorithme présente également des défauts : risque de résolution sommitale limitée (certains nœuds peuvent se retrouver trop proches), le choix du sous-ensemble \(A\) et des positions de ses nœuds n’est pas évident.

Fig. 100 Exemples de visualisations obtenues avec l’algorithme de Tutte. La résolution sommitale limitée est visible dans les deux cas.

Méthodes orientées forces

Dès les années 1980, les besoins industriels et scientifiques (reverse engineering, réseaux de régulation génique, CRM) ont incité à développer des algorithmes plus adaptés aux grands graphes non planaires. L’approche dominante prolonge l’analogie mécanique de Tutte en ajoutant de nouvelles forces.

Modèle général

On associe à chaque paire de nœuds adjacents \((u,v)\) une force de ressort à longueur naturelle non nulle \(l_0 > 0\) :

\[\mathbf{F}_{ressort}(u,v) = k_{uv}\,(d(u,v) - l_0)\,\mathbf{i}_{uv}\]

où \(k_{uv}\) est la raideur du ressort, \(d(u,v)\) la distance euclidienne courante entre les positions des deux nœuds dans le plan de visualisation et \(\mathbf{i}_{uv}\) le vecteur unitaire de \(u\) vers \(v\).

Pour toute paire de nœuds non adjacents, on ajoute une force répulsive qui empêche les nœuds de se superposer :

\[\mathbf{F}_{rep}(u,v) = \frac{r_{uv}}{d^2(u,v)}\,\mathbf{i}_{uv}\]

La force totale sur un nœud \(u\) est :

\[\mathbf{F}(u) = \sum_{(u,v) \in E} \mathbf{F}_{ressort}(u,v) + \sum_{(u,w) \notin E} \mathbf{F}_{rep}(u,w)\]

L’équilibre \(\mathbf{F}(u) = 0\) pour tout \(u\) est le minimum d’énergie recherché. Le système est non linéaire et possède en général plusieurs minima locaux. On l’approche par intégration numérique ou descente de gradient, avec un pas (« température ») qui décroît au fil des itérations.

Contraintes et extensions

Les constantes du modèle permettent d’adapter la spatialisation au domaine :

• pour \(k_{uv}\) élevé et/ou \(l_0\) faible, les arêtes sont courtes, le graphe est compact ;

• des clous (pins) peuvent maintenir certains nœuds en position fixe ;

• des forces magnétiques peuvent aligner les nœuds ou les arêtes sur une grille ou sur des directions préférentielles ;

• des forces de groupe peuvent maintenir ensemble les nœuds d’une même communauté, indépendamment de la structure des arêtes ;

• dans les graphes valués, nous pouvons utiliser \(l_0 \propto 1/w_{uv}\) (les arêtes fortes sont courtes) ou \(k_{uv} \propto w_{uv}\) (le ressort est plus raide pour les arêtes fortes).

Fig. 101 Spatialisation orientée forces avec contraintes additionnelles

Critères esthétiques

Les algorithmes orientés forces cherchent à satisfaire plusieurs critères esthétiques simultanément. Ces critères, formalisés notamment par Purchase [P97] et Di Battista et al. [BETT94], constituent la boussole implicite de tout algorithme de spatialisation :

Minimiser les croisements d’arêtes. C’est le critère le plus directement lié à la lisibilité. Même si l’élimination totale est impossible pour les graphes non planaires, la réduction du nombre de croisements améliore significativement la compréhension.

Minimiser les brisures d’arêtes. Les arêtes droites (ou légèrement courbées) sont plus faciles à suivre visuellement que les arêtes très courbées ou en zigzag.

Uniformiser les longueurs d’arêtes. Des arêtes de longueur comparable facilitent la lecture de la structure globale. La longueur naturelle \(l_0\) du ressort est le levier principal pour ce critère.

Maximiser la résolution angulaire. L’angle minimum entre deux arêtes incidentes à un même nœud doit être le plus grand possible. Une faible résolution angulaire rend difficile de distinguer les arêtes autour d’un hub (nœud de degré élevé).

Maximiser la résolution sommitale. La distance minimale entre deux nœuds doit être suffisante pour qu’ils soient distinguables. C’est le critère qui manquait à l’algorithme de Tutte.

Révéler la symétrie. Les symétries du graphe devraient idéalement se traduire par des symétries visuelles dans la représentation. Ce critère est particulièrement important pour les graphes réguliers.

Révéler la structure communautaire. Les nœuds fortement connectés entre eux devraient être regroupés spatialement. Ce critère est souvent en tension avec la minimisation des croisements.

Ces critères sont partiellement contradictoires, les satisfaire tous simultanément est donc impossible en général. Leur importance relative dépend du type de graphe et de l’objectif de la visualisation.

Algorithmes notables

Plusieurs algorithmes se distinguent dans la littérature et les outils, chacun faisant des compromis différents entre ces critères.

Fruchterman-Reingold (1991)

Fruchterman et Reingold [FR91] proposent une instanciation particulièrement simple et efficace du modèle général. Leur choix est de trouver l’équilibre entre des forces d’attraction entre voisins \(f_a(d) = \frac{d^2}{l}\) et des forces de répulsion entre tous \(f_r(d) = \frac{l^2}{d}\), \(l = C\sqrt{A/n}\) étant la distance « idéale » entre nœuds, avec \(A\) la surface de la zone de dessin et \(C\) une constante empirique.

Le pas de déplacement est réduit à chaque itération selon une température T qui décroît linéairement : on part d’une disposition aléatoire et on « refroidit » progressivement le système. La complexité est \(O(n^2 + m)\) par itération, cet algorithme est donc lent sur les grands graphes.

Usage typique : graphes de taille petite à moyenne (jusqu’à ~1 000 nœuds), mise en évidence de la structure globale et des symétries. Disponible dans NetworkX (nx.spring_layout), Gephi, igraph.

Yifan Hu (2005)

L’algorithme de Yifan Hu [YH05] améliore Fruchterman-Reingold en deux points. D’abord, il utilise une structure de Barnes-Hut (octree) pour approximer les forces répulsives à longue distance en \(O(n \log n)\) au lieu de \(O(n^2)\). Ensuite, il emploie un schéma adaptatif de mise à jour du pas : le pas augmente si l’énergie diminue, et diminue sinon (adaptive cooling). Ces deux améliorations permettent de traiter des graphes d’une centaine de milliers de nœuds dans des délais raisonnables.

Usage typique : graphes moyens à grands (jusqu’à ~100 000 nœuds), bon compromis qualité/vitesse. Disponible dans Gephi (layout Yifan Hu).

ForceAtlas et ForceAtlas2 (2011–2014)

ForceAtlas2 [JAB+14] est conçu spécifiquement pour la fouille visuelle interactive dans Gephi. Ses principaux apports par rapport aux algorithmes précédents :

• Répulsion proportionnelle au degré : les hubs repoussent davantage leurs voisins, ce qui leur alloue plus d’espace et réduit l’encombrement autour d’eux.

• Force de gravité globale : une force attire tous les nœuds vers le centre, évitant que les composantes connexes dérivent trop loin.

• Prévention du chevauchement : une zone d’exclusion autour de chaque nœud empêche les superpositions.

• LinLog mode : remplace les forces linéaires par des forces logarithmiques, produisant des communautés plus compactes et mieux séparées, ce qui est particulièrement utile pour la visualisation des communautés.

• Mode approximatif (emploi de octree) pour passer à l’échelle.

Usage typique : graphes de réseaux sociaux, mise en évidence des communautés, exploration interactive. C’est l’algorithme par défaut dans Gephi.

OpenOrd (2010)

OpenOrd [MG11] est un algorithme parallèle conçu pour les très grands graphes (jusqu’à plusieurs millions de nœuds). Il repose sur une approche multi-niveaux : le graphe est d’abord simplifié par fusion de nœuds similaires (coarsening), spatialisé à basse résolution, puis affiné progressivement en réintroduisant les nœuds supprimés.

Contrairement aux trois algorithmes précédents, OpenOrd privilégie la séparation des communautés (il coupe délibérément les arêtes inter-groupes lors du coarsening). Les visualisations obtenues montrent des groupes bien distincts mais les connexions inter-groupes sont moins visibles.

Usage typique : très grands graphes (>100 000 nœuds), quand la structure communautaire prime sur la fidélité des connexions individuelles. Disponible dans Gephi via le plugin OpenOrd.

Fig. 102 Exemples de rendus avec, dans l’ordre, Fruchterman-Reingold, Yifan Hu, ForceAtlas2 et OpenOrd. Les trois premiers mettent en évidence des complémentarités structurelles, OpenOrd accentue les séparations (illustrations issues de la documentation de Gephi)

Synthèse comparative

Algorithme	Complexité/itér.	Taille cible	Point fort
Fruchterman-R.	\(O(n^2+m)\)	< 1 000 nœuds	Symétrie, lisibilité
Yifan Hu	\(O(n\log n)\)	< 100 000 nœuds	Vitesse, qualité
ForceAtlas2	\(O(n\log n)\)	< 500 000 nœuds	Communautés, interactif
OpenOrd	parallèle	> 100 000 nœuds	Très grand, clusters

Spatialisation et sémantique des nœuds

Dans certains cas, les nœuds disposent d”attributs portant une sémantique spatiale (coordonnées géographiques, positions dans un organigramme, niveaux dans une hiérarchie). Il est alors contre-productif d’utiliser un algorithme orienté forces qui ignorerait ces attributs.

Graphes géographiques. Si les nœuds sont des villes, des stations ou des routeurs dont on connaît la longitude/latitude, on peut fixer leur position par leurs coordonnées réelles et n’appliquer les forces que sur les arêtes (pour les courbures) ou n’en appliquer aucune. L’exercice sur le métro parisien dans le TP illustre ce cas : la disposition géographique donne directement une carte du réseau.

Graphes hiérarchiques. Les organigrammes, arbres de dépendances ou hiérarchies de fichiers ont une direction naturelle (racine en haut, feuilles en bas). Des algorithmes dédiés (Reingold-Tilford pour les arbres, Sugiyama pour les DAGs) placent les nœuds sur des couches horizontales et minimisent les croisements intra-couche. Ces algorithmes sont structurellement très différents des méthodes orientées forces.

Graphes bipartis. Lorsque les nœuds se répartissent naturellement en deux ensembles (utilisateurs/items, auteurs/articles), il est possible de forcer les deux ensembles sur deux lignes parallèles, ce qui clarifie la structure.

Passage à l’échelle et alternatives

Pour les graphes de plusieurs centaines de milliers ou millions de nœuds, même si ForceAtlas2 avec octree et OpenOrd sont en principe applicables, l’exécution est coûteuse et l’image résultante est illisible car il y a trop de nœuds sur un écran de résolution finie.

Plusieurs stratégies sont alors envisageables :

Filtrage préalable. On ne visualise qu’un sous-graphe pertinent : les nœuds les plus centraux, la composante connexe principale, les nœuds d’une communauté particulière, le voisinage d’un nœud d’intérêt. Le filtrage peut se faire dans Gephi (panneaux Filters) ou en amont dans Spark/NetworkX.

Agrégation. On substitue au graphe original un graphe de méta-nœuds : chaque communauté devient un nœud, les arêtes inter-communautaires deviennent des méta-arêtes valuées. La visualisation de ce graphe réduit donne une vue de la structure de haut niveau.

Visualisation en tuiles. Pour les graphes très larges, certains outils (Gephi avec le plugin Graph Streaming, ou des solutions web comme Sigma.js) permettent un zoom sémantique : à faible zoom, seuls les hubs et les méta-arêtes sont visibles ; en zoomant, les nœuds de moindre degré apparaissent progressivement.

Outils et bibliothèques

Gephi (https://gephi.org) est le logiciel de référence pour la visualisation et l’exploration interactive de graphes. Il inclut tous les algorithmes présentés ici, des outils de filtrage, de calcul de métriques et d’export. Son interface graphique permet d’ajuster en temps réel les paramètres de spatialisation. Nous l’utilisons en TP.

NetworkX (Python) est la bibliothèque Python la plus complète pour l’analyse de graphes en mémoire. Elle inclut Fruchterman-Reingold (nx.spring_layout), Kamada-Kawai, spectral layout, etc. L’affichage se fait via Matplotlib.

PyVis est une bibliothèque Python qui génère des visualisations interactives de graphes dans le navigateur (HTML/JavaScript via vis.js). Elle est compatible avec NetworkX.

Plotly permet de tracer des graphes interactifs à partir d’arêtes et de positions de nœuds précalculées, avec des infobulles riches, utile quand on veut intégrer la visualisation dans un notebook ou un tableau de bord.

Sigma.js est une bibliothèque JavaScript optimisée pour visualiser de grands graphes dans le navigateur (rendu WebGL). Elle emploie des fichiers GEXF ou JSON et permet le zoom sémantique.

GraphFrames (Spark) ne fait pas de visualisation directe, mais calcule efficacement les attributs nécessaires à une bonne visualisation (PageRank, communautés, intermédiarité) sur des graphes distribués. Les résultats sont ensuite exportés vers Gephi ou Plotly. C’est l’approche que nous mettons en œuvre dans le TP de cette séance.

Pour aller plus loin

• [BETT94] : Algorithms for drawing graphs: an annotated bibliography, disponible en ligne.

• [T13] : Handbook of graph drawing and visualization, R. Tamassia (dir.).

• [KW03] : Drawing graphs: methods and models, D. Wagner et M. Kaufmann (dir.).

Références

[P97] (1,2,3)

Purchase, H. C., Cohen, R. F., James, M. I. An experimental study of the basis for graph drawing algorithms. J. Exp. Algorithmics 2, Article 4 (1997). https://doi.org/10.1145/264216.264222

[T63]

Tutte, W. T. How to draw a graph. Proceedings of the London Mathematical Society 3.1 (1963): 743–767.

[FR91]

Fruchterman, T. M. J. and Reingold, E. M. Graph drawing by force-directed placement. Software: Practice and Experience 21.11 (1991): 1129–1164.

[YH05]

Hu, Y. Efficient and high quality force-directed graph drawing. The Mathematica Journal 10.1 (2005): 37–71.

[JAB+14]

Jacomy, M., Venturini, T., Heymann, S., Bastian, M. ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software. PLOS ONE 9.6 (2014).

[MG11]

Martin, S., Brown, W. M., Klavans, R., Boyack, K. W. OpenOrd: an open-source toolbox for large graph layout. SPIE 2011.

[BETT94] (1,2)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I. G. Algorithms for drawing graphs: an annotated bibliography. Computational Geometry 4.5 (1994): 235–282.

[T13]

Tamassia, R. (dir.). Handbook of graph drawing and visualization. Chapman and Hall/CRC, 2013.

[KW03]

Kaufmann, M., Wagner, D. (dir.). Drawing graphs: methods and models. Springer, 2003.

[CYN84]

Chiba, N., Yamanouchi, T., Nishizeki, T. Linear algorithms for convex drawings of planar graphs. Progress in graph theory (1984).

[FPP90]

De Fraysseix, H., Pach, J., Pollack, R. How to draw a planar graph on a grid. Combinatorica 10.1 (1990): 41–51.