Dessin de graphes et visualisation d’information

8L’ouvrage de di Battista et al. [12] constitue une bonne introduction au domaine du dessin de graphes, présentant plus de trois cents algorithmes. Un état de l’art de la visualisation de graphes [13], plus récent, recense également un grand nombre de techniques, parfois interactives, pour représenter les graphes et les réseaux. En général, ces techniques tentent d’optimiser un certain nombre de critères esthétiques, comme, par exemple, limiter le nombre de croisements des liens ou bien placer les nœuds pour avoir une longueur uniforme de tous les liens. Plusieurs études ont été réalisées pour déterminer quels critères sont les plus importants et ainsi tenter de découvrir le meilleur algorithme de dessin de graphe. Cependant, il existe un tel nombre de critères qu’il est difficile de former des conclusions générales.

Figure 1.

Réseau d’amitiés entre garçons (triangles) et filles (cercles) par J. Moreno.

Figure 1. Réseau d’amitiés entre garçons (triangles) et filles (cercles) par J. Moreno. Un acteur central lie les deux groupes (triangle du milieu gauche)

Réseau d’amitiés entre garçons (triangles) et filles (cercles) par J. Moreno.

Figure 2.

Réseau d’amitiés entre lycéens par J. Moody, la couleur marque l’origine ethnique.

Figure 2. Réseau d’amitiés entre lycéens par J. Moody, la couleur marque l’origine ethnique. Quatre groupes sociaux émergent après application d’un algorithme de clustering. Ces quatre groupes montrent que les relations d’amitiés sont fortement corrélées avec l’âge et l’origine ethnique des lycéens

Réseau d’amitiés entre lycéens par J. Moody, la couleur marque l’origine ethnique.

9Le domaine de la visualisation d’information a une perspective différente sur le sujet. Ce domaine de recherche se focalise sur l’exploration visuelle et la découverte ou la communication d’informations. Ainsi, les réseaux présentés en figure 1 et figure 2 n’optimisent certainement pas des critères esthétiques, comme la minimisation du nombre de croisements de liens, mais ils permettent de mettre en lumière certaines informations importantes sur la structure du réseau. Dans cet article, nous présentons une série de représentations alternatives aux diagrammes nœud-lien, non pas pour les remplacer mais plutôt pour les compléter. Dans le contexte de l’analyse exploratoire, nous pensons qu’il est nécessaire d’avoir plusieurs perspectives sur les données pour en découvrir toutes les arcanes.

Exploration de réseau et passage à l’échelle

10Un problème récurrent se pose quand le réseau à représenter contient beaucoup de nœuds ou de liens : le diagramme nœud-lien se transforme en un amas de traits et de points difficile voire impossible à transformer en représentation lisible, ni manuellement ni automatiquement. Dans la littérature, il existe trois techniques distinctes pour tenter de résoudre ce problème :

1. réduire la quantité d’information représentée par filtrage ou agrégation. Il existe plusieurs méthodes pour échantillonner les réseaux [14] ou bien calculer des clusters [15] (groupe d’éléments similaires), qui peuvent être ensuite agrégés en un élément représentatif du groupe ;
2. proposer une représentation interactive pour explorer la totalité du réseau. Plusieurs outils de visualisation ne représentent qu’une partie du réseau et proposent de naviguer interactivement pour explorer le reste du réseau. Les stratégies varient : certaines se concentrent sur un nœud particulier et permettent la navigation en suivant les connexions [16], d’autres sont basées principalement sur du filtrage interactif [17] ou bien permettent la navigation dans un réseau agrégé [18] ;
3. utiliser des représentations alternatives aux diagrammes nœud-lien. Cette stratégie consiste à utiliser différentes métaphores visuelles pour la représentation de réseaux. L’idée est de découvrir des représentations permettant d’« augmenter l’espace visuel », permettant d’afficher un plus grand nombre d’information de façon plus lisible.

11La psalmodie de la visualisation d’information [19] est : « vue d’ensemble d’abord, zoomer et filtrer, puis détails à la demande » (overview first, zoom and filter, then details on demand). Cette phrase résume le processus d’exploration visuel.

