Analyse des forces et des faiblesses d’un réseau avec R : le package NetSwan

Suite à l’école thématique RESEM « Etudier les réseaux sociaux : espaces, mobilités » qui s’est tenue du 21 au 25 septembre sur l’île d’Oléron, je me suis dit qu’il serait pertinent de sensibiliser davantage d’autres disciplines aux extensions que je développe concernant l’analyse des forces et des faiblesses des réseaux. En effet, durant cette école thématique pluridisciplinaire, seuls des géographes m’ont posé des questions concernant le plugin QGIS que je développe périodiquement. Il faut dire que les SIG restent avant tout utilisés par des géographes et que le plugin en question se focalise sur des réseaux spatiaux !

Ainsi, durant la semaine de pause pédagogique de cette fin d’octobre, j’ai entrepris d’écrire quelques fonctions permettant d’analyser les forces et les faiblesses d’un réseau à l’aide du logiciel R. Puis, afin de diffuser ces fonctions, je n’ai trouvé d’autres solutions que de produire un package. Autant le dire de suite, l’aide est très cursive et rédigée dans un anglais très moyen. Néanmoins, ce package est depuis le 31 octobre disponible sur le CRAN. Une des tâches les plus difficiles a finalement été de trouver un nom à ce package : ce sera finalement NetSwan pour « NETwork Strengths and Weaknesses ANalysis ». Ce package repose sur le package Igraph.

Cette version 0.1 est un ballon d’essai visant à étudier si ces développements sont pertinents en dehors du champ des réseaux spatiaux. Ainsi, seulement quatre fonctions sont proposées actuellement. Une fonction « swan_efficiency » qui se focalise sur la comparaison des valeurs d’éloignement entre le réseau normal et le réseau perturbé. Une fonction « swan_closenness » qui se focalise sur la comparaison des valeurs de proximité entre le réseau normal et le réseau perturbé. Une fonction « swan_connectivity » qui mesure le nombre de relations rendues impossibles lorsqu’un nœud est supprimé. Une fonction « swan_combinatory » qui reproduit les algorithmes d’erreurs et d’attaques développés par Albert et al. [1] [2].

Au-delà des exemples proposés dans l’aide, nous pouvons désormais analyser un réseau social aspatial comme le Zachary Karaté Club et tester sa résistance aux algorithmes développés par Albert et al. Pour cela, il convient de taper le code suivant :

library(igraph)
library(NetSwan)
karate<-make_graph("zachary")

res<-swan_combinatory(karate,10)

Le plus long consiste finalement à produire le graphique représentant les résultats de l’analyse :

plot(res[,1], res[,5], type="o", col="yellow", xlab="Fraction of nodes removed", ylab="Connectivity loss")
lines(res[,1],res[,3], type="o", col="red")
lines(res[,1],res[,4], type="o", col="orange")
lines(res[,1],res[,2], type="o", col="blue")
legend("bottomright",c("Random", "Betweenness", "Degree", "Cascading"),
lty=c(1,1,1,1), pch=c(1,1,1,1),

col=c("yellow","blue","red", "orange"))

Le code final est disponible ici. Il apparaît qu’avec 3 nœuds supprimés, il est possible de perturber plus de 60% des relations de ce réseau, quel que soit le type d’attaques. Seules les erreurs aléatoires produisent des perturbations moins importantes.

Si le besoin s’en fait ressentir, les pistes de développement pour ce package sont nombreuses. Premièrement, ce package ne supporte que les graphes définis avec igraph, il serait tout aussi pertinent de permettre l’analyse de graphes construits avec d’autres packages, comme par exemple statnet. Deuxièmement, les fonctions développées dans NetSwan proviennent avant tout de travaux se focalisant sur l’analyse des forces et des faiblesses de réseaux spatiaux. Il conviendrait de développer plus de fonctions qui tiennent compte des particularités des réseaux non spatiaux.

Serge Lhomme

Maitre de conférences à l’université Paris Est Créteil – Docteur en géographie de l’université Paris VII spécialité « dynamique des milieux et risques »

More Posts - Website

Cartographie de flux avec le package cartography

