Comment cartographier des données relationnelles et les analyser à l’aide de l’extension Network_Analysis ?

Ce tutoriel a été créé à l’occasion de l’école d’été thématique en analyse de réseaux organisée à Cargèse par le GDR AR-SHS. Elle s’est tenue entre le 24 et le 28 septembre 2018 dans des conditions climatiques miraculeuses.

Demandant d’utiliser la toute dernière version 3.2 de QGIS, cet atelier pratique sur les données spatiales a provoqué une petite mise à jour de l’extension Network_Analysis de Serge Lhomme, déjà présentée à plusieurs reprises sur ce blog.

Nous demanderons donc à celles et ceux qui l’avaient déjà installée sur QGIS 3, de la désinstaller, de la re-télécharger sur le site internet : http://serge.lhomme.pagesperso-orange.fr/dev.html , puis de la réinstaller en suivant les indications ci-dessous.

Pour rappel, l’extension Network Analysis est une extension développée par Serge Lhomme, maître de conférence à l’Université Paris-Est Créteil. Il s’agit d’un outil facile d’utilisation permettant d’effectuer de l’analyse de réseaux sous QGIS, logiciel de Système d’Information Géographique (SIG) libre et gratuit. En effet, dans les SIG, les outils permettant d’analyser les propriétés structurelles de réseaux spatiaux ne sont pas si nombreux.

Installation de l’extension

Marche à suivre

Lancer Qgis

Aller dans le menu Extension -> Installer/Gérer les extensions

Aller dans la section « Installées » et désinstaller le plugin « Network_analysis » s’il apparaît dans la liste des extensions déjà installées

Aller rechercher le plugin « network_analysis_2_1 » sur le site : http://serge.lhomme.pagesperso-orange.fr/dev.html

Retourner dans Qgis au menu Extension -> Installer/Gérer les extensions

Sélectionner « Installer depuis un ZIP » et charger le fichier ZIP que vous venez juste de télécharger « network_analysis ».

Exemple de données relationnelles: les collaborations scientifiques entre villes françaises

Ce tutoriel s’appuie sur des données de recherche permettant de cartographier le réseau français des collaborations scientifiques en chimie. Ces données sont le résultat d’un travail de codage des données de publications scientifiques contenues dans une base de données bibliographique de référence pour les chimistes: le Web of Science.

Deux fichiers sont nécessaires, un fichier précisant la localisation des villes d’où ont été signées des publications scientifiques en chimie entre 2008 et 2012, et un fichier de lien indiquant la fréquence des collaborations entre ces villes mesurées par les co-signatures (le fait qu’une publication soit signée depuis plusieurs lieux différents).

Un fond de carte des régions françaises est également rendu disponible.

Ces fichiers sont téléchargeables depuis le dépôt suivant : https://framagit.org/MarionMai/using-network_analysis-on-qgis-3

Charger les données relationnelles

Marche à suivre

Aller dans le menu Couche -> Ajouter une couche -> Ajouter une couche de texte délimité

Sélectionner le fichier « Point_chimie_France.csv »

Sélectionner le délimiteur « ; »

Dans la section « géométrie », sélectionner « point » et indiquer dans quelles colonnes se trouvent les coordonnées géographiques du fichier (X, Y pour Longitude, Latitude) : soit les colonnes « V2 » et « V3 »

Sélectionner « WGS 84 » comme système de référence spatial puis cliquer sur « Ajouter »

Recommencer l’opération pour charger le fichier de liens appelé « liens_chimie_France.csv »

Ce fichier n’a pas de géométrie (de coordonnées spatiales X,Y). Dans la section « Définition de la géométrie », il faut donc sélectionner « pas de géométrie »

La spatialisation de ce fichier se fera grâce aux informations relationnelles qu’il contient puisqu’on y précise quels sont les points ─ en l’occurrence, les entités urbaines ─ qui sont reliées ensemble :

La colonne V1 indique le point de départ des liens

La colonne V2 indique leur point de destination

Et la colonne V3, l’intensité des liens

À l’aide du package « Network_Analysis », ces trois informations vont suffire à créer une couche spatialisée de liens.Générer une couche spatialisée de liens

Marche à suivre

Pour cela, aller dans le menu Extension -> Network Analysis -> Tools