12Ainsi, il est primordial de présenter une vue d’ensemble du réseau afin d’initier le processus d’exploration. Les deux premières stratégies, visant à supprimer l’information ou à n’en présenter qu’une partie, ne sont donc pas satisfaisantes. Nous nous sommes donc intéressés à la troisième solution : utiliser des représentations alternatives pour explorer les réseaux.

3D et espaces géométriques non euclidiens

13Afin d’augmenter l’espace visuel, un certain nombre de chercheurs ont tenté d’utiliser la 3^e dimension. L’idée est qu’une troisième dimension permet d’avoir plus d’espace pour dessiner de plus grands réseaux mais aussi permet d’optimiser certains critères esthétiques tels que la minimisation du nombre de croisements. Plusieurs programmes utilisent la 3D, la figure 3a montre un exemple créé avec la boîte à outils de dessin de graphes Tulip [20]. Le principal problème lié à l’utilisation de la 3D est l’occlusion : les utilisateurs ont l’impression que les représentations sont « encombrées » et trouvent difficile d’avoir une représentation mentale de la totalité du graphe [21]. Pour palier à ces problèmes, plusieurs stratégies ont été adoptées [22], comme l’utilisation de multiples vues ou des techniques de navigation pour voir la représentation sous de multiples angles. Malheureusement, dans la majorité des cas, ces techniques désorientent l’utilisateur et rendent les visualisations peu efficaces [23]. Plusieurs études ont montré que, si les visualisations 3D sont attractives, elles n’améliorent pas les performances et les détériorent même pour certaines tâches [24].

14Une autre façon d’augmenter l’espace visuel est l’utilisation de la géométrie hyperbolique au lieu de la géométrie Euclidienne. Dans l’espace hyperbolique, le postulat du parallélisme est rejeté : deux lignes parallèles dans l’espace euclidien divergent l’une de l’autre. Donc, si l’on considère un disque dans l’espace hyperbolique, l’espace augmente exponentiellement lorsque l’on s’éloigne de son centre. Ainsi, un réseau dessiné sur ce disque dispose d’un espace infini sur ses bords, ce qui permet d’afficher plus d’information, comme le montre figure 3b. La métaphore s’applique aussi à la 3D [25]. Malheureusement, similairement à la 3D, naviguer dans un espace géométrique non euclidien désoriente l’utilisateur. Il est de plus difficile de se constituer une carte mentale du réseau sans recours à la géométrie 2D euclidienne [26].

Représenter un graphe par un arbre

15Une autre stratégie pour représenter des réseaux peu denses et augmenter leur lisibilité est de les représenter sous forme d’arbres et de le « réparer » avec des connexions supplémentaires. Les algorithmes de dessin d’arbres permettent effectivement d’ôter tous croisements voire d’exploiter au maximum l’espace utilisé si l’arbre est dessiné en utilisant des inclusions de formes.

Figure 3.

Représentation d’un réseau en 3D (a) et dans l’espace hyperbolique (b)

Figure 3. Représentation d’un réseau en 3D (a) et dans l’espace hyperbolique (b) (a) (b)

Représentation d’un réseau en 3D (a) et dans l’espace hyperbolique (b)

Figure 4.

Représentation d’un réseau sous forme d’arbre avec des liens supplémentaires (a) et sous forme de Treemap avec des liens supplémentaires (b)

Figure 4. Représentation d’un réseau sous forme d’arbre avec des liens supplémentaires (a) et sous forme de Treemap avec des liens supplémentaires (b) (a) (b)

Représentation d’un réseau sous forme d’arbre avec des liens supplémentaires (a) et sous forme de Treemap avec des liens supplémentaires (b)

16Pour dessiner un réseau sous forme d’arbre, il est nécessaire de calculer un arbre recouvrant (généralement on prend le plus grand), de dessiner cet arbre puis d’ajouter les liens supplémentaires [27]. Un exemple est présenté dans la figure 4a. Cette technique fonctionne bien pour des réseaux ayant une structure différant peu de celle d’un arbre tels que les arbres généalogiques par exemple, mais la représentation devient illisible pour des réseaux plus denses.

