Cours - Visualisation de graphes et réseaux sociaux

Support complémentaires :

Vous pouvez télécharger les diapositives du cours qui sont projetées durant la séance.

Note aux lecteurs⋅ices :

La rédaction de ce cours est récente, vous pouvez me communiquer vos retours pour l’améliorer à fournier@cnam.fr. Le travail présenté a été inspiré par une présentation de Peter Eades, Professeur émérite de l’université de Sydney, spécialiste reconnu du sujet.

L’objectif de la modélisation d’un problème sous la forme d’un graphe, c’est de se donner des outils conceptuels pour l’analyser (efficacement), comme nous l’avons vu dans les deux chapitres précédents (chapitre 1 et chapitre 2). Au-delà de l’obtention de résultats avec des indicateurs classiques (densité, diamètre, etc.), puisqu’un graphe se compose de nœuds et de liens, il est assez naturel de visualiser ceux-ci. On peut espérer accéder à une compréhension directe (ou presque) de la structure du graphe et du rôle que jouent les nœuds dans le système modélisé. Par exemple, s’il s’agit d’individus, on pourra identifier quelques motifs, individuels et collectifs : quelles sont les zones avec une forte/faible densité de connexions, les individus isolés, ceux qui sont à mi-chemin entre des zones denses, etc.

La visualisation d’un graphe avec peu de nœuds et de liens s’avère souvent simple, puisque l’on peut choisir le positionnement des éléments à visualiser (ou retoucher un positionnement affecté par la machine). Mais l’augmentation des tailles de graphes étudiés aujourd’hui conduit à rechercher des méthodes efficaces de visualisation, c’est-à-dire permettant d’offrir le maximum de compréhension et de lisibilité pour le minimum d’effort de la part de l’analyste : cela passe par la mise au point d’algorithmes d’automatisation. On cherche à passer, pour un grand nombre de nœuds, d’un placement aléatoire initial et monochrome à une visualisation colorée et aérée (illustré avec les figures graphVizprinciple et Fig. 115)

_images/initial-network.png
_images/linkedin-network-map.jpg
_images/principeVisuGraphes.png

Fig. 115 Le principe de la visualisation de graphes.

Un graphe reposant formellement sur un ensemble \(V\) de nœuds et un ensemble \(E\) d’arêtes, les paramètres de la modélisation seront les attributs possibles pour les éléments de chacune de ces catégories. Ainsi, pour les nœuds, on considèrera :

  • leur position

  • leur taille

  • leur couleur

  • voire, plus rarement, leur forme (circulaire ou non)

Pour les arêtes, il sera possible d’agir sur :

  • leur forme (courbes, lignes droites ou brisées)

  • leur position (chevauchements, écart angulaire)

  • l’épaisseur du trait

  • leur couleur

Mais l’histoire de la discipline a axé la réflexion avant tout sur le positionnement des nœuds et des arêtes, et la forme des ces dernières. Les questions de couleur et de taille sont moins centrales, et vous pourrez avoir des éléments permettant d’ajuster ces questions dans les prochains chapitres de visualisation de données, comme le chapitre Enjeux perceptifs.

La suite de ce cours présente les éléments du « dessin de graphes » (pour reprendre les termes des pionniers), avec une progression proche de la progression historique de la discipline, conclue par un panorama (évidemment non exhaustif) des outils et bibliothèques disponibles pour produire des visualisations. Le cours est complété par une séance de travaux pratiques.

Planarité d’un graphe et qualité de la visualisation

Un graphe est dit planaire s’il existe une représentation dans le plan telle qu’aucune arête n’en croise une autre. Un graphe est dit non planaire si toutes ses représentations dans le plan comportent au moins un croisement d’arêtes.

_images/graphesPlanarite.png

Fig. 116 Le graphe de 4 sommets est planaire : même si sa représentation initiale comporte un croisement d’arêtes, il existe une représentation de ce graphe sans croisement. Le graphe de 5 sommets n’est pas planaire.

Cette notion de planarité, très étudiée en théorie des graphes durant le XXe siècle pour son intérêt mathématique, est intervenue dans la partie « visualisation des graphes » à la fin des années 1970, quand des chercheurs ont eu l’intuition qu’elle pourrait avoir un lien avec la qualité d’une représentation, ou du moins la faculté des humains à l’interpréter. L’idée est la suivante : une représentation planaire permet de faire des images jolies et immédiatement compréhensibles.