Sélectionner « Table to graph » qui permet de passer d’une table de liens à un graphe

Sélectionner le nom de la couche de points dans la section « Nodes layer » et sélectionner le nom du fichier de liens dans la section « Edges layer ».Cliquer sur OK

Renseigner la boîte de dialogue en indiquant dans :

– Node ID, le nom de la colonne de la couche de points où sont indiqués les identifiants uniques (sans doublons) des points (qui peuvent être numérique ou textuels) – ici V1

– Field X, le nom de la colonne de la couche de points où est indiquée la longitude des villes – ici V2

– Field Y, le nom de la colonne de la couche de points où est indiquée la latitude des villes – ici V3

– Start Field, le nom de la colonne du fichier de liens où est indiquée l’ID de départ des liens (nom de la ville de départ) – ici V1

– End Field, le nom de la colonne du fichier de liens où est indiquée l’ID de destination des liens (nom de la ville d’arrivée) – ici V2

-EPSG, le nom ou code du système de référencement spatial utilisé, ici « 4326 » comme indiqué sur le bas droit de l’écran. Ce code correspond au système de référencement « WGS 84 » qui correspond au système du GPS.

Cliquer sur OK

Modifier la projection géographique

Marche à suivre

Aller dans Projet->Propriétés du projet

Sélectionner la section « SCR », taper « lambert 93 » (système de projection adapté au territoire français) dans la barre de recherche, sélectionner « RGF_1993_Lambert_93 » et cliquer sur « Appliquer »Sauvegarder les couches « Edges » et « Nodes » avec la projection adaptée

Marche à suivre

Faire un clic droit sur chacune des couches, choisir Exporter et Sauver