17Une alternative est la représentation sous forme de Treemap [28]. Le principe est identique au précédent, mais la représentation utilisée pour l’arbre recouvrant diffère : il s’agit de découper l’espace successivement pour représenter la hiérarchie (imbrications de boîtes). Par exemple, un arbre très simple composé d’une racine, de deux nœuds et de quatre feuilles sur chacun d’eux, est alors représenté par un rectangle occupant tout l’espace visuel, contenant deux rectangles de taille identique (représentant les nœuds), eux-mêmes sub-divisés en quatre rectangles de taille identique. Les liens supplémentaires du réseau sont alors dessinés par dessus le Treemap [29] comme montré sur la figure 4b. Cette représentation devient également difficile à lire si le nombre de liens supplémentaires est important.

18L’ajout d’interaction est une piste intéressante pour améliorer la lisibilité de ces représentations. Elle est particulièrement bien exploitée dans TreePlus [30], un système visualisant une portion du réseau sous forme d’arbre et permettant de naviguer interactivement dans le reste. Afin de résoudre le problème des cycles, dans cette représentation sous forme d’arbre, des nœuds sont dupliqués. Si ce système permet de mieux réaliser un certain nombre de tâches, il rend difficile la constitution d’une carte mentale de la totalité du réseau.

Représentation matricielle

19Les graphes ont deux représentations canoniques : les diagrammes nœud-lien et les matrices d’adjacence. Une matrice d’adjacence représente chaque sommet d’un réseau à la fois comme une ligne et comme une colonne. Si deux sommets sont connectés, la case correspondant à l’intersection de la ligne et de la colonne est marquée. Traditionnellement, on utilise une valeur numérique (0 marquant l’absence de connexion, 1 marquant la présence), soit par une marque graphique comme dans la figure 5. Le tableau 1 liste les principaux avantages et inconvénients des représentations matricielles par rapport aux diagrammes nœud-lien.

Tableau 1.

Avantages et inconvénients des représentations matricielles

Tableau 1. Avantages et inconvénients des représentations matricielles Pour Contre Absence de superpositions des nœuds Taille de l’espace visuel requis à un (ce qui permet de pouvoir toujours lire niveau de détail équivalent plus les étiquettes portées par les nœuds) important que le diagramme nœud-lien Absence de croisements des liens Difficulté à effectuer des tâches de suivi (ce qui permet de toujours identifier la de chemin (suivre les liens de Pierre à source et destination des connexions) Paul passant par Marie) Facilité avec laquelle il est possible Manque de familiarité, les matricese les d’identifier les absences de connexions paraissent moins intuitives qudiagrammes nœud-lien

Avantages et inconvénients des représentations matricielles

20Plus de détails sur les performances des deux représentations de réseaux sont présentés dans les travaux de Ghoniem et al [31]. Il s’agit d’une comparaison plus quantitative de la lisibilité des représentations matricielles et des représentations nœud-lien pour des graphes de différentes tailles et densités. Dans cette étude, une liste de tâches de base a été utilisée pour évaluer la lisibilité des représentations : estimer le nombre de nœuds, estimer le nombre de connexions, trouver le nœud le plus connecté, trouver le nœud portant une étiquette donnée, trouver la connexion entre deux nœuds donnés, trouver un nœud commun à deux nœuds donnés et trouver un chemin entre deux nœuds donnés.

21De manière générale, les résultats de leur expérimentation montrent que les nœud-lien sont plus efficaces pour les graphes de petite taille et peu denses alors que les matrices ont de meilleures performances dès que les graphes sont plus grands (>20 nœuds !) et plus denses pour toutes les tâches excepté le suivi de chemin. Ces résultats ainsi que les pros et cons listés précédemment révèlent le vaste potentiel de le représentation matricielle pour explorer les réseaux sociaux.

Réordonner les matrices

