L’analyse des réseaux personnels avec E-Net

logo du logiciel E-Net

E-Net est un logiciel développé par Borgatti depuis 2006 et dédié à l’analyse des réseaux personnels (ego-networks). Pour mémoire, un réseau personnel est classiquement défini ainsi : un acteur a, l’ensemble des acteurs auxquels cet acteur a est directement connecté (les alters) et l’ensemble des liens entre ces acteurs. Logiciel gratuit mais non libre, il fonctionne sous environnement Windows et la version 0.41 testée ici date du 29 septembre dernier.

 Le logiciel permet l’analyse de réseaux personnels stricto sensu ou l’analyse des ego-networks d’un réseau standard. Deux formats d’importation sont possibles dans le premier cas :

  • des formats texte ayant l’extension .vna
  • des fichiers .xls

La structure des fichiers .vna rappelle un peu celle des fichiers Pajek avec la liste des egos et leurs attributs, la liste des liens entre egos et alters et les attributs de ces derniers, et enfin les liens entre alters. Le petit exemple ci-dessous, extrait de la documentation, donne un exemple de structure des données.

*ego data
ID age    sex
01    32  male
02    67  female
03    ….
*alter data
From    To Friends Age
01    1-1    1     15
01    1-2    1     30
02    2-1    0     50

*Alter-alter data
From    to    knows
1-1    1-2    1

S’il s’agit d’un fichier excel, les données comprennent une ligne par ego et doivent être structurées ainsi :

Identifiant de l’ego 1, caractéristique 1, caract. 2…, Alter 1, caract. 1 de l’alter 1, caract. 2 de l’alter 1…

Deux fichiers d’exemple permettent de comprendre la logique de structuration des données et de se l’approprier rapidement.

Si le logiciel est utilisé pour étudier des ego-networks dans un réseau standard, ce dernier doit être au format Ucinet. Pour mémoire, dans Ucinet, il suffit de copier-coller une matrice depuis un tableur et de l’enregistrer en .net.

La fenêtre principale consiste en une poignée de menus déroulants et de fenêtres.

fenêtre principale E-Net

L’onglet Egos fait apparaître l’ensemble des egos et leurs attributs. Une fenêtre située à droite de l’écran permet de filtrer les Egos de façon très intuitive : si je veux n’étudier que les Egos dont le genre est 1, je tape genre = 1 puis Filter. La logique est la même pour les onglets Alters et Alters-Alters Ties.

Le menu Analyze permet notamment l’étude des alters en fonction d’attributs (table de contingence et test du chi2 avec Crosstabs), d’étudier les fréquences de liens ou de rechercher des trous structuraux. Si les alters possèdent des caractéristiques sous forme de variable continue (âge, revenu…), le logiciel calcule minimum et maximum, moyenne, écart-type et somme des modalités. Le menu Analyse > Heterogeneity permet le calcul de deux indices relatifs aux variables catégorielles, l’indice de Blau et l’indice d’Agresti. Les deux indices varient de 0 à 1 : 0 en cas d’homogénéité totale (ex. je suis une femme et toutes mes relations sont des femmes), 1 en cas d’hétérogénéité totale.

Menu Analyze d'E-Net

La visualisation propose peu d’algorithmes, ce qui est logique pour des ego-networks. Il est possible de faire défiler l’ensemble des sommets et leurs réseaux personnels respectifs à l’aide des flèches situées sur la droite de la fenêtre.

fenetre de visualisation E-Net

Si l’importation des données est aisée, l’exportation des résultats est on ne peut plus simple : il suffit de cliquer sur l’icône xls… et les résultats s’ouvrent aussitôt dans un fichier .xls

L’outil reste perfectible, notamment en ce qui concerne la rubrique d’aide : le format des données à importer est très clairement expliqué, mais cliquer sur la rubrique d’aide fait apparaître la fenêtre suivante :

rubrique d'aide du logiciel E-Net

Volontaire pour écrire l’aide d’un logiciel non libre disponible uniquement sous Windows ? C’est sûrement de l’humour californien… Blague à part, ne travaillant pas spécifiquement sur des réseaux personnels, je ne suis guère capable d’évaluer les manques du logiciel, n’hésitez donc pas à faire part de vos expériences.

 

Références

Site d’E-Net : https://sites.google.com/site/enetsoftware1/Home

Borgatti SP. 2006. E-Network Software for Ego-Network Analysis. Analytic Technologies: Lexington, KY.

Halgin D.S. et Borgatti S.P. 2012. An introduction to personal network analysis with E-Net, Connections, 31(1): 37 – 48.

Où l’on visualise le graphe de ce qu’on nous recommande (sur Amazon©, YouTube©, etc.)