Des travaux ultérieurs ont effectivement montré qu’il y avait des corrélations significatives entre les erreurs de compréhension et la quantité de croisements d’arêtes [P97]. De même, les brisures de lignes sont également associées à des erreurs.

_images/BendsCrossingsErrors.png

Fig. 117 Les deux ensembles de courbes, extraits de [P97], montrent que le nombre d’erreurs de compréhension de l’image du graphe par des humains croît avec l’augmentation des brisures d’arêtes (bends) et des chevauchements (crossings).

En somme, il est naturel de rechercher des représentations d’un graphe où l’on minimise :

  • les croisements d’arêtes

  • les lignes brisées

Le théorème de Fáry, du nom de István Fáry (mais prouvé par d’autres dans les mêmes périodes), énonce qu’un graphe simple planaire peut être dessiné sans chevauchements d’arêtes, avec des lignes droites. Cependant, beaucoup de graphes que l’on rencontrera ne seront pas planaires. Et qu’un théorème assurant l’existence d’une représentation sans croisements ne donne pas immédiatement accès à celle-ci : ce théorème a peu d’utilité pratique.

L’algorithme de W. Tutte

La discipline de la représentation de graphes naît véritablement en 1963 avec la publication d’un article fondateur, « How to draw a graph » [T63]. Son auteur, William Tutte, est un mathématicien anglais brillant, qui était aux côtés d’Alan Turing pour déchiffrer les codes allemands à Bletchley Park. Il introduit un algorithme barycentrique pour construire une représentation d’un graphe, capable de produire des dessins avec des lignes droites (qui se chevauchent éventuellement).

L’algorithme prend en entrée un graphe \(G = (V,E)\). La sortie de l’algorithme est une représentation avec les lignes droites dudit graphe, que l’on appellera \(p\) (et on note \(p(u)\) la position de \(u\) dans \(p\)).