23Dans son livre faisant référence en visualisation d’information [32], Bertin présente la matrice réordonnable. Au travers de plusieurs exemples, il démontre que réordonner les lignes et colonnes d’une matrice permet d’améliorer significativement sa compréhension.

24Prenons pour exemple la figure 5 extraite de ce livre ; la matrice présentée contient seulement 5 lignes et 5 colonnes représentant la production de 5 types de viande dans 5 pays. En transformant la matrice originale, contenant des valeurs numériques, en matrice visuelle, codant les valeurs par des formes géométriques de différentes tailles et en réordonnant « intelligemment » ses lignes et ses colonnes, il devient beaucoup plus simple d’interpréter ce jeu de données. En effet, il est pratiquement immédiat d’observer que la France est le pays ayant la plus grande production, tout type de viande confondu ; que la Belgique a la plus petite et qu’il existe trois différents profils de production (marqué par A, B et C dans la figure). Pour aller une étape plus loin dans l’interprétation de ce simple exemple, imaginons qu’une loi doive être votée pour limiter la production d’un type de viande produit en grande quantité par les pays.

Figure 5.

Matrice réordonnable de J. Bertin, extraite de la Sémiologie graphique.

Figure 5. Matrice réordonnable de J. Bertin, extraite de la Sémiologie graphique. Cette image montre la production de 5 pays pour 5 types de viande. Bertin démontre que la représentation visuelle et la permutation de lignes et colonnes permet d’identifier rapidement des tendances dans les données (ici, les groupes A, B et C)

Matrice réordonnable de J. Bertin, extraite de la Sémiologie graphique.

25Disposant de ces données et de la représentation visuelle associée, un analyste pourra rapidement observer que la Belgique est le pays a convaincre de ne pas accepter cette loi, car son profil de production est plutôt neutre alors que les autres pays voterons dans leur propre intérêt, contraire à celui de l’autre groupe.

26Cet exemple démontre l’importance du réordonnancement des matrices : si les représentations matricielles dont les lignes et les colonnes sont ordonnées aléatoirement sont lisibles, une fois réordonnées elles deviennent réellement exploitables.

Figure 6.

Correspondance entre les motifs visuels des matrices et ceux des diagrammes nœud-lien : A montre un acteur connectant plusieurs communautés, B deux communautés et C une clique

Figure 6. Correspondance entre les motifs visuels des matrices et ceux des diagrammes nœud-lien : A montre un acteur connectant plusieurs communautés, B deux communautés et C une clique .

Correspondance entre les motifs visuels des matrices et ceux des diagrammes nœud-lien : A montre un acteur connectant plusieurs communautés, B deux communautés et C une clique

Naviguer dans de grandes matrices

29A niveau de détail équivalent, la représentation matricielle utilise plus d’espace que les diagrammes nœud-lien. Par exemple, sur un écran de 17 pouces, il est possible d’afficher seulement une centaine de nœuds si l’on souhaite pouvoir lire confortablement leurs noms. Ainsi, afin de tirer parti du potentiel des matrices, il est nécessaire d’avoir des outils efficaces de navigation.

30De nombreuses techniques existent dans le domaine de l’Interaction Homme-Machine pour permettre de se déplacer dans de grands espaces visuels et/ou à divers niveaux de détails. Par exemple, les techniques de Focus+Context [35] telles que la vue à vol d’oiseau (bird’s eye view) permettent d’avoir une vue d’ensemble miniature et une vue zoomée d’une partie de la représentation. Ces techniques ne sont pas directement utilisables dans notre contexte, elles requièrent quelques aménagements. Il est notamment indispensable de toujours voir les étiquettes des lignes et colonnes des matrices et de faciliter les transitions entre les divers niveaux de détails pour éviter à l’analyste de se perdre lors de l’exploration. Plusieurs systèmes intègrent ces outils de navigation tels que MatrixZoom [36] et la matrice d’appels multi-niveaux présentée par van Ham [37].

Initier l’exploration

32L’avantage majeur des matrices par rapport aux diagrammes nœud-lien est de permettre d’avoir une vue d’ensemble du réseau toujours exploitable et ce, même pour de très grands graphes, alors que les diagrammes nœud-lien ne montrent bien souvent qu’un amas de liens et de nœuds superposés.

