Deux ateliers R : deux présentations

Deux ateliers méthodologiques sur R ont eu lieu à Toulouse en Mai dernier. La première séance était une séance d’initiation, de discussion et de présentation autour de R tandis que la seconde portait sur l’utilisation de R pour l’analyse de réseau.

Ci-dessous, nous mettons à disposition les supports qui ont alimenté la discussion lors de ces rencontres en petits comités. Un peu de temps a passé depuis ces ateliers mais le contenu est toujours d’actualité (sauf le lien pour télécharger les documents). Il est à noter que le nombre de packages CRAN a bien évolué depuis, passant de 5531 au 12 mai 2014 à 5894 au 17 septembre 2014!

Le premier support donne un aperçu d’ensemble de R: R comme langage interprété, comme système d’exploration interactif,  comme environnement de programmation.

Le second est une présentation sommaire des différents packages permettant de faire de l’analyse de réseau avec R.

Ces ateliers animés avec Sébastien Plutniak ont été soutenus par le Labex Structuration des Mondes Sociaux (SMS) et organisés par le groupe ResTo (Réseaux Sociaux à Toulouse). Merci à tous de m’avoir permis de diffuser ce contenu en ligne et merci à Pauline pour son regard acéré.

Ecole d’été Ferney-Voltaire, Les réseaux, août 2014 (suite)

