Visone (logiciel)

En 1996, un groupe de recherche fut établi en Allemagne à l'université de Constance entre un groupe de recherche en informatique, sur les algorithmes et structures de données, et un groupe de recherche en politique, sur l'administration publique. En 1999, le groupe publia des articles sur la visualisation des réseaux sociaux et, avec l'obtention du financement de DFG en 2001 (dans le cadre de l'algorithmique des réseaux complexes), la première version du logicielle vit le jour en 2002[1]. Sa conception repose principalement sur deux thèses : celle d'Ulrik Brandes[2], sur la visualisation des graphes, et celle de Michael Baur expliquant le logiciel et son application à l'analyse des réseaux sociaux[3].

Exemples graphiques

L'utilisateur peut créer des gabarits pour les nœuds et arcs, décrivant l'apparence de ceux-ci, et les appliquer au cas par cas ou globalement. Dans cet exemple, il y a deux gabarits pour les nœuds (carrés bleus et triangles verts) ainsi que deux pour les arcs (trait noir et pointillés rouges).

Après l'application d'une transformation géométrique utilisant le meilleur angle.

Visualisation en groupant les sommets et en les coloriant par ID.

Un réseau est représenté par un graphe, celui-ci pouvant par exemple être pondéré ou orienté. Un algorithme pour analyser le graphe est conçu avec des restrictions : par exemple, certains nécessitent que le graphe ne soit pas orienté tandis que d'autres ont besoin de poids strictement positifs. Le problème majeur auquel les utilisateurs peuvent être confrontés avec les nombreux outils d'analyse existant est que l'algorithme qu'ils veulent utiliser n'est pas valide sur le graphe à analyser, et celui-ci doit être transformé manuellement. Ce problème est résolu par Visone en définissant les algorithmes avec aussi peu de restrictions que possibles et, si une restriction empêche l'application, par une transformation automatique du graphe[3].

Le graphe représenté est un multigraphe orienté. Un graphe peut être obtenu par exemple en collectant des informations sur les relations entre des habitants d'une ville, en demander à chaque habitant de donner la liste de ses amis ; il peut arriver qu'un habitant ${\displaystyle A}$ mentionne ${\displaystyle B}$ comme ami mais que ${\displaystyle B}$ ne mentionne pas ${\displaystyle A}$ : il n'est donc pas certain qu'ils soient réellement amis. Pour gérer ces problèmes d'incertitudes survenant dans la collecte des données, Visone permet de spécifier la réciprocité d'un arc : un arc peut-être confirmé par le sommet dont il émane ou par son sommet de destination. Le chercheur garde ainsi le choix[note 1], lors de l'application d'un algorithme, de traiter les arcs n'étant pas confirmés en les supprimant[note 2] ou en les considérant comme normaux[3].

Un nombre illimité d’attributs peut être assigné aux arcs et sommets, avec un type fixe[note 3]. Par exemple, un attribut poids dont le type est nombre peut être utilisé pour chaque arc afin de signaler la force de la connexion entre deux sommets. De même, un attribut nom dont le type est texte pour chaque sommet permet de spécifier le nom de la personne qu'il représente. Lors de la collection d'informations, il y a généralement davantage que les simples relations montrées par les sommets et arcs du graphe : si chaque sommet représente une personne, alors des informations sur cette personne auront également été collectées. Les attributs permettent donc d'importer l'ensemble des informations collectées. Ils peuvent aussi être utilisés pour ajouter des informations obtenues par l'analyse du graphe : par exemple, les sommets peuvent être classés et un attribut rang signalera l'ordre pour chaque sommet. Les algorithmes d'analyse peuvent utiliser le poids et grouper des éléments partageant des mêmes valeurs pour un attribut quelconque[3].

Le format utilisé par Visone est GraphML qui est une représentation du graphe en XML. Il peut également utiliser le format requis par les logiciels Pajek ou UCINET, ou une matrice d'adjacence.

Les algorithmes d'analyse utilisent une version dirigée et pondérée du graphe. Puisque chaque arc peut se voir assigner un nombre infini d'attributs, il faut indiquer lors de l'utilisation d'un algorithme quel est l'attribut représentant le poids d'un arc. Il est possible de le faire de deux façons : en choisissant un attribut comme la force de l'arc (les valeurs élevées sont les meilleures), ou comme la distance de l'arc (les valeurs faibles sont les meilleures). Si l'utilisateur ne souhaite pas spécifier de poids, alors tous les arcs auront la même valeur. Les sommets peuvent être classés selon des algorithmes de centralité, c'est-à-dire qui évaluent la position d'un sommet dans le graphe par rapport aux autres :

• par degré, c'est-à-dire par nombre de voisins.
• par closeness(proximité), c'est-à-dire par l'inverse de la distance à tous les autres sommets.
• par eccentricity(excentricité), c'est-à-dire par l'inverse de la distance maximale à tous les autres sommets. Le sommet avec la plus petite distance par rapport aux autres est le plus central (i.e. valeur d’eccentricity la plus élevée) ; de même pour closeness.
• par betweenness(centralité ou bien son entregens). Lorsque le meilleur chemin, c'est-à-dire le plus court, entre plusieurs sommets passe par un même sommet alors sa centralité de betweenness est élevée. Lorsque le graphe est pondéré, le poids d'un plus cour chemin est le produit des poids de ses arcs.

Certaines mesures de centralité peuvent s'appliquer aux arcs au lieu des sommets. Par exemple, la betweenness considérera le nombre de plus courts chemins passant par un arc au lieu de passer par un sommet.