33Prenons l’exemple d’un réseau social contenant les données d’échanges de courrier électronique entre plus de 450 personnes pendant un an (les sommets sont les personnes et les liens sont les courriers). La figure 7 montre deux représentations de ce réseau. Alors que la représentation nœudlien (utilisant un algorithme de placement traditionnel par forces) permet éventuellement de former l’hypothèse que le réseau est très dense ; la représentation matricielle, elle, donne beaucoup plus d’information. Pour le démontrer, analysons brièvement la matrice présentée à la figure 7.

34Dans cette représentation, chacun des points noirs représente une connexion entre une ligne et une colonne (un lien dans le réseau), le gris marquant donc l’absence de connexion. Tout d’abord, on peut clairement rejeter l’hypothèse précédente : le réseau social n’est pas très dense car on peut observer une majorité de gris dans cette matrice. Deuxièmement, si l’on regarde de plus près la représentation, on peut voir plusieurs blocs de points noirs. Il s’agit de clusters : des groupes de recherche dont les membres échangent des courriers électroniques les uns avec les autres. Une autre observation permet de voir une sorte de croix : une ligne constituée de points noirs verticale et une horizontale (à peu près de la longueur d’une moitié de la matrice). Il s’agit d’un membre du service des missions de cet institut, celui-ci échange effectivement des courriers électroniques avec beaucoup des membres d’équipes, il a donc un grand nombre de connexions.

35Ce simple exemple démontre que les matrices procurent une vue d’ensemble permettant d’initier l’exploration d’un jeu de données en mettant en évidence plusieurs éléments saillants. Le point important est d’apprendre à les décoder, car ces représentations sont beaucoup moins familières que les diagrammes nœud-lien. La figure 6 donne quelques exemples de correspondance entre les motifs visuels courant dans les réseaux sociaux à la fois pour les représentations nœud-lien et matricielles.

Explorer interactivement

36A l’issue d’entretiens avec des analystes et de séances d’observation, nous nous sommes rendu compte que le processus d’exploration visuel est constitué d’opérations successives pour configurer les représentations (ajuster la position des éléments graphiques et les attributs visuels), filtrer certains éléments, les grouper et éventuellement les agréger. Il est important de créer de vues multiples d’un jeu de données, l’analysant sous divers aspects et plusieurs niveaux de détail afin d’identifier sa structure. Par exemple, une représentation matricielle peut permettre d’identifier plusieurs communautés alors qu’un diagramme nœud-lien égocentré peut permettre l’analyse détaillée des connexions d’un acteur important. Dans MatrixExplorer, nous avons donc décidé de proposer plusieurs vues sur les données (figure 8) et d’offrir un grand nombre d’outils pour manipuler directement [39] les représentations.

Figure 7.

Réseau d’échange de courriers électroniques entre plus de 450 chercheurs, pendant un an. Nœud-lien (a), matrice (b)

Figure 7. Réseau d’échange de courriers électroniques entre plus de 450 chercheurs, pendant un an. Nœud-lien (a), matrice (b)

Réseau d’échange de courriers électroniques entre plus de 450 chercheurs, pendant un an. Nœud-lien (a), matrice (b)

Figure 8.

Interface de MatrixExplorer, combinant matrices (grande fenêtre de gauche) et nœud lien (grande fenêtre de droite).

Figure 8. Interface de MatrixExplorer, combinant matrices (grande fenêtre de gauche) et nœud lien (grande fenêtre de droite). Une représentation Treemap (petite fenêtre de gauche) montre la macrostructure du réseau, i.e. ses composantes connexes. Des vues miniatures des représentations permettent la navigation (petites fenêtres de droite)

Interface de MatrixExplorer, combinant matrices (grande fenêtre de gauche) et nœud lien (grande fenêtre de droite).

