Visualisation de graphes

Logo Esipe-mlv Logo Esipe-mlv

Généralités

Définition

Un graphe est un ensemble de points, dont certaines paires sont directement reliées par un ou plusieurs liens (Wikipedia, Théorie des graphes).

Il peut se représenter sous une multitude de formes:

Mais pourquoi utiliser des graphes? Qui peut s'en servir? Comment utiliser au mieux cet outil? Les paragraphes suivants vont répondre à ces questions.

Pourquoi?

Dans notre cas, nous allons étudier les graphes comme des outils parfaitement adaptés pour comprendre un domaine étudié.

Le graphe va permettre de déterminer rapidement quelles sont les intéractions entre utilisateurs. Grâce à ce rendu visuel, il sera possible de comprendre ces intéractions et de déterminer des ensembles de groupes, regroupant des objets ayant des intérêts communs.

Cette citation est assez parlante: Un outil de visualisation bien conçu peut permettre à l'utilisateur d'observer des structures dans un graphe qu'il serait difficile ou impossible à voir dans le graphe sous sa forme brute.Voir la source.

Qui?

Dans cette partie, nous allons voir qui peut tirer profit d'une représentation de données sous forme de graphes. Imaginons que vous soyez en charge d'un projet. Celui-ci nécessite toute une analyse sur un sujet que vous connaissez mal. Vos recherches vont vous ammener à constituer un corpus d'objets en rapport avec le sujet. Vous constituez des relations entre les objets (dans la partie suivante, nous parlerons des solutions possibles pour constituer un tel corpus rapidement). Une fois toutes les données du graphe rassemblées, la personne en charge du projet modélise et visualise le graphe (voir partie solutions existantes).

Exemple

Si vous étudiez le domaine de la photo, votre graphe montrera les photographes les plus célèbres, mais aussi les principales marques (Canon, Nikon, Olympus...), les boîtiers et les objectifs incontournables regroupés par types, etc...

Finalement, le graphe vous aura appris beaucoup de choses sur le domaine en peu de temps.

Un graphe peut donc être exploité aussi bien par des analystes que par des chefs de projets souhaitant comprendre un domaine donné. Le graphe tend à ammener des discussions avec un client. Lors d'une présentation, le graphe peut être un support marquant, sur lequel le client portera une attention particulière. Des discussions peuvent s'entamer à partir de ce support ludique, pouvant aider à mieux comprendre les enjeux d'un projet, ses risques, la concurrence actuelle, etc...

Comment?

Pour pouvoir visualiser un graphe, nous savons qu'il nous faut un ensemble d'objets, et des relations entre ces derniers.

Le principal problème au début d'une analyse est donc la formation de ce corpus d'objets et de relations. Bien entendu, il est possible d'assembler un graphe manuellement, en répertoriant les objets suite à des analyses d'ouvrages, ou tout autre type de recherches. Cependant, cette méthode demande un investissement bien trop conséquent, et le corpus restera de petite taille.

Vient alors l'idée de se servir de larchitecture du Web: nous faisons face à des pages reliées entre elles via des liens hypertextes. Les objets du corpus seront tous représentés par des URLs, dont les pages associées parlent du domaine étudié. Il faudra donc lancer un robot d'exploration (aussi appelé crawler). Voici comment procéder:

  1. le responsable constitue un petit corpus d'URLs parlant du sujet
  2. un robot d'exploration est lancé à partir de ce corpus: il repère les liens contenus dans les URLs, les suit, et ajoute ces liens au corpus initial.
  3. le robot extrait récursivement des URLs, jusqu'à atteindre une limite définie par le responsable (exemple: extraire 10 000 pages au maximum).

La partie suivante va permettre de comprendre ce qu'est un outil de visualisation, et donnera des exemples de types de données pouvant repésenter des graphes. Ces objets peuvent représenter tout et n'importe quoi, tant qu'ils restent spécifiques au domaine étudié.