Ci-dessous, une présentation réalisée à l’occasion de l’Université d’été Ferney-Voltaire consacrée aux réseaux (voir le programme sur le site http://ferney2014.sciencesconf.org/). Cette présentation a servi de support pour l’atelier PAJEK.

Elle comprend une brève introduction à l’analyse de réseau, une présentation des objets réseaux, partitions et vecteurs tels qu’ils doivent être manipulés et mis en forme dans Pajek. On y trouve une description des différentes opérations de type « network+partition » à savoir: extraction d’un sous-graphe, réduction d’un graphe en graphe image, création d’une vue contextuelle.

Pour finir une manipulation est proposée sur un sous-graphe du réseau « world.trade » (lequel est téléchargeable depuis le lien suivant: http://vlado.fmf.uni-lj.si/pub/networks/data/esna/metalWT.htm). A l’issue de cette manipulation, une représentation du réseau européen de commerce est exportée en format vectoriel (svg), chargée et retravaillée dans le logiciel Inkscape afin d’enrichir le contenu et la valeur de la représentation. En particulier, pour en améliorer la lisibilité: on montre qu’il convient d’y ajouter un titre et une légende.

Atelier Pajek Ferney 2014

Le projet Coscimo, de (géo)visualisation des collaborations scientifiques mondiales

Le projet Coscimo, de (géo)visualisation des collaborations scientifiques mondiales est une application en ligne (http://www.coscimo.net/) permettant de visualiser à l’aide de différents modes de représentation, les résultats issus du projet ANR Géosciences de l’UMR LISST, à Toulouse. En Octobre 2013, ce projet présenté par Laurent Jégou et Marion Maisonobe, a remporté le troisième prix du concours de géovisualisation et cartographies dynamiques du festival international de géographie de Saint-Dié-des-Vosges (FIG 2013).

Divers modes d’exploration interactive des données relationnelles sont proposés et l’exploration des données est disponible à plusieurs échelles spatiales (villes, pays, continents) et sur plusieurs périodes (1999-2001 et 2006-2008).

Quatre modes de représentation sont retenus, pour le même ensemble de données : il s’agit de la représentation matricielle, des diagrammes de chord et  lien-noeuds et de la carte de flux. Les commentaires qui accompagnent l’utilisateur montrent que les résultats remarquables varient d’un mode de représentation à un autre ; ces derniers étant par ailleurs plus complémentaires qu’antagonistes.

Après avoir géolocalisé un corpus impressionnant de publications scientifiques (plus de 8 millions de notices bibliométriques indexées dans le Web of Science, une base de donnée privée détenue par Thomson Reuters), l’équipe travaille à explorer, exploiter et valoriser les résultats de la spatialisation des données de la production scientifique mondiale. Le site internet de Coscimo est donc amené à évoluer. Il permettra, entre autres nouveautés, d’approfondir l’exploration du corpus de données de collaboration. Sur le plan technique, il s’agira, par exemple, de laisser l’utilisateur choisir la part d’information qu’il souhaite visualiser, en sélectionnant, par exemple, l’échantillon de villes dont il veut observer les relations pour la représentation sous la forme de diagramme de chord.

Les chantiers en cours comprennent un travail lié au découpage des données par disciplines, ainsi que leur mise à jour, afin d’étendre la période temporelle d’observation.

A noter que l’équipe de Coscimo œuvre à présent dans le cadre du projet Netscience de l’opération Mondes Scientifiques du Labex Structuration des Modes Sociaux (Labex SMS).

Je remercie Françoise Bahoken d’avoir co-écrit ce billet avec moi.

 

Un tutoriel pour faire des cartes de flux avec Qgis

Notre collègue cartographe et géomaticien Laurent Jégou vient de mettre en ligne un tutoriel bien pratique pour réaliser des cartes de flux avec le logiciel SIG libre Qgis: http://portailsig.org/content/qgis-concevoir-une-jolie-carte-de-flux

Le secret c’est d’utiliser la fonction « Hub Lines » du plugin Mmqgis (http://michaelminn.com/linux/mmqgis/) à partir d’une couche (shp) de points origines et une couche de points destinations.

Laurent Jégou complète son explication par une astuce pour rendre les lignes courbes. Un exemple de résultat obtenu avec les données Géoscience (UMR LISST, Université de Toulouse 2), la carte des collaborations internationales de Toulouse en 2008:

toulouse_collab

 

 

 

EgoNet et Vennmaker : logiciels d’analyse de réseaux personnels

Un billet sur les réseaux personnels ou ego-network pour changer un peu. Qu’on se le dise, l’analyse de réseau n’est pas réservée aux fouilleurs de big data. Elle se prête très bien à une démarche de recherche plus qualitative. Les logiciels EgoNet et VennMaker, respectivement développés par des sociologues et des historiens, en témoignent.

Ces logiciels présentent la particularité d’associer un module permettant de générer un questionnaire ou guide d’entretien à un module de représentation et d’analyse de graphe. Bien que la partie analyse de graphe reste limitée, rien n’empêche l’utilisateur d’exporter le graphe de sortie et d’approfondir l’analyse avec des logiciels plus spécialisés (évoqués dans les autres billets du groupe fmr).

Les deux logiciels ne sont pas équivalents. L’utilisation d’EgoNet exige plus de rigueur que celle de VennMaker. Les deux logiciels permettent de construire un questionnaire dont les étapes sont bien balisées: le générateur de nom (« Citez-moi les personnes de votre entourage qui répondent à tel ou tel critère ») ; la qualification des relations entre un ego et ses alters (« Quelle est la nature de la relation que vous entretenez avec chacune de ces personnes ? ») ; la qualification des relations entre alters (« Quelle est la nature de la relation que ces personnes entretiennent entre elles ? »).

Ci-dessous, une capture d’écran de la partie entretien du logiciel Egonet :

Capture d'écran Egonet

Une fois le questionnaire généré, il est prévu que vous le complétiez, en direct, pendant l’entretien. Avec les réponses enregistrées, les logiciels génèrent le graphe du réseau personnel de la personne interrogée. Vous pouvez alors, le lui montrer, faire quelques traitements (calculs des indices de centralité basiques sur EgoNet) et en discuter avec elle.

Si c’est cette démarche qui vous intéresse, nous vous conseillons d’avoir plutôt recours à EgoNet car c’est l’interface qui s’y prête le mieux. En effet, la particularité de VennMaker est de permettre à son utilisateur d’intervenir directement sur le graphe sans qu’il y ait besoin du questionnaire. Contrairement à EgoNet, VennMaker permet de dessiner, littéralement, le réseau tout en réalisant l’entretien.

La souplesse de VennMaker est intéressante, à notre sens, s’il s’agit moins de réaliser un questionnaire qu’un entretien semi-directif. Les options de dessins sont originales pour, par exemple, rendre compte d’attributs multiples : on peut faire varier la forme et la couleur des nœuds et il est possible de les placer sur un cadran (en toile de fond) ce qui permet, éventuellement, d’indiquer leur localisation géographique.

Ci-dessous, une capture d’écran de l’interface graphique de VennMaker :

Capture d'écran VennMaker

Avec EgoNet, ce sont uniquement les réponses obtenues par le biais du questionnaire qui définissent le graphe. Cela permet d’éviter les erreurs d’interprétation du résultat a posteriori. En effet, le gros défaut de VennMaker est de permettre à l’utilisateur de modifier la configuration du graphe obtenu par le biais de l’entretien, après que celui-ci ait été réalisé. Le risque est alors important de ne plus pouvoir s’y retrouver. Un autre point positif en faveur d’Egonet : il est gratuit et libre ce qui n’est pas le cas de VennMaker (pour autant, une version d’essai gratuite est disponible en ligne). Les deux logiciels évoluent régulièrement pour pallier aux défauts rencontrés par les utilisateurs.

En conclusion, voici deux logiciels originaux pour les tenants d’une approche aux frontières du qualitatif et du quantitatif. Je remercie Ainhoa de Federico d’avoir organisé les deux ateliers méthodologiques qui m’ont permis de découvrir ces logiciels. Ces ateliers ont été organisés dans le cadre du Labex SMS (Structuration des Mondes Sociaux) à l’Université de Toulouse – Le Mirail. Le prochain atelier méthodologique aura lieu le 12 juin 2012 de 16 à 19h à la Maison de la Recherche (UTM).  Cette fois-ci, Juergen Lerner de l’Université de Konstanz viendra présenter le logiciel Visone (logiciel déjà évoqué sur ce blog).

Site du logiciel Egonet : http://sourceforge.net/projects/egonet/
Site du logiciel VennMaker : http://www.vennmaker.com/en/

La détection de communautés avec Pajek 3.6

La toute nouvelle version de Pajek réserve de bonnes surprises aux explorateurs de graphes complexes.

Les nouveautés dont il est question ici ont été ajoutées au logiciel entre Mai 2012 et Septembre 2012.

Deux algorithmes de détection de communautés ont été implémentés:

Network/Create Partition/Communities

-Louvain method

Le premier algorithme s’appuie sur la méthode de Louvain [1]. Cette méthode est bien adaptée aux graphes valués, y compris s’ils sont signés. Comme pour beaucoup d’algorithmes de clustering (ou détection de communautés), la qualité du partitionnement est optimisée par maximisation de la fonction de modularité [2].  L’indice de modularité mesure la différence entre la densité d’un graphe (ou sous-graphe) donné et la densité d’un graphe aléatoire possédant les même caractéristiques (nombre et poids des liens).

Principe

Maximiser la fonction de modularité pour partitionner un graphe revient à s’assurer que le nombre et le poids des liens est plus important à l’intérieur des partitions qu’entre les partitions. Pour l’exprimer autrement, il faut que la densité intra-communautaire dépasse la densité inter-communautaire.

La méthode de Louvain est « bottom-up » et multi-niveau. Au lancement de l’algorithme, tous les sommets appartiennent à une partition différente. Ils sont regroupés, par itération, dans des partitions de modularité optimale. Arrivé à une première situation d’optimum, le processus se poursuit au niveau supérieur : chaque partition est traitée comme un sommet et ainsi de suite. L’opération continue jusqu’à ce qu’il n’y ait plus aucun gain de modularité possible.

Avantage

Cette approche permet d’échapper au défaut de la modularité connu sous le nom de « limite de résolution » [3]. Si le fait d’associer une partition du premier niveau avec une autre devait engendrer une perte de modularité, cette association ne serait pas réalisée par la méthode de Louvain. De ce fait, les petites structures dotées d’une bonne modularité ne risquent pas d’être noyées dans des structures plus grandes et moins significatives. C’est ce qu’il risquerait d’arriver avec un algorithme « top-down » appliqué à un trop grand graphe.

Inconvénient

Le défaut connu de la méthode provient de la sensibilité du résultat à l’ordre de traitement des sommets. L’ordre dans lequel les sommets sont considérés a une influence sur le partitionnement. De ce fait, il peut être utile de procéder à des permutations pour s’assurer de la robustesse du résultat [4]. L’autre piste est d’imposer un ordre qui tienne compte des caractéristiques du réseau [5].

En plus de l’algorithme classique de Louvain,  Pajek propose une variante (avec rafinement multi-niveau) qui tend à donner de meilleurs résultats pour les grands graphes [6]. La méthode de Louvain est également disponible dans les logiciels Gephi et NetworkX ainsi que dans la librairie igraph du logiciel R, l’algorithme étant plus rapide sur Pajek que sur Gephi.

-VOS Clustering

La méthode de détection de communauté VOS optimise une autre fonction de qualité que la fonction de modularité: la fonction dite de VOS clustering [7]. Il s’agit d’une variante pondérée de la modularité qui a été pensée pour le traitement des données bibliométriques. Cette technique donne moins de poids qu’une méthode classique aux sommets à très haut degré. Contrairement à la méthode de Louvain, elle dépend d’un algorithme « « top-down« . Pour cette raison, le seul moyen d’échapper au problème de limite de la résolution consiste à faire varier le paramètre de résolution.

Cette méthode convient en fait aux graphes pour lesquels la valeur des liens rend compte de l’importance de la similarité entre les sommets. Ses concepteurs ont souhaité que soit associé à l’algorithme de clustering un algorithme de visualisation faisant appel au même principe mathématique. Cette approche unifiée permet d’éviter qu’ils y ait des incohérences entre le résultat du processus de clustering et la représentation graphique de ce résultat.

Tout naturellement, Pajek propose aussi l’algorithme de visualisation VOS. Il fonctionne sur le principe de l’optimisation de la fonction de qualité dite de VOS mapping. Étant donné la proximité des deux méthodes de détection, il n’est surement pas impensable d’utiliser le VOS mapping pour représenter un graphe partitionné suivant la méthode de Louvain.

Aller plus loin

Une comparaison des deux méthodes de détection est accessible sur: http://mrvar.fdv.uni-lj.si/pajek/community/LouvainVOS.htm

Des précisions sur l’utilisation de ces méthodes avec Pajek se trouvent aussi sur le site: paramétrage, évaluation de la qualité du partitionnement, représentation graphique du résultat.

Depuis l’interface graphique de Pajek, un raccourci vers le logiciel VOSviewer offre la possibilité d’obtenir rapidement une représentation  élégante du partitionnement.

Ci-dessous, un exemple à partir des données de collaborations scientifiques néerlandaises (Source: Web of Science 2006-2008):

Références
[1] V. Blondel, J.-L. Guillaume, R. Lambiotte, et E. Lefebvre, « Fast unfolding of communities in large networks », Journal of Statistical Mechanics, vol. 2008, no 10, sept. 2008.
[2] Il existe de nombreuses autres méthodes de détection de communautés. Pour avoir un aperçu de l’existant: S. Fortunato, « Community detections in graphs », Physics and Society, vol. 2010, no 486, p. 75-174.
[3] S. Fortunato et M. Barthélemy, « Resolution limit in community detection », Proceedings of the National Academy of Sciences of the United States of America, vol. 104, no 1, p. 36-41, janv. 2007.
[4] V. Blondel, G. Krings, et I. Thomas, « Régions et frontières de téléphonie mobile en Belgique et dans l’aire métropolitaine bruxelloise », Brussels studies, no 42, oct. 2010.
[5] P. De Meo, E. Ferrara, G. Fiumara, et A. Provetti, « Generalized Louvain method for community detection in large networks », under review, 2011. URL: http://www.emilio.ferrara.name/wp-content/uploads/2011/07/isda2011-k-path.pdf
[6] R. Rotta et A. Noack, « Multilevel local search algorithms for modularity clustering », Journal of Experimental Algorithmics, vol. 16, no 2.3, 2011.
[7] L. Waltman, N. J. van Eck, et E. C. M. Noyons, « A unified approach to mapping and clustering of bibliometric networks », Journal of Infometrics, vol. 4, no 4, p. 629-635, oct. 2010.

 

L’actualité réseau en Ile-de-France

Ce mois-ci,  on note une actualité chargée en l’Ile-de-France.

Les spécialistes des approches mathématiques et informatique des réseaux se réuniront à Villetaneuse (LIPN – Université Paris 13) les 17 et 18 Octobre 2012 à l’occasion de la troisième conférence sur les Modèles et l’Analyse des Réseaux. A l’affiche: Alain Barrat (Marseille), Vincent Blondel (Louvain) et Eric Gaussier (Grenoble). Le programme et les inscriptions sont accessibles sur le site : http://lipn.fr/marami12

Quelques jours plus tard, les 22 et 23 octobre, l’Institut Européen d’Administration des Affaires (INSEAD) organise la troisième conférence sur l’évolution des réseaux. Cette fois-ci, c’est une approche organisationnelle des réseaux sociaux qui sera privilégiée. Sociologues américains et canadiens assureront le show (en anglais évidemment!) à Fontainebleau (Joel Baum (Toronto), Ron Burt (Chicago) et David Stark (Columbia)). Les informations sont disponibles sur le site: http://www.insead.edu/facultyresearch/faculty/personal/ashipilov/network12.cfm.

Enfin, la prochaine séance du séminaire Complex networks accueillera Franck Delaplace, bioinformaticien, le 18 octobre à Paris 6 (http://www.complexnetworks.fr/events/).