37Tout d’abord, nous avons synchronisé les deux visualisations (matricielle et nœud-lien) afin de combiner leurs avantages et de faciliter l’identification des motifs visuels. Il est ainsi possible d’utiliser les matrices pour certaines tâches et les diagrammes nœud-lien pour d’autres. Si un analyste souhaite avoir une vue d’ensemble sur un réseau et, par exemple, identifier ses principales communautés, il est préférable qu’il utilise une représentation matricielle. Par contre, lors d’une analyse plus détaillée, s’il est nécessaire d’identifier un plus court chemin entre deux acteurs du réseau, le diagramme nœud-lien constitue une meilleure alternative.

38De plus, synchroniser les deux représentations par la sélection permet de comparer la représentation d’un motif visuel dans l’une et l’autre représentation, facilitant ainsi leur compréhension (et l’apprentissage des matrices).

39Pour manipuler interactivement les deux représentations nous avons mis en place un certain nombre de fonctionnalités :

1. spécification interactive des attributs visuels comme la couleur des nœuds, des en-têtes des lignes et de colonnes dans les matrices, ou bien encore l’épaisseur des liens ou la couleur des cellules de la matrice ;
2. méthodes automatiques et interactives pour le placement des nœuds des diagrammes nœud-lien et le réordonnancement des lignes et colonnes des matrices. En particulier, nous avons développé plusieurs outils d’aide au réordonnancement en proposant d’appliquer des algorithmes automatiques sur des portions de matrices ou bien de bloquer l’ordre de plusieurs lignes et colonnes lorsque l’analyste souhaite les conserver ;
3. filtrage interactif de nœuds ou de connexions en fonction d’une sélection ou d’un attribut particulier présent dans les données (l’âge ou le sexe des personnes contenues dans le réseau social par exemple) ;
4. clustering interactif permettant d’identifier les différents groupes ou communautés détectées pour les marquer par un attribut visuel tel que la couleur ;
5. finalement, plusieurs vues d’ensemble sont proposées : miniatures des visualisations dans lesquelles l’analyste peut se déplacer ou représentations sous forme de Treemap de la macrostructure du réseau (voir figure 8).

40En combinant les deux représentations et permettant de les manipuler interactivement, les utilisateurs de MatrixExplorer peuvent créer de multiples vues sur leurs données et les explorer à divers niveaux de détail.

Trouver un consensus

41Comme chaque visualisation présente une perspective différente, nous avons tenté de favoriser l’établissement de consensus à l’aide d’interactions simples. La figure 9 donne un exemple. Pour faciliter cette recherche de consensus, nous avons également introduit la sélection approximative : possibilité de marquer le degré d’appartenance d’un élément à un cluster (représenté par une couleur plus claire par exemple) ; et le clustering multiple : possibilité de marquer l’appartenance d’un élément à plusieurs clusters.

Figure 9.

Figure 9. L’image du milieu montre l’identification de plusieurs clusters de la matrice initiale. Après réordonnancement, nous constatons que l’un des clusters (entouré par un ovale) est conservé alors que l’autre (entouré par un rectangle) se retrouve divisé en trois morceaux. Il y donc seulement consensus sur une partie des clusters identifiés ; il faut continuer à explorer pour en identifier éventuellement d’autres

Présenter l’information

42Alors que la matrice permet principalement d’explorer les données et d’en manipuler une grande quantité, le diagramme nœud-lien est indispensable pour présenter des résultats et communiquer des découvertes. Ainsi, une fois le réseau filtré et éventuellement agrégé, MatrixExplorer permet d’extraire directement des images nœud-lien du résultat.

Augmenter les matrices

44Comme l’ont montré les travaux sur la lisibilité de la matrice [40], la tâche de base pour laquelle cette représentation est moins performante que les diagrammes nœud-lien est le suivi de chemin. Pour remédier à ce problème, nous avons créé MatLink [41], une représentation matricielle augmentée (figure 10).

45Le principe de MatLink est de dessiner des liens sur les bords de la matrice afin de mieux représenter la connectivité et faciliter le suivi de chemin. Deux catégories de liens sont ajoutées sur la matrice : des liens statiques (en blanc sur l’image) et des liens interactifs (en plus foncé sur l’image) qui apparaissent uniquement lors d’un survol ou d’un clic de la souris sur les entêtes des lignes et colonnes. Lorsque l’utilisateur sélectionne deux éléments, les liens apparaissent montrant un plus court chemin.