Nous avons pratiquement tous effectué au moins une recherche d’ouvrage – ou de produit quelconque – sur le site de Amazon© et consulté, à l’occasion, la liste des  « recommandations ». Au sens de Amazon, les  « recommandations » sont une liste d’ouvrages (d’auteurs, de produits, etc.) associés à celui qui fait l’objet de votre recherche. Elle est donc susceptibles de vous intéresser car elle vous renseigne sur des ouvrages du même auteur ;  des  ouvrages d’auteurs différents sur un sujet similaires ; des produits liés au thème de votre recherche, etc.)  qui ont été recherchés – avant vous – par d’autres utilisateurs du site. De ce fait, l’ouvrage qui vous intéresse est, par conséquent, mis en relation à d’autres ouvrages par le principe des recommandations. Il est donc possible de visualiser le graphe de ces recommandations.

Christopher Warnow est parti de ce principe de mise en relation des produits de Amazon pour concevoir une application de visualisation du graphe des recommandations liées à un ouvrage recherché sur le site. L’auteur précise que l’idée lui est venue suite à la lecture du Chapitre 7 « Your choices reveal who you are » de Valdis Krebs (de l’ouvrage de J. Steele : Beautiful Vizualization).

L’application Warnow génère donc un graphe de recommandations à partir d’un « produit » Amazon : les noeuds correspondent aux produits recommandés par d’autres utilisateurs, accessoirement vendus sur le site et les liens à l’existence d’une recommandation. La représentation graphique s’appuie sur  Gephi pour la visualisation des « communautés ».  Les résultats peuvent être exportées en .pdf ou, bien sûr, capturés sur écran. Quelques illustrations sont disponibles sur Flickr.

Nous avons souhaité tester cette application Warnow directement sur Amazon©. Pour ce faire, nous avons utilisé Yasiv la variante développée par Andrei Kashcha (2012).  Le résultat de la recherche d’ouvrages, à partir du mot-clé « Jacques Bertin »  a été réalisée sur les sites canadiens, américain et français de Amazon©. Dans les trois cas, l’ouvrage associé à cette recherche d’auteur est « Sémiologie graphique » (1967), ce qui n’est pas surprenant.

Les résultats obtenus sont les suivants :

– Sur le site canadien : 28 références sont recommandées pour la version anglaise de l’ouvrage ;
– Sur le site américain : 50 références sont recommandées pour la version anglaise de l’ouvrage ;
– Sur le site français : 97 références sont recommandées pour la version française de l’ouvrage Sémiologie graphique, les diagrammes, les réseaux et les cartes.

Figure 1. Résultats obtenus sur Amazon.com (USA)

 

 

Figure 2. Résultats obtenus sur Amazon.fr (France)

On observe sur le graphe des recommandations issues du site français (Figure 2) que les références à « Jacques Bertin » sont plus variées que sur le site américain (Figure 1). Pour preuve, cette référence à l’ouvrage Danses tracées (Louppe & al., 1991) sur le dessin des trajectoires de danseurs par des chorégraphes. Ou encore, plus étonnant, la recommandation d’un pointeur laser vert Ecran LCD de portée de 30 m et de couleur noire. Cette dernière connexion est indirecte (degré 3) : le pointeur est, en effet, lié (degré 1) à un ouvrage sur l’art des présentations sous Powerpoint© qui, lui-même est lié (degré 2) à un ouvrage sur l’Art de convaincre avec des graphiques efficaces réalisés à l’aide des produits Microsoft Office© qui est, lui (degré 3), directement lié à Jacques Bertin (!). Il faut préciser que les différentes recommandations appartiennent à des groupes cohérents, ce qui témoigne de l’influence de l’auteur dont il est question ici.

Nous avons voulu aller plus loin dans ces associations inédites et avons donc relancé la recherche « Jacques Bertin » dans l’ensemble des départements du site. Le résultat obtenu est, non plus focalisé sur des produits liés au graphisme et à la graphique mais plutôt sur trois artistes – que nous ne connaissions pas – qui lui sont homonymes. Et l’idée nous est venue de rechercher des vidéos des dits artistes sur YouTube. Et là, surprise ! L’application Yasiv fonctionne également.

… vers YouTube et LinkedIn

La recherche « Jacques Bertin » avec Yasiv pour YouTube©, accessible ici, propose le graphe des vidéos liées aux auteurs concernés avec deux variantes par rapport au site de Amazon : la taille des vignettes des vidéos est proportionnelle au nombre de citations et elles sont accompagnées d’un nombre de Like et Dislike. L’application propose, par ailleurs, de filtrer les vidéos selon qu’elles sont likées ou dislikées.

Dans le même ordre d’idée et sans prendre le temps de la présenter, nous signalons l’application InMap du réseau professionnel LinkedIn(c) qui permet de visualiser son propre graphe de relations. Un billet est disponible ici.

Au final, une application totalement interactive et plutôt intéressante car elle permet de découvrir des ouvrages en lien avec notre recherche.

Figure 3. Popularité des ouvrages du graphe
des recommandations (sites américains et français)