Depuis hier, le package cartography développé par nos collègues Timothée Giraud (http://rgeomatic.hypotheses.org/) et Nicolas Lambert (http://neocarto.hypotheses.org), tous deux ingénieurs à l’UMS RIATE, est en ligne sur le CRAN. Il permet de faire beaucoup de cartes différentes dont des cartes de flux. Le script et les données utilisés dans ce billet sont téléchargeables ici (j’arrête provisoirement github, j’y fais un peu n’importe quoi…) – le script est encodé en utf-8 (pour règler l’encodage dans RStudio : Tools > Global Options > Default text encoding).

La documentation sur les fonctions est lisible et homogène et les exemples fonctionnent mais, bien entendu, ce qui est intéressant est de pouvoir importer et cartographier ses propres données. Deux fichiers sont attendus en entrée : une liste de liens (origine, destination, intensité de la relation) et un fond de carte au format .shp. Les deux donneront dans R un data.frame et un  SpatialPolygonsDataFrame (noté SPDF dans la suite du  billet). Il est bien entendu nécessaire que le code des unités spatiales soit le même dans les deux fichiers…

La première étape consiste à attribuer des coordonnées à la liste de liens à l’aide de la fonction getLinkLayer. La fonction prend comme argument : le nom du SPDF et les colonnes origine-destination du data.frame. Si l’identifiant commun n’est pas la première colonne du SPDF, il est nécessaire de préciser la colonne adéquate avec l’argument spdfid = « Nom_de_la_colonne ». Dans l’exemple téléchargeable, l’argument est utilisé.

La fonction plot(SPDF) permet ensuite de visualiser le fond de carte.

Deux fonctions permettent de cartographier les flux : propLinkLayer (épaisseur proportionnelle à l’intensité) et gradLinkLayer (flux discrétisés). Le script téléchargeable devrait vous permettre de comprendre la logique d’utilisation et les principales options. Dans les deux cas, l’orientation des flux n’apparaît malheureusement pas.

Signalons enfin la fonction legendPropLines qui permet de personnaliser la légende de la carte réalisée (fonction non encore testée à ce jour).

La réalisation de cartes est plutôt aisée mais, comme toujours pour la cartographie des flux, cela ne garantit pas nécessairement un résultat d’une grande lisibilité…

 

 

Sélection de flux avec R : le package flows

L’analyse et la représentation des flux supposent le plus souvent une sélection de ces derniers. La méthode classique en analyse spatiale des flux dominants (voir ce billet) et les méthodes des flux majeurs (garder x premiers flux par lieu, les x flux les plus install.packages(« flows », dependencies = TRUE)importants en volume, les flux représentant plus de x % d’un volume donné etc.) forment les deux grandes familles de sélection couramment employées.

Le package flows, développé en juin-juillet au sein de l’UMS RIATE avec mes collègues Timothée Giraud (voir le blog rgeomatic) et Marianne Guérois permet de choisir ses critères de sélection, de calculer des indicateurs statistiques et, pour les flux dominants, de visualiser la sélection effectuée. Il est disponible sur le CRAN donc s’installe normalement avec un install.packages(« flows », dependencies = TRUE).

Les fonctions de sélection et d’analyse prennent en entrée une matrice carrée origine – destination. Si les données de départ sont de type origine – destination – intensité, la fonction prepflows permet de passer en format carré.

La fonction statmat fournit pour une matrice origine destination un certain nombre d’éléments utiles pour connaître les données de départ mais également justifier statistiquement la méthode ou le seuil retenu. On obtient notamment le volume total de flux et les indicateurs statistiques de base sur ces flux (quartiles, moyenne, etc.), la densité, le nombre, la taille et la composition des composantes connexes, le degré pondéré et non pondéré des sommets. Des sorties graphiques permettent d’étudier la distribution des degrés (pondérés et non pondérés) et des liens (boîte à moustache et courbe de Lorenz sur l’intensité des flux).

En ce qui concerne la sélection, trois familles de méthode sont implémentées :

  • flux dominants classiques ;
  • critères locaux (pour chaque sommet, garder les flux obéissant à tel critère) ;
  • critères globaux (considérant l’ensemble des flux, garder ceux obéissant à tel critère).

La fonction compmat permet de comparer deux matrices origine-destination de même dimension, notamment pour connaître la perte d’information consécutive à une sélection.

Enfin, la représentation graphique est limitée aux résultats issus de la méthode des flux dominants dans la mesure où d’autres packages existent pour visualiser des graphes valués ou réaliser des cartes de flux (un package de cartographie développé par le déjà cité Timothée Giraud et son collègue Nicolas Lambert devrait être disponible très prochainement). Elle permet d’obtenir des figures de ce type :

exemplemap

Exceptionnellement, je ne fournis pas de script : je me permets de renvoyer à la vignette qui accompagne le package et qui explique tant les méthodes que l’utilisation des fonctions.

Dernier point : n’hésitez pas à envoyer vos remarques (par mail ou en commentaire), demandes et critiques, pour que nous puissions améliorer ce package.

Combinaisons de graphes avec igraph

Ayant eu récemment à me pencher sur la question délicate des jointures entre réseaux ayant des liens en communs, j’en profite pour faire un point rapide sur les fonctions du package igraph permettant ces combinaisons. Si vous ne connaissez pas ce package, voyez les billets taggés R sur ce blog. Le script utilisé est téléchargeable sur github ici-même. et, pour les personnes qui n’ont pas envie et/ou besoin de s’inscrire sur ce git, il est reproduit à la fin de ce billet.

Soit les deux graphes suivants :

g1g2

g1 et g2 sont deux graphes non orientés et ont trois sommets (ACD) et deux liens en commun (pléonasme…). Toutes les fonctions commentées ici prennent des graphes de même type en entrée (orientés ou non), certaines autorisent les combinaisons de graphes différents (un orienté et un non orienté).

La première étape du script consiste à créer des attributs pour g1 et g2 : attributs du réseau, des sommets et des liens. L’objectif est de contrôler la perte éventuelle d’attributs lors des opérations effectuées. Pour mémoire, pour un graphe nommé g, la syntaxe de igraph est la suivante :

g$densite <- graph.density(g) #attribut du graphe
V(g)$degre <- degree(g) #attribut des sommets (V comme vertex)
E(g)$betw <- edge.betweenness(g) #attributs des liens (E comme edges)

La fonction graph.complementer prend un graphe en attribut et crée son complémentaire : les liens absents dans le graphe de départ sont créés, les liens présents dans le graphe de départ sont supprimés. Un paramètre booléen loops permet de décider si on souhaite ou non générer des boucles (par défaut, loops = FALSE). Les attributs du réseau et des sommets sont conservés, les attributs des liens sont perdus (ce qui semble cohérent, ces liens étant supprimés).

La fonction graph.difference prend deux graphes en entrée : seuls les liens présents dans le premier réseau et non dans le deuxième sont conservés, tous les attributs du premier réseau sont gardés. On peut également utiliser l’opérateur %m% (comme minus) : écrire graph.difference(g1,g2) ou g1%m%g2 est donc équivalent. La figure ci-dessous permet de comparer les résultats obtenus : le lien AD présent dans g1 et g2 donc les opérations g1-g2 et g2-g1 entraînent sa disparition.

graph_difference

La fonction (non utilisée dans le script) graph.disjoint.union permet de joindre deux graphes dont les sommets sont distincts.

La fonction graph.intersection (ou %s%) prend deux graphes en entrée et un paramètre keep.all.vertices (TRUE par défaut) permet de choisir entre garder l’ensemble des sommets et les seuls sommets connectés dans le graphe produit. Les attributs sont tous conservés. Enfin, la fonction graph.union prend deux graphes en entrée : tout lien présent dans un moins un graphe
sera dans le graphe produit – sans création de liens multiples – et tous les attributs seront conservés.

Script complet

library(igraph)

#création des deux graphes
d1 <- rbind(c(« A », »B »),c(« A », »C »), c(« B », »C »), c(« A », »D »), c(« D », »E »))
d2 <- rbind(c(« A », »F »), c(« A », »D »), c(« A », »C »), c(« C », »I »))

g1 <- graph.data.frame(d1, directed = FALSE)
g2 <- graph.data.frame(d2, directed = FALSE)

#visualisation
par(mfrow = c(1,2))
plot(g1, main = « g1 »)
plot(g2, main = « g2 »)
dev.off()

#3 points communs (ACD) et deux liens communs (AD et AC)

#ajout d’attributs : degré des sommets
V(g1)$degree <-  degree(g1)
V(g2)$degree <- degree(g2)

#ajout d’attributs aux liens (intermédiarité)
E(g1)$between <- edge.betweenness(g1)
E(g2)$between <- edge.betweenness(g2)

#ajout d’attributs au réseau : densité
g1$densite <- graph.density(g1)
g2$densite <- graph.density(g2)

#fonction graph.complementer
#crée un graphe avec les liens absents du graphe de départ
#les liens présents au départ sont eux supprimés
compg1 <- graph.complementer(g1, loops = FALSE)
plot(compg1)
#les attributs des sommets et du graphe sont conservés
#attributs des liens sont perdus
V(compg1)$degree
compg1

#fonction graph.difference premier réseau – deuxième réseau (opérateur %m%)
#seuls les liens présents dans le premier réseau et non dans le deuxième sont conservés
#tous les attributs du premier réseau sont gardés
diffg1 <- graph.difference(g1, g2)
diffg1

diffg2 <- graph.difference(g2, g1)

#coordonnées (quasi) identiques pour faciliter la comparaison
lay <- layout.fruchterman.reingold(g1)

#lien A-D présent dans g1 et g2 donc g1-g2 et g2-g1 entrainent sa disparition
par(mfrow = c(2,2))
plot(g1, main = « g1 », layout = lay, vertex.color = « red », vertex.size = 20, vertex.label.dist =3)
plot(g2, main = « g2 », layout = lay, vertex.color = « red », vertex.size = 20, vertex.label.dist =3)
plot(diffg1, main = « graph.difference(g1, g2) », layout = lay, vertex.color = « red », vertex.size = 20, vertex.label.dist =3)
plot(diffg2, main = « graph.difference(g2, g1) », layout = lay, vertex.color = « red », vertex.size = 20, vertex.label.dist =3)
dev.off()

#calculer degré actualisé
V(diffg1)$degree2 <- degree(diffg1)
V(diffg1)$degree
V(diffg1)$degree2

#graph.disjoint.union pour joindre des graphes dont les sommets différents (opérateur %du%)

#liens communs à deux graphes : conserve les attributs
#tous les sommets sont conservés (opérateur %s%)
interg1 <- graph.intersection(g1,g2, keep.all.vertices = TRUE)

#seuls sommets adjacents aux liens communs sont gardés (ici ACD)
interg2 <- graph.intersection(g1,g2, keep.all.vertices = FALSE)

par(mfrow = c(1,2))
plot(interg1, sub = « graph.intersection(g1,g2,\nkeep.all.vertices = TRUE) »)
plot(interg2, sub = « graph.intersection(g1,g2,\nkeep.all.vertices = FALSE) »)
dev.off()

#union de graphes : tout lien présent dans un moins un graphe
#est dans le graphe produit – tous les attributs sont conservés
#ne crée pas de liens multiples

uniong <- graph.union(g1,g2) #opérateur %u%

R et igraph – revue de détail

Suite du billet consacré à statnet il y a peu ici même.

L’objectif du billet est le même que pour celui signalé une ligne au dessus : importer et effectuer une série de mesures sur le graphe suivant. Téléchargement des fichiers de données et du script commenté ici (encodage en utf-8).
td1plot

Importer ses données

L’importation des données avec igraph est plus simple dans la mesure où les liens et les attributs des sommets peuvent être importés simultanément à l’aide de la commande graph.data.frame – et la gestion des sommets isolés ne pose donc aucun problème particulier. En ce qui concerne les liens, igraph considère que les deux premières colonnes correspondent aux origines et aux destinations, toutes les éventuelles colonnes suivantes seront considérées comme des attributs des liens.

Après transformation, taper le nom de l’objet créé permet d’obtenir à peu près les mêmes informations qu’avec statnet mais sous une forme un peu moins lisible.

library(igraph)

liens <- read.table("liens2.txt", header=TRUE, sep=";")
attributs <- read.table("attributs.txt", header=TRUE, sep=";")

g <- graph.data.frame(liens, vertices = attributs)
g
IGRAPH DN-- 7 8 -- 
+ attr: name (v/c), ANC (v/n), TEAM (v/c), I (e/n)

g est donc un objet igraph de type directed network (DN), comprenant 7 sommets et 8 liens. Il existe 3 attributs pour les sommets (attr v), deux de type character (name et TEAM), un de type numeric (ANC (v/n)) ; un attribut numérique I pour le lien.

Filtrer les données

Sélectionner une partie du graphe en fonction d’un attribut (des sommets et/ou des liens) est d’une grande simplicité une fois comprise la logique de la syntaxe.

Si je souhaite supprimer les liens d’une intensité inférieure à 2

g2 <- delete.edges(g,E(g)[I<2])

soit, si l’on décompose, la fonction delete.edges (nom du graphe, E comme edge (nom du graphe) [ attribut et condition]). Si l’on veut supprimer des sommets, on remplace par delete.vertices et E devient V comme ici où je supprime les sommets de degré inférieur à 2.

g22 <- delete.vertices(g, V(g)[degree(g) < 2])

Si l’on supprime des sommets, les liens adjacents disparaissent également. Si l’on supprime des liens, par défaut, tous les sommets du graphe restent présents.

Mesurer

La recherche de la densité (graph.density) donne – et c’est heureux – le même résultat que statnet, soit 0.19 (8/42).

La recherche des composantes connexes (clusters) renvoie une liste de 3 objets, l’appartenance des sommets (les sommets abcd sont dans la composante connexe numérotée 1), la taille des composantes connexes et leur nombre.

$membership
[1] 1 1 1 1 2 2 3
$csize
[1] 4 2 1
$no
[1] 3

Contrairement à statnet, igraph considère par défaut que la connexité faible est recherchée. Pour la connexité forte, il faudra utiliser l’option mode = « strong ».

La recherche des cliques (fonction cliques) est ici efficace mais, par défaut, igraph fournit toutes les cliques de taille 1, 2 etc. Il est donc conseillé d’indiquer un min. La direction des liens n’est pas et ne peut pas être prise en compte. Les commandes dyad.census et triad.census donnent exactement les mêmes résultats que statnet mais la présentation est moins claire ici pour cette dernière fonction car les codes MAN ne sont pas rappelés. Le résultat reproduit ci-dessous n’est pas très simple à interpréter.

 triad.census(g) 
 [1] 11 12  8  0  1  0  1  0  1  0  0  0  1  0  0  0

La commande degree fournit par défaut est la somme des degrés entrants et sortants. La normalisation (normalized = TRUE) se fait ici par le degré maximal possible. Si je calcule les degrés entrants normalisés, j’obtiens le résultat suivant :

 degree(g, mode="in", normalized = TRUE) 
    a         b      c     d      e       f         g 
0.1666667 0.3333333 0.50 0.000 0.1666667 0.1666667 0.00

Le degré entrant de c est 3, il y a 7 sommets donc le maximum possible est de 6 (pas de boucle) : c a donc un degré entrant normalisé de 0.5. La fonction degree.distribution donne la proportion de sommets ayant un degré zéro, un, deux etc. Mais si on visualise avec la fonction plot(degree.distribution(g)), l’axe des abscisses est faux (il commence à un au lieu de zéro). Et si vous faites partie des adeptes du scale-free, le fameux plot log log s’obtient aisément (voir le script) mais il n’a évidemment aucun intérêt pour un réseau aussi modeste.

La fonction closeness appliquée à un graphe non connexe donne les résultats aberrants suivants :

      a          b          c          d          e          f          g 
0.03333333 0.03333333 0.02380952 0.04000000 0.02777778 0.02777778 0.02380952

Il n’est par définition pas possible de calculer une centralité de proximité pour un sommet isolé, igraph y parvient… La solution permettant d’obtenir un résultat cohérent est de décomposer le graphe puis de la mesurer sur chacune des composantes considérée individuellement. L’option mode= »all » permet d’ignorer la direction des liens.

g2 <- decompose.graph(g)
plot(g2[[1]])
sapply(g2, closeness, mode="all")
[[1]]
        a         b         c         d 
0.2500000 0.3333333 0.3333333 0.2500000 
[[2]]
e f 
1 1 
[[3]]
  g 
NaN

Le résultat est plus crédible (NaN soit Not a Number pour g effectivement). 1 pour e et f, c’est logique. Mais pourquoi 0.25 pour a et d, 0.33 pour b et c. Petit rappel : pour mesurer la closeness, on divise 1 par la somme des plus courts chemins entre un sommet et tous les autres. Pour a et d, on a donc 1/(1+1+2) ; pour b et c, 1/(1+1+1). À retenir en résumé : faire attention avec la fonction closeness qui peut facilement donner des résultats absurdes…

La fonction betweenness donne les mêmes résultats que statnet mais igraph propose également de mesurer l’intermédiarité des liens, c’est-à-dire le nombre de plus courts chemins empruntant un lien donné. Par définition, cette intermédiarité des liens sera toujours supérieure ou égale à 1 (le lien entre a et b est placé sur le plus court chemin entre ces deux points). Les résultats sont présentés dans l’ordre des liens du fichier de départ. Soit le résultat suivant (les codes des liens ont été rajoutés manuellement a posteriori) :

edge.betweenness(g, directed=TRUE) 
   ef fe  ab  ba  ac db dc bc
[1] 1  1   1  2   1  2   1   1
edge.betweenness(g, directed=FALSE)
    ef  fe  ab        ba         ac      db        dc         bc
[1] 0.5 0.5 0.8333333 0.8333333 1.3333333 1.6666667 1.3333333 1.0

Si on prend en compte l’orientation des liens, tous ont un minimum de 1 et le lien ba atteint 2 : il se situe en effet sur les plus courts chemins ba et dba.  Si on ne la prend pas en compte, les résultats sont difficiles à comprendre. Pourquoi des résultats différents pour les liens db, dc, ab et ba ? Tout simplement parce qu’il y a trop de liens pour l’opération demandée : si je ne tiens pas compte de la direction, mon graphe ne comprend que 6 liens.  Donner des résultats pour 7 oblige à des pondérations étranges… La solution la plus pertinente est de transformer d’abord le réseau en réseau non orienté (as.undirected) puis de mesurer l’intermédiarité des liens. On obtient alors un résultat cohérent :

[1] 1.5 1.5 1.0 1.5 1.5 1.0

1 correspond ici aux liens ef et bc et les quatre autres liens obtiennent un score identique. Chacun est placé sur le plus court chemin entre ses sommets terminaux et est l’un des deux plus courts chemins entre a et d : tous ont donc 1.5.

La fonction transitivity (nombre de triangles fermés parmi les voisins d’un sommet) ne permet pas de prendre en compte l’orientation des liens : il est donc nécessaire pour obtenir des résultats corrects de prendre le graphe non orienté. On obtient alors les résultats suivants

transitivity(g3, "local")
[1] 1.0000000 0.6666667 0.6666667 1.0000000       NaN       NaN       NaN

a et d sont situés à la pointe dans des triangles fermés donc la transitivité est de 1 ; efg ne font pas partie de triades donc le résultat n’est pas un nombre (NaN = Not a Numer). b et c sont voisins et tous deux liés à a et à d ; comme il manque 1 lien entre a et d, ils obtiennent un score de 2/3 (2 triangles fermés sont présents sur 3 possibles). La recherche des plus chemins, par défaut, ne tient pas compte non plus de l’orientation des liens. La fonction centralization donne des résultats corrects pour les graphes k-réguliers (score de 0) et non valides pour les graphes en étoile (voir le script où un graphe étoilé de 10 sommets obtient un score de centralisation par le degré de 0.8 seulement). En ce qui concerne les graphes bipartis, même remarque que pour statnet : igraph permet d’en définir, d’en représenter mais ne permet pas de les analyser – lorsqu’une mesure est lancée, il est considéré comme un one-mode.

Pour résumer : il est beaucoup plus facile d’importer ses données et de les filtrer avec igraph, il est aussi beaucoup plus facile d’obtenir des résultats aberrants si l’on n’est pas attentif… À venir très prochainement, un billet détaillé consacré au package bipartite.

R et statnet – revue de détail

Suite aux cours et aux TD donnés à l’ENSAI, j’ai découvert de nouveaux (et agaçants) problèmes liés à l’analyse de réseau avec R. De plus, la nécessité de commenter les résultats m’est clairement apparue. Ce billet vise donc à détailler au maximum les étapes et les résultats produits par le package statnet – un billet consacré à igraph est en cours de préparation. Le script et les fichiers de données sont téléchargeables ici.

Rappel : statnet (et igraph) permettent d’analyser des graphes non valués et one-mode. Si statnet permet de mener des modèles type ERGM, igraph est plus simple d’utilisation. Pour l’analyse de réseau biparti avec R, oubliez statnet et igraph (qui proposent pourtant des options bipartite=TRUE) et voyez plutôt du côté du package bipartite qui est, à ma connaissance, le seul à donner des résultats corrects pour ce type de réseau (voir la démonstration dans le script).

1. Liens, attributs et isolés : sur le format et l’importation des données

Le graphe fictif qui va servir d’exemple tout au long de ce billet représente les interactions autour d’une machine à café dans une petite entreprise : la population est constituée de 7 individus répartis en 2 équipes et de niveaux d’ancienneté différents. Un lien signale qu’une personne a payé un café à une autre. Le graphe est simple : pas de boucle (on ne prend pas en compte les cafés que s’offre une personne) ; pas de liens de nature différente. Il est orienté (une personne offre à une autre) et valué (combien de cafés ont été offerts par une personne à une autre dans la semaine ?).td1plot

Les sommets sont définis par deux attributs : un attribut quantitatif relatif à l’ancienneté (ANC – taille du sommet), un attribut qualitatif relatif à l’équipe (TEAM – couleur du sommet). Les liens sont définis par une direction et une intensité (INT). La valeur des attributs est donnée dans le tableau ci-dessous.

td11

Un rappel important : statnet (comme igraph) ne prend pas en compte de l’intensité des liens pour les calculs. Elle peut juste être utilisée pour la représentation graphique.

Premier problème : statnet génère un graphe à partir d’une liste de liens. Or, le sommet g est isolé. Une solution est de créer dans son fichier de départ un lien fictif g-g puis de préciser lors de l’importation qu’il n’y a pas de boucle.

L’importation des données se fait en deux temps (liens, attributs des sommets). La transformation en objet network, manipulable par statnet, nécessite de ne prendre en compte que les deux premières colonnes (origine – destination). Taper ensuite le nom du graphe permet d’en connaître les caractéristiques. De façon étrange, alors qu’il n’y a pas de boucle, statnet indique malgré tout 9 liens et non 8. Pourtant, le calcul de la densité (cf infra) donne un résultat correct – seuls les 8 liens réellement présents sont donc pris en compte dans les calculs.

library(statnet)
#import fichier
 liens <- read.table("liens.txt", header=TRUE, sep=";")
 attributs <- read.table("attributs.txt", header=TRUE, sep=";")
g <- as.network(as.matrix(liens[,-3]), loops = FALSE)
g
 Network attributes:
 vertices = 7
 directed = TRUE
 hyper = FALSE
 loops = FALSE
 multiple = FALSE
 bipartite = FALSE
 total edges= 9
 missing edges= 0
 non-missing edges= 9
Vertex attribute names:
 vertex.names
No edge attributes

Pour l’instant, les sommets ont un attribut (leur nom) et les liens n’en ont aucun. Les lignes suivantes permettent de transférer les données des data.frame vers l’objet network.

g %v% "ANC" <- attributs$ANC
g %v% "TEAM" <- as.numeric(attributs$TEAM)
g %e% "INT" <- liens$I

Si l’on tape à nouveau g, on observe que les attributs sont désormais plus nombreux.

 Vertex attribute names:
 ANC TEAM vertex.names
Edge attribute names:
 INT

Il est sans aucun doute possible de filtrer le graphe selon les attributs des liens et des sommets (par exemple, extraire le graphe des relations entre membres de l’équipe A) mais si l’opération est facile avec igraph, elle ne l’est pas avec statnet (i.e. je n’ai pas trouvé comment faire, si ce n’est en filtrant les données en amont, avant la transformation en graphe…).

Pour obtenir la figure ci-dessus, deux options sont possibles : appeler les données des data.frame, appeler les attributs de l’objet network. Le résultat est heureusement le même.

#à partir des fichiers de départ
gplot(g, gmode="digraph", displaylabels=TRUE, vertex.col=nodeColors, 
      vertex.cex= log(attributs$ANC), edge.lwd = liens$I*2)

#à partir des attributs de l'objet network
gplot(g, gmode="digraph", displaylabels=TRUE, vertex.col=nodeColor, 
      vertex.cex= log(g %v% "ANC"), edge.lwd = g %e% "INT")

2. Quelques mesures et quelques précisions

Le calcul de la densité (fonction gden) donne comme résultat 0.1904762, ce qui correspond bien à 8 (nombre de liens présents) divisé par 7*6 (nombre de liens possibles) – pour mémoire, dans un graphe simple orienté de n sommets, le nombre maximum de liens est égal à n*(n-1).

Le nombre de composantes connexes s’obtient avec la fonction components et donne ici comme résultat 5. Pourquoi 5 ? Par défaut, statnet considère que, dans un graphe orienté, la connexité recherchée est la forte : il doit exister un chemin (une suite de liens orientés) entre toute paire de sommets au sein d’une composante connexe. La composition des 5 composantes connexes est obtenue avec la commande component.dist. Si l’on souhaite les composantes faiblement connexes (au nombre de 3), il suffit de modifier l’option.

components(g)  #   5 composantes fortement connexes
cs <- component.dist(g) 
cs$membership #  et leur composition

components(g, connected="weak") #  3 composantes faiblement connexes
cw <- component.dist(g,connected="weak")
cw$membership #composition
cw$csize      #et taille

La liste des plus chemins – retour de la commande geodist – comprend deux matrices : $counts donne le nombre de plus courts chemins entre paires de sommets (il peut très bien y avoir plusieurs plus courts chemins entre deux sommets) ; $gdist donne la longueur en liens des plus courts chemins. La commande dyad.census donne un résultat facilement interprétable (nombre de liens mutuels, asymétriques et nuls). La commande triad.census donne en sortie le code MAN (mutuel, asymétrique, nul) des triades et le nombre de triades respectives. Dans le graphe fictif étudié, il n’y a aucune triade complète, et donc 0 sous le code 300.

Il est déconseillé d’utiliser la commande clique.census : même avec un graphe aussi petit, et sur un ordinateur récent et plutôt puissant, RStudio plante…

En ce qui concerne le degré, la commande degree fournit par défaut la somme des degrés entrants et sortants par sommet. Si l’on choisit de normaliser, la somme des degrés des sommets sera égale à 1 (le mode de normalisation est différent dans igraph). Le graphe étant non connexe, la commande closeness donne un résultat égal à zéro pour tous les sommets (igraph donne lui des résultats aberrants). La centralité d’intermédiarité (betweenness) donne ici 0 pour tous les sommets sauf pour b qui obtient 1 : il y a en effet un seul plus court chemin (dba) passant par b. Si l’on ne prend pas en compte la direction des liens, tous les autres sommets restent à zéro et b descend à 0.5. Pourquoi ? Il y a deux plus courts chemins entre d et a (dba et dca), et 1 sur 2 passe par b. Que c reste à zéro est par contre difficilement explicable… (si vous avez une idée, n’hésitez pas à la soumettre).

Enfin, et je termine ici pour l’examen détaillé de certaines fonctions de statnet, la mesure de la centralisation du graphe est correcte dans statnet – on obtient bien 0 avec un graphe type cercle et 1 avec un graphe étoilé – mais elle donne des résultats erronés dans igraph

Dernier point qui concerne les graphes bipartis : statnet permet (difficilement) de les importer puis de calculer des indicateurs mais ceux-ci sont faux. Dans l’exemple du script, nous avons 7 liens, 3 événements et 4 acteurs. Si les 4 acteurs participent aux 3 événements, le graphe est complet, la densité de 1 et le nombre de liens égal à 12. Or, la commande gden donne comme résultat 0.33, soit 7*2 / 7*6 – dans un graphe simple non orienté de n sommets, la densité est égale à 2n / n(n-1). Et si vous tentez l’expérience avec igraph, le résultat est le même. Le seul – et très relatif – intérêt est de pouvoir passer ensuite à des matrices acteurs-acteurs ou événements-événements. Cette dernière opération est possible sans ces packages en multipliant la matrice m par sa transposée pour obtenir la matrice acteurs-acteurs

m %*% t(m)

ou en faisant l’opération inverse (matrice événements-événements)

t(m) %*% m

ENSAI TD2 – Manipulation de matrices et cartographie de flux avec R

L’objectif du TD est double : manipuler des matrices pour cartographier des indicateurs calculés à partir des marges (cf cours 3) ; mettre en œuvre avec R les méthodes de flux dominants, de flux majeurs et les modèles gravitaires. Ce TD reprend en partie une séance donnée avec Claude Grasland dans le cadre du groupe elementR (cf ce billet). Outre Claude Grasland, les scripts utilisés pour ce TD doivent beaucoup à Timothée Giraud (cf le blog R Géomatique), Nicolas Lambert (cf le blog néocarto) et Malika Madelin.

Packages utilisés : reshape2, maptools, rCarto, RColorBrewer.

Les données utilisées sont les migrations entre les dix régions tchécoslovaques en 1965 (téléchargement).

Manipulations de base

Deux manipulations sont nécessaires pour travailler sur les matrices : passer d’une matrice carrée à un format origine – destination – flux et réaliser l’opération inverse. De plus, pour cartographier des flux, il est nécessaire d’avoir un fond de carte au format .shp (avec des codes pour les unités spatiales similaires aux codes utilisées dans les fichiers de données pour permettre la jointure), de calculer les coordonnées des centroïdes et enfin les distances entre ces centroïdes. L’exemple ci-dessous détaille les étapes :

library(reshape2)

#passage data.frame type matrice en objet matrix

#importation de la matrice
tab <- read.table("matrice.csv", ... ,stringsAsFactors=FALSE)

#passage d'un objet data.frame à un objet matrix
mat <- as.matrix(tab[,-1])
row.names(mat) <- tab[,1]

#passage d'une matrice au format origine - destination - flux
tabflow <- melt(mat)
names(tabflow) <- c("i","j","Fij")
head(tabflow)

#passage d'une liste i-j-Fij au format matrice
tempo <- melt(tabflow,
             id.vars=c("i","j"),
             measure.vars="Fij")
tempo2 <- dcast(tempo, i~j)
matflow2 <- as.matrix(tempo2[,-1])
rownames(matflow2) <- tempo2[,1]

library(maptools)

#import d'un shape
fdc <- readShapeSpatial("carte.shp")

#calcul des centroides
centres <- cbind(fdc@data[,"CODE"], as.data.frame(coordinates(fdc)))
colnames(centres) <- c("CODE","X","Y")
head(centres)

#calcul de la distance
#2 étapes : passer en format long et coller les xi, yi, xj, xj
#appliquer la formule dij = round(sqrt((xi-xj)**2 + (yi-yj)**2)/1000, 1)

Déroulement du TD

Les scripts détaillant toutes les étapes sont disponibles ici.

Opérations élémentaires sur les matrices

  • importer le fichier matmig_1961_1965.csv et le tranformer en objet matrice (Fij)
  • calculer la transposée (Fji)
  • calculer le volume et le solde des échanges
  • à l’aide de la fonction apply, calculer les sommes marginales (arrivée, départ, volume, solde, asymétrie)
  • importer le fichier tch10.shp
  • cartographier différents indicateurs à l’aide du package rCarto (somme des départs, volume et asymétrie migratoire)
  • cartographier les flux d’émigration

Voici deux exemples de cartes à produire.

solde

echanges

Flux dominants et flux majeurs

  • à l’aide des fonctions apply, sum, max et de l’argument which.max, déterminer les flux dominants
  • à l’aide des foncions apply et rank, déterminer les flux majeurs (x premiers flux de i vers j)
  • repérer les flux supérieurs à 2% du volume total des flux et les cartographier

Modèles gravitaires

  • calculer les marges de la matrice de flux et les centroïdes des dix régions
  • passer la matrice en format i – j – Fij et coller masses et coordonnées
  • importer le fichier attributaire tchpop_1965_1990.csv et coller les éléments utiles au tableau i j Fij
  • le tableau final comprendra les éléments suivants : i j Fij Fji Fi Fj Xi Yi Xj Yj Dij POPi POPj
  • tester un modèle gravitaire prenant en compte masses et distance de type glm(Fij~log(POPi)+log(POPj)+log(Dij), data=mydata, family=poisson)
  • étudier les paramètres – summary(model) –, analyser la variance puis calculer et cartographier les résidus
  • mêmes étapes avec un modèle à double contrainte (origine et destination) – glm(Fij~i+j+log(Dij), data=mydata, family=poisson)

ENSAI TD1 – Analyse de réseaux avec R (statnet, igraph, tnet)

Packages utilisés : statnet, igraph, tnet.

Déroulement du TD

Créer les fichiers texte liens et attributs permettant de générer le graphe suivant. Ce graphe fictif représente les interactions autour d’une machine à café dans une petite entreprise : la population est constituée de 7 individus répartis en 2 équipes et de niveaux d’ancienneté différents. Un lien signale qu’une personne a payé un café à une autre. Le graphe est simple : pas de boucle (on ne prend pas en compte les cafés que s’offre une personne) ; pas de liens de nature différente. Il est orienté (une personne offre à une autre) et valué (combien de cafés ont été offerts par une personne à une autre dans la semaine ?).

td1plot

Les sommets sont définis par deux attributs : un attribut quantitatif relatif à l’ancienneté (ANC – taille du sommet), un attribut qualitatif relatif à l’équipe (TEAM – couleur du sommet). Les liens sont définis par une direction et une intensité (INT). La valeur des attributs est donnée dans le tableau ci-dessous.

td11

Consignes

  • créer les fichiers .txt liens et attributs
  • les importer dans R
  • les transformer avec statnet en graphe (le sommet isolé pose problème, il est nécessaire de créer un lien fictif g-g d’une intensité de 1 puis de spécifier qu’il n’y a pas de boucle)
  • représenter le graphe pour obtenir l’image ci-dessus
  • effectuer les mesures globales et locales pertinentes (et justifier le choix de ces mesures et des options choisies)
  • faire les mêmes opérations avec le package igraph (la gestion de l’isolé ne pose cette fois aucun problème) et tnet et comparer les résultats obtenus

Remarques

Quand c’est possible, calculer les mesures en prenant en compte l’orientation des liens ou non, calculer les mesures brutes et normalisées (repérer comment se fait la normalisation, par le maximum possible ou par le maximum atteint ?). Avec tnet, faire varier le paramètre alpha et comparer les résultats quand alpha vaut 0 (les intensités des liens ne sont pas prises en compte), 0.5 et 1 (prise en compte complète de l’intensité des liens).

Pour trouver les fonctions nécessaires et leurs options, voir les billets tagués R sur ce blog et la documentation des packages. Les résultats obtenus avec statnet sont détaillés dans ce billet ; ceux obtenus avec igraph dans celui-ci.

R et espace

Les éditions Framabook viennent de sortir le manuel R et espace. Traitement de l’information géographique coordonné par Hadrien Commenges et issu des réunions du groupe ElementR. Les contributeurs de l’ouvrage sont :

  • Laurent Beauguitte, chargé de recherche CNRS (UMR IDEES),
  • Élodie Buard, ingénieure de recherche à l’IGN,
  • Hadrien Commenges, post-doctorant au LEESU,
  • Robin Cura, doctorant à Géographie-cités (UMR 8504),
  • Florent Le Néchet , maître de conférences à l’Université Paris-Est Marne-la-Vallée,
  • Marion Le Texier, post-doctorante à l’Institut universitaire européen de Florence,
  • Hélène Mathian, ingénieure de recherche CNRS (UMR EVS),
  • Sébastien Rey-Coyrehourcq, doctorant à Géographie-cités (UMR 8504).

Ne vous laissez pas abuser par le titre, l’ouvrage s’adresse à toute personne désireuse de se former au logiciel R, qu’il s’agisse de réaliser des traitements statistiques, de l’analyse de réseau ou de la cartographie. Le sommaire est le suivant :

Introduction : R pour . . .
1 Prise de contact p. 1 – 10
2 Prise en main et manipulation des données p. 11 – 41
3 Introduction à la programmation p. 45 – 65
4 Analyse univariée p. 71 – 76
5 Analyse bivariée p. 83 – 103
6 Analyses factorielles p. 105 – 116
7 Méthodes de classification p. 121 – 135
8 Analyse de graphes p. 141 – 155
9 Focus sur la visualisation graphique p. 159 – 172
10 Introduction aux objets spatiaux et à la cartographie p. 175-203
11 Initiation aux statistiques spatiales p. 209 – 227
Annexes
A Bibliographie thématique 235
B Liste des packages utilisés 239

Le livre est en vente au prix modique de 15 euros mais la version pdf peut également être téléchargée gratuitement à cette adresse : http://framabook.org/16-r-et-espace/. L’ensemble des codes et les données utilisées dans l’ouvrage sont librement disponibles à cette même adresse. Enfin, le groupe a depuis peu repris ses activités et vient de créer un blog sur la plateforme hypotheses. Il n’est pas encore très fourni mais cela devrait changer dans les prochaines semaines (http://elementr.hypotheses.org/).

 

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

Ci-dessous, deux présentations faites à l’école d’été Ferney-Voltaire consacrée aux réseaux (voir le programme sur le site http://ferney2014.sciencesconf.org/). La première est un survol, nécessairement très schématique, bourré de raccourcis et sans aucun doute empreint d’une évidente subjectivité, de l’analyse de réseaux dans les différentes sciences (sociales ou non sociales) de Moreno à nos jours. La deuxième présentation est une initiation à R qui pourra utilement compléter les différents billets tagués R disponibles sur ce site. Et les autres riches présentations faites à cette école (qui dure jusqu’au jeudi 28 août) devraient normalement être prochainement disponibles en ligne sur le site signalé plus haut.

 

 

Les indices Kansky avec R : premières fonctions

K. Kansky est un géographe américain qui, dans sa thèse imprimée en 1963, proposa un certain nombre d’indicateurs permettant de caractériser des réseaux, indicateurs directement issus de la théorie des graphes. Si l’ouvrage est quasiment introuvable, le chapitre 2 Measures of network structure en 1989 paru dans la revue Flux est lui accessible sur Persée (http://www.persee.fr/web/revues/home/prescript/article/flux_1154-2721_1989_hos_5_1_913). Ces indices ont connu un succès foudroyant en géographie des transports et restent encore largement utilisés aujourd’hui. Bizarrement, aucun package R ne permet – à ma connaissance – de calculer ces indices. Le présent billet rappelle très brièvement la définition de ces indices, leur interprétation et fournit les fonctions R – basées sur le package igraph – permettant de les calculer.

Petite précision : il s’agit de ma toute première tentative d’écriture de fonction, merci  donc d’être indulgent-e, ma marge de progression dans ce domaine étant immense… Merci à Serge L’homme qui m’a donné la formule pour le diamètre kilométrique et corrigé mon indice de Shimbel, merci enfin à Timothée Giraud qui est toujours disponible pour répondre à mes nombreuses (et souvent naïves) questions. J’en profite pour signaler leurs sites respectifs : site pédagogique de Serge Lhomme (http://serge.lhomme.pagesperso-orange.fr/) ; blog R géomatique de Timothée Giraud (http://rgeomatic.hypotheses.org/).

Les indices de Kansky

Soit e le nombre de liens, v le nombre de sommets et p le nombre de composantes connexes d’un graphe g, Kansky propose notamment les indices suivants :

  • nombre cyclomatique mu = e – v + p. Plus il est élevé, plus le réseau est dense ;
  • alpha : ratio entre le nombre de circuits présents et le nombre de circuits possibles : il varie entre 0 (arbre) et 1 (graphe complet) ;
  • beta : e/v. Une valeur inférieure à 1 signale un arbre, beta ne peut dépasser 3 pour un graphe planaire ;
  • gamma : ratio entre le nombre de liens présents et le nombre de liens possibles. Une formule est proposée pour les graphes planaires et une autre pour les graphes non planaires. Le terme densité employé dans les autres disciplines est synonyme ;
  • degré de connectivité : v*(v-1) * 1/2(e). Ratio entre le nombre de sommets et le nombre de liens (son interprétation m’échappe – mais je suis loin d’être un spécialiste des graphes planaires et des infrastructures de transport…) ;
  • indice de Shimbel : somme des toutes les distances entre les sommets. Peut être mesuré de façon topologique (distance mesurée en nombre de liens) ou pondéré (par une distance, un flux, une intensité etc.)
  • eta : distance moyenne des liens, exprimé généralement en kilomètres ;
  • pi : flux total divisé par le long des plus courts chemins kilométriques ;
  • theta : flux total divisé par le nombre de liens (intensité moyenne)
  • iota : distance totale divisée par le flux total

Trois fonctions R

Les données doivent avoir la forme suivante : un data.frame (tableau de données) ayant au minimum 3 colonnes : origine, destination et distance. Des colonnes peuvent être ajoutées pour porter des poids divers (flux de marchandises, débit horaire etc.). Cette liste de liens doit être transformée en objet igraph : le package igraph doit donc être appelé avant leur exécution (library(igraph)).

La fonction kansky_un mesure les indicateurs ne prenant pas en compte les poids et les distances : diamètre (topologique), nombre cyclomatique, indice alpha (planaire et non planaire), beta, gamma (planaire et non planaire), le degré de connectivité et l’indice de Shimbel (topologique).

La fonction kansky_di mesure les indicateurs prenant en compte une distance entre les sommets : diamètre (kilométrique), eta, pi et indice de Shimbel (pondéré). Le tableau en entrée doit impérativement avoir trois colonnes (origine, destination, distance).

La fonction kansky_df mesure les indicateurs prenant en compte une distance et une intensité entre les sommets : indices theta et iota. Si le tableau de départ ne comprend pas 4 colonnes minimum, un message  d’erreur apparaît.

Exemple reprenant une des figures utilisées par Kansky pour détailler le nombre cyclomatique (mu)

library(igraph)
d <- rbind(c(1,2), c(2,3), c(2,5), c(2,7), c(3,4),
             c(4,5), c(5,6),  c(6,7)) 
g <- graph.data.frame(d, directed = FALSE)
kansky_un(g)

Fonctions téléchargeables ici.

tnet : package R pour l’analyse de réseaux valués

La plupart des packages disponibles dans R permettent l’analyse de réseaux booléens (1 s’il existe une relation entre deux sommets i et j, 0 sinon) mais, si l’on souhaite étudier des réseaux valués (l’intensité des liens est variable entre les sommets), le choix est plus restreint. tnet est un package R maintenu par Tore Opsahl permettant l’analyse de réseaux valués simples et celle de réseaux bipartis et longitudinaux non valués. Le package est bien documenté, le site de Tore Opsahl est riche (http://toreopsahl.com/tnet/), cela méritait donc un billet un peu détaillé. Précision liminaire : tnet permet l’analyse mais non la visualisation des graphes, en effet, les objets manipulés par tnet sont de simples data.frame.

Je suppose pour la suite que R et le package tnet sont installés sur vos machines (voir les billets consacrés à R sur ce blog ou la foultitude de documentation disponible en français et en ligne sur le sujet).

Format des données et importation

Plusieurs jeux de données, classiques (le fameux Davis’ Southern Women Club) ou plus récents, sont disponibles dans tnet (voir la description détaillée sur la page http://toreopsahl.com/datasets/). Qu’on souhaite s’entraîner avec ou pas, il est intéressant d’y jeter un œil pour comprendre la structure des données. Elle est on ne peut plus simple : 3 colonnes origine – destination – intensité. Les attributs des sommets seront importés dans un fichier séparé. Si le réseau one-mode est non orienté, les liens devront être entrés deux fois (i-j et j-i). Les codes des sommets doivent être numériques et commencer par 1. La fonction as.tnet(jeu-de-données) permet de contrôler que la structure des données est correcte. Enfin, pour éviter la prise en compte des sommets isolés, la fonction compress_ids les supprime avant calcul.

Les fonctions se terminant par _w permettent l’analyse des réseaux valués (weighted), celles se terminant par _tm l’analyse des graphes bipartis (two-mode) et celles terminées par _l l’étude des réseaux longitudinaux.

Analyse des graphes valués one-mode

Le principe des mesures disponibles est simple : on fait varier un paramètre entre 0 – pas de prise en compte de l’intensité des liens – et 1 – prise en compte complète de l’intensité des liens. Il n’y a pas de recette miracle pour choisir le bon seuil et tout dépend de l’étendue des intensités : plus celle-ci  est grande, plus le paramètre devra être proche de zéro. Le petit graphe ci-dessous servira d’exemple pour cette partie :

tnet1

Pour le créer directement dans R :

rm(list=ls())
 library(tnet)
g <- rbind(c(1,2,3), c(2,1,3),
           c(1,3,4), c(3,1,4),
           c(2,3,1), c(3,2,1),
           c(3,4,2), c(4,3,2),
           c(4,5,1), c(5,4,1))

En pratique, mieux vaut évidemment importer ses données…

Les principales fonctions disponibles sont les suivantes :

degree_w(g) fournit un tableau à 3 colonnes : identifiant du sommet, degré et sommes des intensités des liens adjacents. Si je contrôle sur la figure, je vois par exemple que le sommet 3 a trois liens adjacents (degré) et que la somme des valeurs de ces trois liens est bien égale à 7 (4 + 2 + 1).

node degree output
 [1,] 1    2    7
 [2,] 2    2    4
 [3,] 3    3    7
 [4,] 4    2    3
 [5,] 5    1    1

closeness_w fournit un tableau de 3 colonnes : identifiant du sommet, centralité de proximité et centralité de proximité normalisée. La centralité mesurée ne repose pas sur le nombre de liens comme c’est le cas habituellement en analyse de réseau mais sur la somme des valeurs des liens parcourus. En d’autres termes, chaque intensité est assimilée à un coût et l’objectif est de trouver les chemins entre sommets minimisant ces coûts.

clustering_local_w et clustering_w fournissent les clustering coefficients locaux et globaux. Plusieurs prises en compte des intensités sont possibles avec l’argument measure = » ». Les principales options sont « am » (moyenne arithmétique, valeur par défaut de l’argument), « gm » (moyenne géométrique), « mi » et « ma » (respectivement minimum et maximum) et enfin « bi » (binaire). Dans ce dernier cas, l’intensité des liens n’est pas  utilisée.

D’autres fonctions et mesures sont disponibles (rich club coefficient global et local) mais il est fortement conseillé de relire attentivement les billets et articles de Tore Opsahl pour les utiliser à bon escient.

Analyse des graphes bipartis…

La structure des données est la même : origine – destination – intensité et, là encore, les deux ensembles de sommets doivent être numérotés de 1 à n. Attention donc à ne pas s’emmêler les pinceaux lors de la mise en forme… L’option type de la fonction as.tnet as.tnet(jeu-de-données, type= »weighted two-mode tnet ») – permet de contrôler la structure des données.

Les principales mesures disponibles sont la mesure de la distance (distance_tm()), le clustering coefficient global (clustering_tm()) et le clustering coefficient local (clustering_local-tm()). Là encore, mieux vaut relire d’abord ses articles et billets : ces mesures sont des propositions a priori pertinentes, ce ne sont pas (pas encore ?) des mesures communément utilisées.

… et analyse des réseaux longitudinaux

 Le package propose en tout en pour tout deux fonctions dont l’une (growth_l) qui prétend identifier les mécanismes responsables de l’apparition de liens entre  les sommets. Ayant à ce jour une connaissance fort limitée de l’analyse des réseaux longitudinaux,  je préfère ne pas m’avancer plus avant…

Dernier point : je déconseille en temps normal l’utilisation de packages développés et maintenus par une seule personne, le risque est en effet grand qu’il cesse brusquement d’être mis à jour avant de disparaître… Si je fais une exception pour celui-ci, c’est en grande partie due à la très grande qualité du site de Tore Opshal. Mais ce jeune homme (cf sa photo ici) travaillant dans le secteur privé, ne vous attachez quand même pas trop à son package….

 

 

L’analyse de réseaux avec R – un état des lieux (journée Semin-R du 24 mai 2013)

La courte présentation Beamer ci-dessous a été présentée à la journée Semin-R du 24 mai 2013 à Paris. Comme toujours, les commentaires – absents ici – permettent de nuancer ou de préciser le contenu des différentes diapositives. Il va de soi que cette présentation ne vise ni l’exhaustivité – je n’ai pas testé les 46 packages annoncés – ni l’objectivité. Elle  me semble pouvoir néanmoins servir d’introduction correcte au vaste champ de l’analyse de réseaux avec R.

Cliquer sur Crtl + L pour visualiser le diaporama (je n’ai pas encore trouvé l’astuce pour permettre l’affichage en plein écran…).

L’analyse de réseaux avec R, les premiers pas (deuxième partie)

Un premier billet publié début avril a présenté l’installation de R et de RStudio, le fonctionnement général du logiciel et a montré comment effectuer des mesures basiques sur un graphe à l’aide des packages statnet et igraph. L’objectif de ce billet est d’expliquer le plus simplement possible comment importer et transformer ses propres données et comment les visualiser. L’objectif de l’exercice est le suivant : importer un jeu de données comportant des attributs sur les liens et sur les sommets, puis de représenter le graphe en faisant dépendre la taille et la couleur des sommets de deux attributs et l’épaisseur des liens d’un troisième attribut.

Importer ses données

Les données proposées en exemple représentent un graphe fictif de relations entre enfants. Elles comportent deux fichiers : un fichier de type origine – destination – intensité concernant les liens non orientés existants, un fichier de type individus – variables qui précise les attributs de chacun des sommets (genre et âge). Pour télécharger le jeu de données et le script commenté dans ce billet, cliquer ici (les fichiers sont encodés en utf-8). En  règle générale, avec R, il est préférable pour limiter les risques d’erreurs d’importer des fichiers de format texte (.txt ou .csv).

La démarche à suivre est la même avec les deux packages : mettre en forme ses données, les importer dans R puis les transformer en un objet que statnet et igraph sont capables d’analyser. Détail important : ces deux packages ne permettent pas d’analyser des graphes valués (i.e. l’intensité des liens n’est pas prise en compte pour le calcul des indicateurs) mais, dans la représentation graphique, il est possible de faire varier l’épaisseur des liens en fonction de leur intensité.

Une fois vos fichiers placés dans un dossier, créez dans ce même dossier un fichier script.txt et changez l’extension pour obtenir script.R. Ouvrez-le ensuite avec RStudio.

Le début du script est le suivant :

rm(list=ls())
l <- read.table(« liens.txt », sep= »; », header=TRUE)
s <- read.table(« sommets.txt », sep= »; », header=TRUE, stringsAsFactors=FALSE)

La première ligne supprime tout les objets précédemment créés dans R, les deux lignes suivantes permettent l’importation des fichiers. Il convient de préciser leur nom, le caractère utilisé pour séparer les colonnes (sep= » »), éventuellement le caractère utilisé pour les décimales (dec= » ») et header=TRUE informe R que la première ligne contient les étiquettes de colonnes. L’option stringsAsFactors permet d’éviter que R ne transforme les caractères de la variable qualitative GENRE en facteur. Une fois les fichiers importés, vous pouvez les visualiser en cliquant sur eux dans la fenêtre Workspace. Il est toujours prudent, surtout lorsque l’on débute avec R, mais la règle reste valable ensuite, de vérifier avant toute opération que l’importation s’est bien déroulée.

Avec igraph

La transformation des données est relativement simple  avec igraph : la fonction graph.data.frame prend comme premier argument une liste de liens dont les deux premières colonnes doivent être les origines et les destinations. Les éventuelles colonnes supplémentaires seront considérées comme des attributs des liens. Les arguments suivants concernent la nature du graphe (orienté ou non notamment). Enfin, un argument vertices = permet d’importer les attributs des sommets. La ligne de code suivante permet donc de transformer nos deux fichiers en un objet igraph.

g <- graph.data.frame(l, directed=FALSE, vertices = s)

Pour la représentation, il faut d’abord définir les différents paramètres nécessaires et préciser les couleurs à utiliser, à quelle variable les attribuer, à quoi correspond la taille des sommets, l’épaisseur des liens etc. etc. Le code ci-dessous devrait vous donner la figure suivante – l’orientation des sommets pouvant être différente.

vertexCol <- get.vertex.attribute(g, »GENRE »)
colors = c(« Pink », »Blue »)
vertexCol[vertexCol == « F »] = colors[1]
vertexCol[vertexCol == « M »] = colors[2]

vertexSiz <- get.vertex.attribute(g, « AGE »)

edgeW <- get.edge.attribute(g, « INT »)

plot(g, vertex.color= vertexCol, vertex.size = vertexSiz,
      edge.width = edgeW)

Visualisation avec igraph

Avec statnet

La transformation en objet network analysable par statnet se fait à l’aide des commande as.matrix et as.network. Les noms sont explicites : as.matrix transforme une liste de liens en matrice ; as.network transforme la matrice en objet network. Donc, si vos données de départ sont au format matriciel, vous n’aurez pas besoin d’utiliser as.matrix… Dans la mesure où mes liens ne sont pas orientés, je le précise lors de la transformation avec l’option directed=FALSE. Je ne dois par contre prendre que les deux premières colonnes d’où les crochets et les parenthèses.

library(statnet)
ls <- as.network(as.matrix(l[,c(1:2)], directed=FALSE)
ls
gplot(ls)

La dernière étape consiste à transformer la dernière colonne du fichier l (intensité de la relation) et le fichier s (sommets) en données attributaires pour l’objet network ls créé à l’étape précédente. Cela se fait avec l’assignation %v% pour les sommets (v comme vertex) et %e% pour les liens (e comme edge).

ls %v% « GENRE » <- s$GENRE  
ls %v% « AGE » <- s$AGE
ls %e% « int » <- l$INT

Pour la  représentation graphique, il faut d’abord définir les couleurs à utiliser puis visualiser avec la fonction gplot. Cette fonction propose un très grand nombre d’options, le plus simple est de taper ?gplot puis de tester les différents scripts d’exemple. Bizarrement, il faut faire appel aux tableaux de départ et non à l’objet network pour personnaliser la visualisation. Les options utilisées ici sont les suivantes : gmode = « graph » signale que le graphe est non orienté ( = « digraph » dans le cas contraire) ; displaylabels permet d’afficher ou non les labels des sommets, vertex.col et vertex.cex permettent de choisir couleur et taille des sommets et enfin edge.lwd permet de moduler l’épaisseur des liens.

nodeColors <- ifelse(s$GENRE== »F », »Pink », »Blue »)

gplot(ls, gmode= »graph », displaylabels=TRUE, vertex.col=nodeColors,
      vertex.cex= s$AGE/4, edge.lwd = l$INT)

Le résultat obtenu ressemble – à l’orientation générale de la figure près – à ceci :

 Visualisation avec statnet

En guise de conclusion

Le premier billet vous a – théoriquement – permis d’installer R, RStudio et de tester différente mesures de graphe à l’aide des packages statnet et igraph. Vous savez maintenant importer vos données (liens et attributs) et visualiser vos graphes en fonction des attributs importés, vous êtes donc quasi autonomes. Un dernier conseil pour finir : prenez toujours le temps de bien parcourir les rubriques d’aide des fonctions.