Figure 10.

Figure 10. MatLink augmente les matrices en ajoutant des liens statiques (en blanc) et des liens interactifs (en plus foncés sur les en-têtes) pour aider au suivi de chemin

Figure 11.

Figure 11. Les liens permettent à l’analyste d’être conscient que des éléments connectés aux nœuds qu’il étudie existent en dehors de la vue courante (le cercle montre ces indices : les liens quittant la vue)

46Nous avons réalisé une expérimentation contrôlée similaire à celle de Ghoniem et al. afin d’étudier si cette représentation améliorait significativement la représentation matricielle standard. Nous avons testé un lot de tâche de lisibilité de base ainsi que plusieurs tâches spécifiques à l’analyse de réseaux sociaux : trouver un point d’articulation, trouver une clique et identifier plusieurs communautés (groupe fortement connecté).

47D’une manière générale, nous avons démontré que MatLink améliore significativement la représentation matricielle standard, en particulier pour la tâche de suivi de chemin, auparavant très laborieuse à réaliser. Pour ce cas précis, MatLink montre même des performances supérieures au diagramme nœud-lien pour les graphes denses (et ce, même augmenté de surlignage interactif) à cause du grand nombre de superpositions et de croisements. La seule tâche pour laquelle les diagrammes nœud-lien restent plus performants est l’identification de points d’articulation. Cette tâche requiert assez grande familiarité avec la représentation matricielle, ce qui n’était pas le cas de nos participants (qui, en moyenne, disposaient de 30 minutes d’entraînement avec les matrices).

Figure 12.

Mélange permet de « plier » l’espace pour voir deux régions éloignées de la matrice tout en preservant le contexte intermédiaire

Figure 12. Mélange permet de « plier » l’espace pour voir deux régions éloignées de la matrice tout en preservant le contexte intermédiaire

Mélange permet de « plier » l’espace pour voir deux régions éloignées de la matrice tout en preservant le contexte intermédiaire

Naviguer dans de grandes matrices

48Le second avantage de MatLink est l’amélioration que la technique offre pour la navigation dans de grandes matrices. Un des inconvénients des matrices est la grande taille requise pour les représenter. Ainsi, il peut (souvent) arriver qu’un acteur soit connecté à plusieurs autres acteurs placés en dehors de la vue. Il est nécessaire de naviguer sur toute la largeur (ou hauteur) de la matrice pour identifier tous les voisins d’un acteur particulier, ce qui est laborieux. Grâce aux liens affichés dans MatLink, et par un simple clic sur l’acteur étudié, l’analyste a un retour visuel immédiat sur tous les éléments connectés à cet acteur et possède une indication pour ceux placés hors de l’écran. La figure 11 présente un exemple.

49En outre, afin de faciliter l’exploration de ces grandes matrices (et le déplacement jusqu’aux éléments placés hors de la vue), nous avons mis au point une technique de navigation « pliant l’espace » : Mélange [42]. Cette technique permet de visualiser deux parties de la matrice dans une même vue, en offrant un aperçu de l’espace intermédiaire, comme illustré dans La figure 12. Mélange offre même la possibilité de zoomer sur l’une des régions d’intérêt indépendamment de l’autre.

Figure 13.

Figure 13. Représentation nœud-lien (à gauche) dans laquelle il est difficile d’identifier que les nœuds en noir ne sont pas connectés. La représentation NodeTrix (au milieu) visualise les sous-parties denses en matrices, il devient alors possible de voir les absences de connexions (matrice du haut gauche avec des cellules manquantes). Enfin, dupliquer des nœuds (à droite) permet d’améliorer la lisibilité en supprimant des croisements de liens inter-communautés

Figure 14.

Interagir avec la représentation matricielle pour mieux comprendre la structure de la communauté.