Le résultat propose, en outre, des informations complémentaires :

– sur la gauche de l’écran, les autres ouvrages recommandés les plus « populaires » en nombre de recommandations (voir figure 3 ci-après) ;

– sur la droite de l’écran, toutes les informations disponibles sur l’ouvrage recherché (prix, références, commentaires, etc.) telles qu’elles sont actuellement présentées sur le site Amazon.

 

 

 

 

Références : 

Le code source de l’application Warnow est disponible ici (attention : fichier de 60 Mo).

Pour Yasiv(c), la version pour une visualisation en ligne des recommandations d’Amazon :  c’est par ici et de YouTube, c’est par

Louppe, L., Dobbels, D., Virilio, P., Thom, R., Laurenti, J-N., 1991, Danses tracées : dessins et notations de chorégraphes, Editions Dis Voir, 60 p.

Steele, J., Iliinsky N.,2010, Beautiful Visualization, O’Reilly Media, Inc. 416 p.

Françoise Bahoken

Géographe et cartographe, Chargée de recherches à l'IFSTTAR et membre-associée de l'UMR 8504 Géographie-Cités.

More Posts

Enfin de beaux graphes avec R ? Le package qgraph à l’essai

Je l’ai déjà écrit, R me paraît être aujourd’hui le logiciel le plus performant en analyse de réseau, et ce quel que soit le type de réseau étudié. Reste que lorsqu’il s’agit de passer de l’exploration des données à la communication, les graphes produits par R ne font pas le poids face aux visualisations générées par des outils comme Cytoscape, Gephi ou Tulip. Est-ce que l’arrivée du récent package qgraph change les données du problème ? Pas sûr…

Développé par de psychologues, l’objectif du package qgraph est de permettre des visualisations lisibles de graphes denses tout en minimisant la taille des fichiers vectoriels exportables. Si l’objectif premier affiché par les auteurs est la visualisation de matrices de corrélation, il est évidemment possible de l’utiliser pour représenter un graphe simple valué.