Voici les étapes de l’algorithme :

  1. on choisit un sous ensemble de sommets, A, de V

  2. on choisit une position p(A) pour chaque sommet \(a \in A\).

  3. pour chaque sommet \(u \in V-A\), on a :

    \[p(u) = \frac{1}{deg(u)} \sum_{v \in N(u)} p(v) \quad \mbox{avec }N(u)\mbox{ l'ensemble des voisins de } u.\]

Ce qui donne un système de \(2n\) équations :

\[\begin{split}\left\{\begin{array}{ll} x(u) & = & \frac{1}{deg(u)} \sum\limits_{v \in N(u)} x(v) \\ y(u) & = & \frac{1}{deg(u)} \sum\limits_{v \in N(u)} y(v) \\ \end{array} \right.\end{split}\]

Prenons un exemple avec un graphe à 8 sommets, avec les liens comme illustrés sur la figure suivante :

_images/graphTutteAlgo.png

Fig. 118 Les sommets 4 à 8 sont placés au début, on cherche en fonction de ceux-ci les positions des sommets 1 à 3.

  1. Initialement, on choisit \(A = {4,5,6,7,8}\).

  2. On choisit \(x_i\) et \(y_i\) pour \(i \in {4,5,6,7,8}\).

  3. On doit ensuite trouver \(x_1, y_1, x_2, y_2, x_3, y_3\) tels que :

    \[ \begin{align}\begin{aligned}\begin{split}\left\{\begin{array}{ll} x_1 & = & \frac{1}{4} (x_2 + x_3 + x'_4 + x'_8) \\ x_2 & = & \frac{1}{4} (x_1 + x_3 + x'_5 + x'_6) \\ x_3 & = & \frac{1}{3} (x_1 + x_2 + x'_7) \\ \end{array} \right.\end{split}\\\begin{split}\left\{\begin{array}{ll} y_1 & = & \frac{1}{4} (y_2 + y_3 + y'_4 + y'_8) \\ y_2 & = & \frac{1}{4} (y_1 + y_3 + y'_5 + y'_6) \\ y_3 & = & \frac{1}{3} (y_1 + y_2 + y'_7) \\ \end{array} \right.\end{split}\end{aligned}\end{align} \]

Avec \(x'_i\) et \(y'_i\) les valeurs choisies à l’étape précédente. Ce qui donne :

\[ \begin{align}\begin{aligned}\begin{split}\left\{\begin{array}{lll} 4 x_1 - x_2 - x_3 & = & x'_4 + x'_8 & = & c_1\\ -x_1 + 4 x_2 - x_3 & = & x'_5 + x'_6 & = & c_2\\ -x_1 - x_2 + 3 x_3 & = & x'_5 & = & c_3\\ \end{array} \right.\end{split}\\\begin{split}\left\{\begin{array}{lll} 4 y_1 - y_2 - y_3 & = & y'_4 + y'_8 & = & d_1 \\ -y_1 + 4 y_2 - y_3 & = & y'_5 + y'_6 & = & d_2 \\ -y_1 - y_2 + 3 y_3 & = & y'_5 & = & d_3 \\ \end{array} \right.\end{split}\end{aligned}\end{align} \]

Avec \(c_1, c_2, c_3, d_1, d_2, d_3\) qui sont des constantes.

Vision matricielle de cet algorithme

Il s’agit de trouver les vecteurs \(\begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \end{bmatrix}\) et \(\begin{bmatrix} y_{1} \\ y_{2} \\ y_{3} \end{bmatrix}\) tels que :

\[\begin{split}\left\{\begin{array}{ll} M x = c \\ M y = d\\ \end{array} \right. \quad \mbox{avec } M = \begin{bmatrix} 4 & -1 & -1 \\ -1 & 4 & -1 \\ -1 & -1 & 3 \\ \end{bmatrix}\end{split}\]

Ainsi, le cœur de l’algorithme de Tutte consiste à inverser une matrice. Et il ne s’agit pas de n’importe quelle matrice, mais de la matrice laplacienne du graphe (plus précisément : de la sous-matrice correspondant à l’ensemble V-A des sommets restant à placer), qui est définie formellement comme suit :

\[\begin{split} M_{uv} = \left\{\begin{array}{ll} deg(u) & \mbox{si} u = v\\ -1 & \mbox{si} (u,v) \in E\\ 0 & \mbox{sinon.} \end{array} \right.\end{split}\]

De même, \(c\) et \(d\) valent :

\[ \begin{align}\begin{aligned}c_u = \sum_{w \in A} x_w\\d_u = \sum_{w \in A} y_w\end{aligned}\end{align} \]

Ainsi, les coordonnées x et y de chaque sommet de A sont obtenues par :

\[ \begin{align}\begin{aligned}\begin{split}\left\{\begin{array}{ll} x & = & M^{-1} c \\ y & = & M^{-1} d \\ \end{array} \right.\end{split}\\ \mbox{Enfin, } p(u) = (x_u,y_u)\end{aligned}\end{align} \]

La Fig. 119 présente deux exemples de dessins de graphes obtenus avec cet algorithme, dans le cas d’un graphe planaire, et dans le cas d’un graphe non-planaire.

_images/graphTutteExemples.png

Fig. 119 Exemples de dessins obtenus avec l’algorithme de W. Tutte. Au-delà de la bonne qualité générale de l’ensemble, que dans certains cas, des liens sont trop proches et difficiles à distinguer (visible en bas à droite dans le cas non planaire).

La vision énergétique

L’algorithme de Tutte peut également être vu comme un problème de minimisation de l’énergie d’un système. On fait l’analogie avec la mécanique classique. L’énergie d’une représentation \(p\) est la somme des énergies des arêtes, et l’énergie d’une arête est définie comme :

\[E((u,v)) = d^2(u,v) = (x_u - x_v)^2 + (y_u - y_v)^2\]

\(d(u,v)\) désigne la distance entre \(u\) et \(v\) dans le plan. On a donc :

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

Cette analogie avec la mécanique peut amener à considérer chaque arête comme un ressort, d’une longueur naturelle \(l_0 = 0\) (voyez la page Ressort de Wikipedia pour rafraîchir vos souvenirs de physique de lycée). La première étape de l’algorithme est la même. La seconde étape, où l’on choisit des positions pour les sommets, consiste maintenant à les fixer (clouer). Au début de la 3e étape, on se trouve en présence d’un ensemble de ressorts dont certaines extrémités sont fixées (choix des positions initiales pour certains sommets). On libère le système, qui devrait osciller avant d’atteindre une position d’équilibre : l’énergie est minimisée.

La minimisation de l’énergie correspond à un état unique, tel que :

\[\begin{split}\left\{\begin{array}{ll} \frac{\partial E(p)}{\partial x_u} & = & 0 \\ \frac{\partial E(p)}{\partial y_u} & = & 0 \end{array} \right.~\mbox{ , pour chaque } u \in V-A.\end{split}\]

Ce qui se traduit (en x, même chose en y) par :

\[\begin{split}\begin{array}{lll} & \frac{\partial E(p)}{\partial x_u} & = & 0 \\ \mbox{soit :} & \frac{\partial}{\partial x_u} \left(\sum\limits_{(u,v) \in E}(x_u - x_v)^2 + (y_u - y_v)^2\right) & = & 0 \\ \mbox{puis :} & \sum\limits_{v \in V t.q. (u,v) \in E} 2 (x_u - x_v) & = & 0 \\ \mbox{d'où : } & x_u = \frac{1}{deg(u)} \sum_{v \in V t.q. (u,v) \in E} x_v \end{array}\end{split}\]

Et l’on a retrouvé le système d’équations vu initialement.

Qualités et défauts de l’algorithme de Tutte

La complexité de l’algorithme est théoriquement en \(\mathcal{O}(n^{1.5})\), pour les graphes planaires. En pratique, avec les méthodes de résolution numérique d’équation, il est assez rapide. L’algorithme est également simple à comprendre et plutôt facile à implémenter, reposant sur des bibliothèques numériques efficaces pour les parties difficiles. En terme de visualisation, on obtient des représentations planaires pour les graphes planaires et des lignes droites.

Mais l’algorithme souffre d’un défaut, dit de « résolution sommitale limitée » (poor vertex resolution). C’est-à-dire que les sommets peuvent se placer très près les uns des autres.

Après Tutte

Au cours des années 1980, les motivations pour disposer d’algorithmes de visualisation de graphes ont changé, passant d’une « curiosité mathématique » à un besoin (éventuellement commercial) de fouille visuelle de données.

L’industrie du logiciel (reverse engineering), la biologie (réseaux de régulation de gènes), ainsi que d’autres domaines (CRM, gestion de risques) ont commencé à représenter de grands graphes, en espérant améliorer leur compréhension du système modélisé grâce à la visualisation.

Ces besoins ont amené la création de nouveaux algorithmes, pour améliorer les visualisations, car le défaut de l’algorithme de Tutte le rendait insuffisant.

L’impasse de la planarité

Après Tutte, deux grandes orientations ont été suivies : - des développements autour des graphes planaires - de nouvelles méthodes reposant sur des analogies physiques (force-directed methods)

Les méthodes autour de la planarité ont abouti d’abord à des algorithmes linéaires, avec des approches efficaces… mais qui souffraient toujours du problème de résolution sommitale limitée ([R86], [CYN84]).

En 1990, de Fraysseix, Pach et Pollack [FPP90] ont énoncé le théorème suivant :

Tout graphe planaire peut être représenté avec des lignes droites avec les sommets sur une grille de \(2n \mbox{ x } 4n\).

Cela résout la question de la résolution, puisque la distance minimale entre deux sommets est au minimum de \(\frac{\mbox{taille écran}}{4n}\). Et un algorithme linéaire a rapidement été trouvé [CP90], ce qui a amené de nombreuses améliorations dans la décennie qui suivit. Cependant, ces algorithmes souffrent d’un problème de résolution angulaire, et aboutissent à des positions peu conventionnelles.

Ainsi, bien que la planarité soit un critère esthétique fondamental, aujourd’hui presque aucun algorithme reposant sur la planarité n’est adopté commercialement, au profit des méthodes « orientées forces », que nous allons voir maintenant.

Méthodes et algorithmes modernes de spatialisation

De manière indépendante au développement des algorithmes liés à la planarité, des améliorations de l’algorithme de Tutte ont été proposées, en poursuivant l’analogie avec la mécanique. Pour éviter que les sommets puissent être trop proches les uns des autres, il a été proposé de modifier le système en introduisant deux nouvelles forces :

  • une force reposant sur une longueur naturelle non nulle pour les ressorts

  • une force répulsive, proportionnelle à l’inverse du carré de la distance entre les sommets

Formellement, la force \(\mathbf{F}_{ressort}\) s’applique pour des sommets voisins \(u\) et \(v\), elle vaut :

\[\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)\) est la distance euclidienne entre les sommets

  • \(l_0\) est la longueur naturelle du ressort

  • \(\mathbf{i_{uv}}\) est un vecteur unitaire de u vers v

Pour des sommets non-adjacent, la force répulsive \(\mathbf{F}_{rep} (u,v)\) s’exerce. Elle vaut :

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

Où :

  • \(r_{uv}\) est une constante de répulsion

La somme des forces qui s’exercent sur un sommet devient ainsi :

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

Un minimum local d’énergie correspond, comme précédemment, au cas où \(F(u) = 0\), pour chaque sommet \(u\). On obtient un système d’équation non-linéaire. En général, la solution de ce système n’est pas unique, il y a des minima locaux qui peuvent ne pas être des minima globaux. Il existe diverses méthodes pour résoudre de tels systèmes.

Contraintes du domaine

Le modèle avec des forces contient des constantes qui peuvent permettre de contraindre la représentation, pour tenir compte des objectifs liés au domaine du graphe. Par exemple, si les liens sont importants, on peut choisir un \(k_{uv}\) grand et \(l_0\) faible.

On peut également utiliser d’autres analogies mécaniques pour introduire de nouvelles équations dans le système et agir sur la visualisation :

  • des « clous » peuvent maintenir la position de certains nœuds

  • des forces magnétiques peuvent agir sur des sommets (par exemple pour les aligner sur une grille)

  • des forces attractives peuvent agir sur des groupes de sommets pour les maintenir proches les uns des autres

Le schéma Fig. 115 devient :

_images/principeVisuGraphesModif.png

Fig. 120 Schéma de principe de la visualisation de graphes adaptée avec les contraintes spécifiques.

Quelques algorithmes notables

Il existe aujourd’hui quelques algorithmes notables reposant sur l’algorithme général à base de forces :

  • Fruchterman-Reingold

  • Yifan Hu

  • ForceAtlas et ForceAtlas2

  • OpenOrd

Les trois premiers mettent en évidence des complémentarités, alors que le dernier met l’accent sur des divisions.

La figure Fig. 121 présente des exemples de graphes avec ces quatre algorithmes de spatialisation.

_images/graphLayoutExemples.png

Fig. 121 Exemples de dessins obtenus avec Fruchterman-Reingold, Yifan Hu, ForceAtlas2 et OpenOrd (schémas provenant de la documentation Gephi)

Ces algorithmes sont implémentées dans divers outils logiciels, comme Gephi que nous verrons en détail en séance de travaux pratiques.

Aller plus loin

Les lecteurs et lectrices souhaitant aller plus loin pourront consulter les références suivantes :

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

  • [T13] : Handbook of graph drawing and visualization, dirigé par Roberto Tamassia.

  • [KW03] : Drawing graphs, dirigé par Dorothea Wagner et Michael Kaufmann.


Références citées dans ce chapitre

P97(1,2)

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

T63

Tutte, William Thomas. « How to draw a graph. » Proceedings of the London Mathematical Society 3.1 (1963): 743-767.

CYN84

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

BETT94

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

R86

Read, R. C. (1986). A new method for drawing a planar graph given the cyclic order of the edges at each vertex. Faculty of Mathematics, University of Waterloo.

FPP90

De Fraysseix, H., Pach, J., & Pollack, R. (1990). How to draw a planar graph on a grid. Combinatorica, 10(1), 41-51.

CP90

Chrobak, M., & Payne, T. H. (1990). A Linear Time Algorithm for Drawing Planar Graphs on the Grid. Tech. Rep. UCR-CS-90-2, Dept. of Mathematics and Computer Science, University of California at Riverside.

T13

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

KW03

Kaufmann, M., & Wagner, D. (Eds.). (2003). Drawing graphs: methods and models (Vol. 2025). Springer.