Indiquer format « GeoJSON », choisir le répertoire et le nom à donner au fichier (par exemple « Edges.geojson » pour la couche Edges et « Nodes.geojson » pour la couche Nodes

Sélectionner le « SCR du projet » dans la section SCR soit « Lambert 93 »

Cliquer sur OK

Supprimer les couches Edges et Nodes précédentes (clic droit sur la couche-> supprimer la couche)

Glisser déplacer la nouvelle couche « Edges » en dessous de la nouvelle couche « Nodes »

Modifier la couleur des liens selon l’intensité des collaborations

Marche à suivre

Faire un clic droit sur la couche Edges et sélectionner « Propriétés » puis « Symbologie »

Sélectionner « Gradué » dans le menu déroulant se trouvant en haut de la fenêtre de dialogue

Dans Colonne, sélectionner le nom de la variable contenant la valeur associée à l’intensité des collaborations scientifiques, en l’occurrence V3

Dans Palette de Couleur, sélectionner le dégradé de vert

Dans Mode, sélectionner le mode de discrétisation de Jenks

Décocher, la première valeur de classe [de 0 à 13,5] pour que ne s’affichent que les liens de collaborations d’une valeur supérieure à 13,5

Pour information -> les valeurs de collaboration sont décimales car fractionnées en fonction du nombre d’agglomérations urbaines d’où ont été signées les publications scientifiques en chimie. Pour en savoir plus sur cette méthodologie, se référer au site internet du projet de recherche : http://geoscimo.univ-tlse2.fr/

Cliquer sur Appliquer puis sur OK

Calculer le degré des nœuds

Marche à suivre

Commencer par modifier les ID des champs en utilisant l’option « Correct ID » de l’extension Network Analysis

Pour cela Aller à Extension->Network Analysis->Tools->Correct ID

Sélectionner « Nodes » dans Nodes layer et « Edges » dans Edge layer

Sélectionner les colonnes où se trouvent les identifiants uniques de la couche « Nodes » et de la couche « Edges », en l’occurrence V1 dans la couche « Nodes », et V1 et V2 dans la couche « Edges ».

Aller à Extension-> Network Analysis-> Basic Analysis

Sélectionner « Nodes » dans Nodes layer et « Edges » dans Edge layer

Choisir « Nodes » dans la fenêtre permettant d’indiquer que l’on souhaite calculer un indicateur portant sur les nœuds plutôt que sur les liens

Indiquer dans la fenêtre de dialogue, les colonnes correspondant aux nouveaux identifiants de la couche « Edges » à savoir « StartNode » et « EndNode »

Choisir « No » dans Normalization pour que l’indicateur de degré ne soit pas normalisé.Pour consulter le résultat, effectuer un clic droit sur la couche « Nodes » et ouvrir la table des attributs

Le résultat apparaît dans une nouvelle colonne intitulée « Degree »

Faire varier la taille des nœuds en fonction de leur degré

Marche à suivre

Effectuer un clic droit sur la couche « Nodes »

Aller dans Propriétés puis Symbologie

Choisir comme couleur de nœud un vert par défaut – code rgb(51, 160, 44)

Cliquer sur l’icône se trouvant à droite de l’indice de « Taille » du symbole (ci-dessous en rouge)

Aller dans Assistant, sélectionner le nom de la variable où est stocké le Degré, soit « Degree »

Indiquer l’intervalle entre lequel se situe les valeurs de l’indicateur, en l’occurrence 1 et 119 (comme on l’observe en consultant la table attributaire)

Choisir de faire varier la taille des nœuds entre une taille de 1 à 5

Choisir de faire varier la surface des cercles (méthode de calcul : Surface)

Ajouter un fond de carte de la France

Marche à suivre

Pour finir, charger le fichier shapefile « FRA_adm1.shp » en allant dans :

Ajouter une couche->Ajouter une couche vecteur

Sélectionner le fichier « FRA_adm1.shp » dans la section « Source » de la boîte de dialogue

Cliquer déplacer la nouvelle couche en dessous des couches « Nodes » et « Edges »

Changer la couleur de la couche en faisant un clic droit sur le nom de la couche puis choisir une couleur légère comme par exemple la couleur correspondant au code html #fdf0c1

Une fois satisfait du résultat obtenu, vous pouvez mettre en page, ajouter une légende et un titre en allant dans le composeur d’impression :  Projet->Composeur d’Impression (ou en anglais : Layout Manager)

Pour en savoir plus sur l’utilisation du composeur d’impression, consulter par exemple :

http://www.qgistutorials.com/fr/docs/automating_map_creation.html

Pour toutes questions ou problèmes regardant l’utilisation de l’extension Network Analysis, vous pouvez vous adresser à serge.lhomme@u-pec.fr

Et pour suivre les mises à jour, consulter son site : http://serge.lhomme.pagesperso-orange.fr/index.html

Bonne chance !

1ere séance du cycle de formation à l’analyse de réseaux avec R

La première séance du cycle de formation à l’analyse de réseaux avec R s’est tenue le 24 octobre 2017 à Paris (bâtiment Olympe de Gouges).

La séance était organisée en deux partie. En première partie, une introduction à l’analyse de réseaux a été proposée. Elle revient sur le vocabulaire de la théorie des graphes, montre plusieurs champs d’application dans le domaine de l’analyse des réseaux spatiaux et sociaux et décrit les principales approches  (calculs d’indicateurs locaux, globaux, visualisation, partitionnement, modélisation).

Le diaporama suivant a servi de support pour cette présentation:

 

La seconde partie de la séance était consacrée à la manipulation avec R Studio. L’interface de travail ainsi que les rudiments du langage R ont été présentés puis, pour débuter avec le package igraph, nous nous sommes appuyés sur les supports de cours développés par Rosemonde Letricot en juin 2017 pour l’école d’été d’initiation à l’analyse de réseaux en sciences humaines et sociales organisée par le GDR AR-SHS qui sont téléchargeables au lien suivant:
https://arshs.hypotheses.org/480

Les scripts et données utilisés lors de la séance sont disponibles ici.

La prochaine séance, le 21 novembre 2017, permettra d’aller plus loin dans la manipulation et apprendra à conduire une analyse de réseaux en calculant des indicateurs locaux sur les sommets et sur les liens. Les différents moyens de visualiser les résultats obtenus seront présentés en détail (visualisation de réseaux permettant de faire varier la taille des cercles et des liens, distribution de degrés etc.).

Les inscriptions sont ouvertes. Il suffit d’indiquer votre intérêt pour la formation par mail à l’adresse de Ryma Hachi (hachiryma<a>gmail.com).

La formation se tiendra au même endroit que précédemment de 10h à 12h: Bâtiment Olympe de Gouges, 8 Place Paul-Ricoeur, Paris

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/).