Le nombre de commandes est on ne peut plus limité : qgraph est la seule du module. Comme l’expliquent les auteurs dans le Journal of Statistical Softwares, le nombre de packages permettant l’analyse de graphes est largement suffisant – et ils n’ont pas tort. Pourtant, le package permet d’obtenir les mesures de graphe valué proposés par Tore Opshal dans ses articles, sur son blog (dont la visite est très recommandée : http://toreopsahl.com/) et… dans son package tnet.

Si on teste les scripts d’exemple du mode d’emploi, on obtient des résultats visuellement plus attractifs que la très grande majorité des images produites dans R.

visualisation avec qgraph

Le code R utilisé pour générer cette image est le suivant :

library(qgraph)

data(big5)

qgraph.panel(cor(big5),groups=big5groups,minimum=0.25, borders=FALSE,vsize=1,cut=0.3)

Le format des données en entrée est le même que pour le package igraph et, pour utiliser qgraph(x), x doit être une matrice (valuée), une liste de liens ou un objet de type qgraph. Le script suivant importe un tableau de données (individus – variables), calcule la matrice des corrélations puis la visualise en faisant varier couleur et valeur en fonction de la corrélation – seules celles supérieures à |0.5| sont représentées (option minimum).

library(qgraph)

#import du tableau de données

d <- read.table(« donnees.txt », sep= »\t », header=TRUE, row.names=1)

#calcul de la matrice de corrélations

m <- cor(as.matrix(d))

#visualisation

qgraph(m, layout= »spring », minimum=0.5)

Et on obtient une image de ce type-là : les corrélations négatives sont en verts, les corrélations positives en rouge, et l’épaisseur dépend de l’intensité de la relation entre les variables.

visualisation avec qgraph

Si on résume, le package peut produire des images plus sympathiques que la majorité des packages d’analyse de graphe dans R – sauf à écrire dans ces derniers d’interminables scripts – mais les limites sont évidentes : seuls les graphes simples et valués sont concernés. Et le résultat reste quoi qu’il en soit moins attrayant que ceux obtenus avec les logiciels évoqués au début de ce billet. Donc, ce package vous sera utile si et seulement si vous représentez souvent des matrices de corrélation…

Références

S. Epskamp, A.O.J. Cramer, L.J. Waldorp, V.D. Scmittmann et D. Borsboom, 2012, qgraph: Network Visualizations of Relationships in  Psychometric Data, Journal of Statistical Softwares, 48(4): 1-18, http://www.jstatsoft.org/v48/i04/.

Blog de Sacha Epskamp : http://sachaepskamp.com/qgraph.

Du côté de chez QuACN – module R pour l’analyse de réseaux

Il est des jours où l’on se croit parvenu à un niveau de connaissance concernant l’analyse de réseaux tout à fait honorable. Pas de quoi faire  carrière au MIT ou révolutionner l’analyse de réseaux, certes. Mais enfin, on est capable de lire des sociologues, des historiens, des physiciens, on est capable d’apprécier la nouveauté des approches et d’échanger avec des praticiens de ces disciplines.

Et puis, on découvre en fouillant sur le CRAN un package R intitulé QuACN (Quantitative Analysis of Complex Networks). Le module est récent, la documentation de bonne qualité et, au premier coup d’œil, on se croit en terrain bien balisé. Les indicateurs standards sont là, du diamètre au clustering coefficient (global et local) en passant par les degrés.

Puis, on regarde la documentation en détail et là, oh surprise, je ne connais pas la moitié des indices et mesures proposés. La documentation étant bien faite, toutes les formules correspondantes sont indiquées et les références bibliographiques sont nombreuses. Et il y a visiblement de quoi creuser, que ce soit du côté des mesures d’entropie, des indices variés (Harary, Wiener ou Balaban J – ???) ou des mesures de complexité disponibles pour sommet, graphe et liens (valués ou non).

L’importation des données se fait sans souci majeur.

Le format des données doit être de type graphNEL. Convertir  un objet igraph en objet graphNEL se fait à l’aide de la fonction igraph.to.graphNEL. L’opération inverse – convertir un objet graphNEL en objet igraph, par exemple pour permettre sa visualisation – se fait avec la fonction igraph.from.graphNEL. Il est également possible d’importer des matrices ou des listes de liens. Pour le premier cas (matrice d’adjacence valuée ou non), il suffit de la transformer à l’aide de la commande as(nom_matrice, « graphNEL »). S’il s’agit d’une liste de liens, il faudra après l’importation la transformer en matrice (as.matrix) puis en objet graphNEL. Un certain nombre des mesures disponibles nécessite des graphes de type particulier (orienté ou non, valué ou pas).

De tous les packages testés ces dernières semaines, celui-ci paraît l’un des plus riches en mesures (pour moi) inédites et il est aisé d’utilisation – à creuser donc.

Références

Laurin AJ Mueller, Karl G Kugler, Andreas Dander, Armin Graber et Matthias Dehmer, 2011, QuACN – An R Package for Analyzing Complex Biological Networks Quantitatively, Bioinformatics, 27, p.140-141.
Package QuACN sur CRAN : http://cran.r-project.org/web/packages/QuACN/index.html

Cytoscape, logiciel pour l’analyse des graphes (biologiques et autres)

logo du logiciel CytoscapeSi on en croit la page What is Cytoscape?, ce logiciel, open source et multi-plateformes, est dédié à l’analyse des graphes biologiques, et plus précisément à la visualisation des interactions moléculaires. Les réseaux biologiques étant formellement équivalents à tous les autres (sommets, liens et attributs), ce logiciel est évidemment adapté à tous les types de réseaux (simples ou non, bipartites ou one-mode, valués ou booléens), y compris les multigraphes ou les réseaux multiniveaux. Public depuis 2002 et la version 0.8, le logiciel, développé en Amérique du Nord (États-Unis et Canada) mais bénéficiant de soutiens plus larges (Institut Pasteur notamment), en est désormais à la version 2.8.3.

Téléchargement et documentation : http://www.cytoscape.org/

 

Import et export des données

Le format natif du logiciel bénéficie de l’extension .cys. Il s’agit en fait d’un fichier unique généré par le logiciel à partir de différents fichiers sources (.xls, .csv notamment).

L’importation de ses propres jeux de données est relativement simple dans la mesure où il suffit d’un fichier .xls, .txt ou .csv comportant deux colonnes (origine – destination) ou plus (attributs des liens seulement). Il suffit de préciser dans la boîte de dialogue l’origine (Source interaction) et la destination (Target interaction). Le type d’interaction proposé par défaut pp (soit protéine – protéine) convient pour la plupart des réseaux. Une boîte de dialogue permet de spécifier le séparateur de colonnes, la présence ou non de noms de colonnes etc. Pour une fois, la mise en forme des données ne devrait pas être trop chronophage.

Pour importer des attributs relatifs aux sommets, dérouler le menu File > Import > Attribute from Table.

Menu pour l’importation

menu d'importation du logiciel cytoscape

 Importation de tables (.xls, .txt, .csv)

importation de tables dans le logiciel cytoscape

Menu pour l’exportation

menu d'exportation du logiciel cytoscape

La taille des graphes étudiés ne devrait guère poser de problèmes : le manuel indique qu’avec 512 Mo de RAM (souvenirs, souvenirs…), le logiciel permet d’étudier des graphes de 20 000 (avec visualisation) à 70 000 sommets (sans visualisation).

Mesures

De nombreuses mesures, tant locales que globales, sont disponibles. Les plugins installés par défaut (et il y en a un nombre respectable, mais bien d’autres sont disponibles) permettent de recueillir de nombreuses données de façon simultanée. Et si on souhaite étudier tel ou tel type de graphe, on peut installer les plugins disponibles à l’adresse http://chianti.ucsd.edu/cyto_web/plugins/. Les mesures peuvent être exportées en bloc, et les nuages de points (avec ou sans courbe d’ajustement) peuvent être sauvegardés en format image ou vectoriel. Comme tous les logiciels récents, les mesures proposées viennent autant de la Social Network Analysis que de l’approche physicienne des réseaux.

plugins du logiciel cytoscape

 

Mesures disponibles via le plugin Netwok Analysis

mesures proposées par cytoscape

Les modifications (supprimer des boucles par exemple) peuvent être effectuées simultanément sur tous les graphes chargés lors d’une session (Plugins > Networks modification). En cas de manipulation hasardeuse, la commande Undo (Ctrl + Z) permet d’annuler celle-ci.

Les visualisations produites sont modifiables à l’envie, tant pour les liens (couleur, épaisseur, style, droits ou courbes) que pour les sommets ou l’algorithme de visualisation, et les résultats sont esthétiquement très satisfaisants. Il est possible de créer et d’enregistrer ses propres styles visuels afin de les réutiliser ultérieurement. Gadget qui peut être utile : il est possible d’importer une image (format .gif, .jpg ou .png) qui servira d’attribut à un ou plusieurs sommets.créer son style visuel avec Cytoscape

La sélection d’un sommet ou d’un ensemble de sommets se fait par simple clic de souris. Les algorithmes de visualisatipn peuvent être appliqués à l’ensemble du graphe (heureusement) ou à une sélection de sommets seulement. Certains sont originaux : ainsi le Attributes circle layout qui aligne sur un même cercle les sommets ayant le même attribut. Enfin, l’export peut se faire en format image ou vectoriel (.pdf, .svg, .eps, et .png notamment).

Exemple de visualisation avec Cytoscape

 

En conclusion (provisoire)

Les indications données ici ont pour seul objectif de faire connaître l’outil et de faciliter sa prise en main, mais les possibilités du logiciel sont beaucoup plus conséquentes et méritent largement d’être explorées. Même les personnes qui sont (comme moi…) lassées des logiciels clicodromes à produire de la belle image devraient être séduites par les capacités de cet outil. D’autant plus qu’il est possible de l’utiliser en lignes de commande !

 

Ressources, aide et tutoriels

La rubrique d’aide, accessible via l’icône bouée, est complète mais plutôt mal fichue, le texte étant mal formaté et obligeant à lire d’interminables lignes horizontales. Plusieurs tutoriaux sont accessibles sur le wiki http://opentutorials.cgl.ucsf.edu/index.php/Portal:Cytoscape. De nombreux jeux de données (biologiques) se trouvent à l’adresse http://www.pathguide.org/. Ils peuvent être importés directement dans le logiciel via le menu File > Import > Network from Web Services

Pour citer le logiciel : Shannon P, Markiel A, Ozier O, Baliga NS, Wang JT, Ramage D, Amin N, Schwikowski B, Ideker T., Cytoscape: a software environment for integrated models of biomolecular interaction networks. Genome Research, 2003 Nov, 13(11): 2498-504.

 

Note : le logiciel testé est la version 2.8.3 sous environnement Windows 7 – 64 bits.

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.

 

Cartographier flux et relations avec Paj2KML

Le logiciel Paj2KML est un petit utilitaire Windows bien utile pour qui souhaite combiner graphe et représentation cartographique.

Le fichier .exe doit être placé dans le même dossier que :

  • un graphe Pajek au format .net

Lancer le logiciel produit alors un fichier .kml qu’il est possible de superposer à une vue Google Earth ou Google maps. Le plus pratique reste cependant d’ouvrir le fichier .kml et de copier/coller le contenu ici : http://display-kml.appspot.com/. La carte apparaît quelques secondes plus tard. Il n’est pas possible de l’exporter en format image ou vectoriel, seule la capture d’écran est possible.

L’exemple ci-dessous utilise l’un des jeux de données sur les relations entre les villes mondiales du GaWC (http://www.lboro.ac.uk/gawc/datasets/da7.html).  Il s’agit d’un indice variant entre 0 et 1 et mesurant l’intensité des échanges de services entre villes. Le graphe de départ est complet, différents seuils ont été testés afin de produire une visualisation lisible.  Seuls les liens supérieurs à 0.4 ont été gardés.

Les deux images ci-dessous montrent le graphe généré par Pajek (algorithme de Kamada-Kawai > Free) et la carte correspondante générée par display-klm.

Visualisation produite par Pajek

Résultat obtenu avec Paj2KLM

La principale limite est évidemment la projection Mercator qui se prête particulièrement mal à la représentation de flux mondiaux. De plus, si la vue globale peut faire illusion, zoomer sur la carte (voir ci-dessous) montre que la précision de l’outil est très relative…

Visulisation produite par Paj2KLM - détail

Le fichier groupefmr_Paj2KML.zip téléchargeable ci-dessous contient trois fichiers : le jeu de données du GaWC original au format .net, le même fichier mais uniquement avec les liens supérieurs à 0.4 et enfin le fichier .txt avec les coordonnées de 55 villes concernées. Les liens internet et le descriptif des fichiers  se trouvent dans LISEZ_MOI.txt.

Dossier .zip téléchargeable ici.

Merci à Marion Maisonobe d’avoir attiré mon attention sur cet utilitaire il y a de nombreux mois déjà.

Plus d’informations et d’exemples sur la page http://www.leydesdorff.net/gmaps/.

Après Pajek, Pajek XXL

Logo de Pajek XXLUne version spéciale de Pajek, dédiée à l’analyse des énormes graphes (huge graph), est disponible depuis maintenant près d’un an pour les systèmes d’exploitation Windows 32 et 64 bits.

D’après le site officiel, cette version XXL permet l’analyse de graphes peu denses (sparse networks) comptant jusqu’à plusieurs dizaines de millions de sommets, à condition bien sûr que l’ordinateur puisse stocker les résultats générés.

L’interface ne change guère, excepté l’absence du menu Draw et, inversement, la présence du menu VertexID. Ce dernier permet de nommer les sommets de 1 à n, les sommets étant par défaut anonymes afin de garder un maximum d’espace mémoire disponible.

 Interface du logiciel Pajek XXL

Avant de s’amuser avec des graphes monstrueux, il est prudent de déterminer la mémoire disponible sur son ordinateur avec la fonction Info > Memory (ou F11), surtout après avoir généré un graphe volumineux. La capture d’écran ci-dessous montre les informations obtenues.

Message obtenu avec Info > Memory

Afin ne pas saturer l’espace disponible, les auteurs recommandent de répondre No quand Pajek demande si l’on souhaite créer un nouveau réseau. Pour mémoire (mais je renvoie au billet écrit avec Pierre Mercklé dans Quanti/Sciences sociales [1]), à chaque opération ou presque, Pajek crée de nouveaux réseaux correspondant aux résultats de ces opérations. On s’en doute, si le  graphe de départ est monstrueux, les fichiers correspondants aux résultats ne seront pas très légers.

L’utilisation attendue par les auteurs est double :

  • mesures directes sur un gros graphe ;
  • extraction d’un sous-graphe pertinent pouvant être analysé et visualisé avec le programme Pajek standard.

Les exemples proposés par les auteurs sont d’un intérêt limité dans la mesure où, comme ils l’écrivent eux-mêmes, les mêmes traitements pourraient être réalisés sans problème avec le Pajek standard. L’absence de visualisation pourra gêner celles et ceux qui restent persuadé-e-s que l’exploration visuelle reste la démarche primordiale en analyse de graphes.

Enfin, il est possible de s’interroger sur les utilisateurs et utilisatrices potentiel-le-s de ce programme. A priori, si je sais générer des graphes de millions de sommets, je n’ai pas spécialement besoin d’un logiciel clicodrome… Mais dans la mesure où les packages R se heurtent vite à des problèmes de mémoire disponible, ce Pajek-XXL peut constituer ne piste alternative ou complémentaire intéressante. A tester donc…

Téléchargement et informations : http://mrvar.fdv.uni-lj.si/pajek/default.htm

[1] Beauguitte Laurent et Pierre Mercklé (2011), “Analyse des réseaux : une introduction à Pajek”, Quanti, mis en ligne le 6 juin 2011, URL : http://quanti.hypotheses.org/512/.

Jongler avec les objets R, le package intergraph

Plusieurs modules existent pour analyser les graphes dans R, les plus fréquemment commentés étant sna et igraph. Ces packages utilisent des objets particuliers [1] : sna utilise des objets network, igraph des objets… igraph [2]. Le module intergraph permet de jongler entre les modules et les objets et deux commandes s’avèrent particulièrement utiles : as.igraph et as.network. La première transforme un objet network en objet igraph, la seconde fait l’inverse. La fonction netcompare permet ensuite de contrôler que la transformation s’est déroulée correctement. Autre fonction très utile asDF qui transforme objets network et igraph en data.frame.

Exemple de script tiré de la documentation du package

#chargement des packages

library(intergraph)
library(statnet)
library(igraph)

#jeux de données statnet

g1 <- faux.mesa.high

#type et structure

class(g1)
summary(g1)

#transformation en objet igraph

g2 <- as.igraph(g1)

#contrôle

netcompare(g1, g2)

#jeux de données igraph

g3 <- exIgraph

#transformation en objet network

g4 <- as.network(g3)

#contrôle

netcompare(g3,g4)

#transformation en data.frame
#et contrôle

d1 <- asDF(g1)
str(d1)
d2 <- asDF(g3)
str(d2)

Référence : Michal Bojanowski, Package ‘intergraph’, Coercion routines for network data objects in R, 19 Juin 2012.

http://intergraph.r-forge.r-project.org, http://www.bojanorama.pl

[1] Le type d’un objet x dans R s’obtient avec la commande class(x).

[2] Le problème ne se pose pas avec tnet qui utilise des objets matrix.

Pigale, logiciel pour l’analyse des graphes planaires

Logo du logiciel PigaleSi les logiciels d’analyse de graphes sont très nombreux, les logiciels dédiés à l’analyse des graphes planaires le sont beaucoup moins.

Le logiciel Pigale (Public Implementation of a Graph Algorithm Library and Editor), développé par H. de Fraysseix  et P. Ossona de Mendez, fait partie de cette catégorie peu fournie. Libre et multi-plates-formes, il présente une autre originalité : son interface est en français (voir image ci-dessous).

 

Interface du logiciel Pigale

 Il est possible soit d’importer un graphe (formats .tgf, .txt ou .graphml) soit de le dessiner directement dans la fenêtre (Fichier > Nouveau graphe). L’exportation est possible dans les 3 formats cités précédemment. Les visualisations peuvent être exportées en format image ou vectoriel (.png, .jpg, .pdf, .svg, .ps). 

 Pour dessiner un graphe, cocher l’option Ajout/Eff du menu Boutons gauche  puis cliquer dans la fenêtre graphique pour ajouter les sommets. Pour tracer un lien, cliquer sur un sommet et maintenir la pression jusqu’au sommet cible. Les liens créés sont par défaut non orientés : il est possible dans un second temps de les orienter en cochant l’option Oriente avant de cliquer sur le sommet récepteur du lien. Ainsi, pour obtenir la figure ci-dessous, je crée deux sommets (Ajout/Eff), coche le bouton Oriente puis clique sur le sommet numéro 6.

L’orientation des liens peut être générée (ou supprimée) pour l’ensemble du graphe à l’aide du menu déroulant Orienter (commandes Tout orienter et Désorienter les arêtes). Les caractéristiques du graphe dessiné s’actualisent à chaque tracé dans la fenêtre Propriétés du graphe. Les analyses possibles en fonction du graphe tracé s’actualisent également : les options en noir sont accessibles, celles en rouge ne le sont pas.

Pour supprimer un sommet ou un lien, cliquer sur l’objet en maintenant Shift enfoncé. Il est possible de modifier l’aspect du graphe (liens courbes ou lignes brisées – voir les deux représentations du même graphe ci-dessous). Enfin, trois épaisseurs de ligne sont possibles (bouton Col/Thick).

Il est également possible de générer de nombreux types de graphes dont l’image ci-dessous ne donne qu’un petit échantillon.

Générer des graphes avec Pigale

 Je n’ai pas l’impression qu’il soit possible d’allouer des attributs aux sommets et/ou aux liens. Quant à savoir si la panoplie d’outils proposée est suffisamment complète ou si elle souffre de graves lacunes, j’avoue ne pas être capable de le déterminer, n’ayant qu’exceptionnellement travaillé sur des graphes planaires. En tout cas, l’outil est facile à prendre en main et constitue sans nul doute un bon support pédagogique pour des cours sur ce type de graphes.

La version de Pigale testée ici est  la version 1.3.11 (une version 3.12 est disponible mais l’installation sous Windows est un peu pénible).

Pigale : http://sourceforge.net/projects/pigale/

Un module R pour l’analyse des graphes bipartis : le package bipartite

Dans un tutoriel disponible sur Cours en ligne, j’ai présenté trois modules R pour l’analyse de réseaux (statnet, igraph et tnet). D’autres modules sont disponibles et ce court billet présente les principales fonctions du module bipartite (version 1.17). Les termes anglophones sont en italique, les commandes et les scripts R en gras.

Pour mémoire, un graphe biparti (bipartite, two-mode network ou affilliation network) représente les liens entre deux ensembles d’acteurs différents. L’un des jeux de données les plus étudiés de ce type est ainsi le graphe dit Davis’ Southern Women Club, à savoir le graphe symbolisant la participation de 18 femmes à 14 réunions dans une ville du sud des États-Unis dans les années 30 (ce jeu de données est disponible dans quasiment tous les logiciels d’analyse de réseau).

Le package bipartite étant développé par des écologues, les réseaux inclus concernent essentiellement des liens fleurs – pollinisateurs.

La structure des données en entrée doit être de forme matricielle, le package traitant des objets de type « matrix« . Le graphe peut être valué.

Contrairement à la plupart des modules qui proposent un (voire plusieurs) fonction(s) pour obtenir un seul indicateur, bipartite a l’excellente idée de proposer deux fonctions, l’une portant sur les sommets (specieslevel), l’autre sur l’ensemble du graphe (networklevel). Dans les deux cas, les mesures proposées sont nombreuses et mêlent indicateurs canoniques (densité, degré) et innovations de ces dix (quinze) dernières années (modularité). Certaines fonctions créent des graphiques bienvenus, telle la fonction degreedistr qui permet de représenter fréquence cumulée et droite de régression.

Résultat des commandes

data(Safariland)                   #réseau de pollinisation argentin

degreedistr(Safariland)

sortie graphique de la commande degreedistr

Il est également possible de comparer les caractéristiques du graphe étudié et celles de graphes aléatoires bipartis (voir script téléchargeable ci-dessous).

Les visualisations produites sont moins attrayantes que celles disponibles avec des réseaux one-mode et cela est logique dans la mesure où les algorithmes de visualisation pour les graphes bipartites sont – à ma connaissance – rares. Trois types sont disponibles (voir les sorties graphiques par défaut ci dessous) : matrice d’adjacence, graphe bipartite et graphe de co-occurence.

Résultat des commandes

data(Safariland)
visweb(Safariland)
résultat de la commande visweb

Résultat des commandes

data(Safariland)
plotweb(Safariland)
résultat de la commande plotweb

Résultat des commandes

data(Safariland)
plotPAC(Safariland)
résultat de la commande plotweb

Comme toujours avec R, le plus utile est encore de tester le package et de fouiller les rubriques d’aide des différentes fonctions. Le script téléchargeable ci-dessous présente les principales fonctions et les options de visualisation disponibles. Il ne prétend évidemment pas à l’exhaustivité.

Script R pour le package bipartite

Toute la documentation est ici : http://cran.r-project.org/web/packages/bipartite/index.html

Référence : Dormann, C.F., Gruber B. & Fründ, J. (2008). Introducing the  bipartite Package: Analysing Ecological Networks. R news Vol 8/2, 8-11.

Visone (visual social network)

Visone est un logiciel développé depuis 2001 à l’University de Konstanz et à l’Institut de technologie de the Karlsruhe. La version testée ici est la 2.6.5 (Java jar, 18 MB) du 5 mars 2012. Gratuit, le logiciel est multiplateforme (Linux, OSX et Windows) mais non Open source. L’installer suppose d’avoir un environnement Java installé sur son ordinateur (voir le tutoriel suivant ).

L’interface graphique ressemble beaucoup à celle d’autres logiciels (Tulip, Gephi etc) mais a l’avantage de proposer toutes les options possibles sur la même page.

Interface du logiciel Visone

Les algorithmes de visualisation proposés sont peu nombreux et souvent classiques (circle, random ou MDS notamment). Les outils d’analyse sont peu nombreux mais divers et piochent chez les physiciens comme chez les sociologues (notamment pour le clustering). Ils permettent d’étudier graphes booléens et valués. Les résultats ainsi que les graphes ouverts (ou directement dessinés grâce à la plume) sont stockés dans le dossier nommé attribute manager. Il est possible d’obtenir les résultats et d’appliquer un algorithme de visualisation de façon simultanée à tous les graphes ouverts.

Le format des fichiers est, pour le graphe, des fichiers  .graphml et pour les attributs des sommets et/ou des liens, des fichiers .csv. Il est possible d’importer et d’exporter dans les formats les plus courants (Ucinet, Pajek ou .gml) et l’exportation des visualisations est possible en format image comme en format vectoriel.

Point intéressant, le logiciel peut être connecté à R (voir ici), ce qui permet de lancer des modèles Siena (à ce sujet, voir la synthèse fmr n°13 consacrée à la modélisation statistiques des réseaux). Il permet également de créer des animations de façon relativement simple : il suffit de créer une network collection manager et de sélectionner les graphes à introduire dans l’animation, puis de cliquer sur la bobine.

Par contre, je n’ai pas trouvé d’indications concernant les tailles limites de graphes supportées par le logiciel (mais je n’ai pas encore tout lu).

Pour plus d’informations : http://www.visone.info/

Le convertisseur de matrices

Le convertisseur de matrices, développé par Isabelle Brémond au sein du laboratoire RESO (UMR 6590 CNRS – Université de Rennes 2), est  un petit outil très pratique pour transformer :

    • une liste de liens en matrice ou
    • une matrice en liste de liens (origine, destination, poids).

Il est donc très utile pour préparer une importation de données dans Pajek par exemple. Les formats en entrée et en sortie sont des fichiers .txt ou .csv. L’interface est simple et intuitive et la prise en main du logiciel demande… une poignée de secondes.

Menu pour choisir l’action à effectuer

Noms donnés par défaut au tableau 3 colonnes

Un bémol ? Il n’est utilisable pour le moment que sous environnement Windows (XP ou Vista,  je n’ai pas réussi à l’installer sous Windows 7 64 bits). On peut également regretter que cet utilitaire très pratique ne soit pas Open Source.

Pour plus de renseignements : cliquer ici.