Figure 14. Interagir avec la représentation matricielle pour mieux comprendre la structure de la communauté. Ici, en ôtant une personne de la communauté, il est possible de voir qu’il s’agit d’un point d’articulation

Interagir avec la représentation matricielle pour mieux comprendre la structure de la communauté.

Fusionner matrices et nœud-lien

50La structure des réseaux sociaux varie beaucoup : certains exhibent une structure d’arbre (ou presque) très peu dense tels les arbres généalogiques, d’autres ont des structures quasi complètes (réseau bipartite très dense) tels que les réseaux d’import/export entre pays du monde et enfin, certains ont une structure intermédiaire, localement dense mais globalement creuse, il s’agit des réseaux petit-monde [43] tels que les réseaux d’amitiés ou encore de communication.

Figure 15.

Représentation NodeTrix pour l’exploration.

Figure 15. Représentation NodeTrix pour l’exploration. Les étiquettes sont toutes lisibles et permettent l’interaction pour éditer la représentation. (Réseau de copublication d’infovis contenant plus d’une centaine d’acteurs)

Représentation NodeTrix pour l’exploration.

51Les représentations visuelles que nous avons présentées précédemment sont plus ou moins performantes selon le type de réseau à visualiser. Par exemple, les diagrammes nœud-lien ainsi que les représentations basées sur des arbres avec liens supplémentaires (Treemap+liens par exemple) sont particulièrement efficaces pour les réseaux peu denses présentant une structure d’arbres. Au contraire, si le réseau à représenter est plutôt dense ou bipartite et présentant une structure quasi complète, la représentation matricielle est alors tout indiquée. Par contre, le choix n’est pas si simple pour les réseaux petit-monde.

52Le problème que posent les réseaux petit-monde réside dans la variation de la densité locale. Si l’on choisit un diagramme nœud-lien, alors les parties denses (communautés) ne sont pas lisibles. Inversement, si l’on choisit une matrice, alors la majorité de l’espace est vide et l’exploration requiert beaucoup de navigation. Une possibilité est alors d’utiliser MatrixExplorer, combinant les deux représentations, mais le coût cognitif est plus élevé.

53Pour ne plus avoir à choisir, nous avons mis au point une seconde représentation hybride, fusionnant matrice et diagramme nœud-lien : NodeTrix [44]. Le principe de NodeTrix est de représenter le réseau global comme un nœud-lien mais d’utiliser une représentation matricielle pour ses sous parties les plus denses. Deux exemples sont présentés figure 13 et figure 15.

Présenter l’information

59Le grand avantage de NodeTrix est sa versatilité : il est possible de l’utiliser pour explorer un réseau et découvrir sa structure mais aussi pour en faire une représentation très compacte et l’utiliser pour présenter des résultats. Un exemple est présenté figure 16.

Figure 16.

Représentation NodeTrix compacte pour la communication (réseau de co-publication d’InfoVis contenant plus d’une centaine d’acteurs).

Figure 16. Représentation NodeTrix compacte pour la communication (réseau de co-publication d’InfoVis contenant plus d’une centaine d’acteurs). Des types de collaboration sont clarement visibles. Croix : un chercheur senior et ses étudiants (Bederson, Plaisant, Shneiderman, Eick). Blocs : des chercheurs collaborant beaucoup les uns avec les autres (Parc, Berkeley). Motif visuel intermédiaire (CMU-Roth)

Représentation NodeTrix compacte pour la communication (réseau de co-publication d’InfoVis contenant plus d’une centaine d’acteurs).

60Cette souplesse d’utilisation est liée à l’intégration des représentations matricielles et à leur capacité à produire à la fois une vue d’ensemble et une vue de détail. En mode présentation des résultats, il est alors possible de réduire au maximum la taille des communautés représentée par des matrices, faisant disparaître les étiquettes individuelles de chacun des membres (mais en conservant une étiquette pour la communauté par exemple) mais permettant de conserver un aperçu de la connectivité à l’intérieur de la communauté. La figure 15 et la figure 16 sont un bon exemple, toutes deux représentent le même réseau, à des niveaux de détail différents.