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.

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.

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.

Communautés, QGIS, R (igraph) et Python…

Toujours dans la continuité des billets précédents (billet 1) (billet 2) qui présentent des plugins d’analyse de réseaux spatiaux, ce billet présente un plugin permettant d’identifier des communautés au sein de ces réseaux. En effet, ce billet permet d’aborder d’une part un sujet important de l’analyse de réseaux, l’identification de communautés, et d’autre part les relations possibles entre R et QGIS via Python, puisque la bibliothèque choisie pour ces analyses est igraph.

igraph, qui est un package réputé sous R pour l’analyse de réseaux, dispose d’une extension Python. Dans un premier temps, il s’agit d’utiliser cette extension qui permet de travailler sous QGIS avec igraph et ce indépendamment de R. Pour utiliser igraph avec Python et par conséquent QGIS, c’est néanmoins un peu plus compliqué qu’avec NetworkX, car il faut cette fois-ci compiler la bibliothèque en question. Le plus simple consiste à télécharger l’installateur Windows pour Python 2.7 (http://igraph.sourceforge.net/download.html). Une fois l’installateur lancé, il suffit de bien préciser l’emplacement de Python dans QGIS « C:/Program Files/Quantum GIS Lisboa/apps/Python27 ». Normalement, dès le premier lancement de QGIS, tout fonctionne. Il est alors possible d’importer igraph via la console Python de QGIS.

Exemple de test du fonctionnement de IGraph sous QGIS via la console Python.

Exemple de test du fonctionnement de IGraph sous QGIS via la console Python.

Il convient ensuite de télécharger le nouveau plugin (cliquer ici pour l’obtenir). Il faut le dézipper, puis placer le dossier dans le répertoire suivant : « C:\Program Files\Quantum GIS Lisboa\apps\qgis\python\plugins ». Il suffit alors de lancer QGIS pour que le plugin apparaisse dans « Extension -> Analyse de Graphe… -> Detection de communautes ». S’il n’apparaît pas, il faut aller dans « Extension -> Gestionnaire d’extensions » et cocher l’extension « Detection de communautes (version 0.1) ». Après avoir lancé le plugin, une boîte de dialogue s’ouvre. Elle permet de sélectionner les nœuds et les arcs du graphe à étudier. Après avoir validé cette première boîte de dialogue, une deuxième boîte de dialogue apparaît. Elle permet de sélectionner les champs des extrémités des arcs, de préciser si le graphe est orienté ou non, de préciser si le graphe est pondéré ou non (et si oui, quel est le champ de cette pondération : distance, flux, importance…). Enfin, différents algorithmes sont proposés afin d’identifier les communautés au sein du réseau étudié.

Présentation de la deuxième boite de dialogue.

Présentation de la deuxième boite de dialogue.

Les différents algorithmes proposés par le plugin utilisant igraph sont les suivants :

  • Walktrap, algorithme développé par Latapy et Pons et fondé sur des marches aléatoires ;
  • Betweenness, algorithme fondé sur la centralité des arcs. Les arcs les plus centraux sont retirés progressivement, chaque nouvelle composante connexe définissant alors une nouvelle communauté ;
  • Multilevel, algorithme fonctionnant par agrégation de nœuds à une communauté afin d’améliorer la modularité ;
  • Eigenvector, algorithme séparant progressivement les communautés à partir des valeurs propres du graphe ;
  • Infomap, deuxième algorithme fondé sur des marches aléatoires.

Pour chaque algorithme, seule la solution optimale est retenue (c’est-à-dire celle offrant la modularité la plus forte). C’est pourquoi le nombre de communautés n’est pas demandé avant le calcul. La valeur finale de la modularité est indiquée afin de comparer les résultats obtenus par les différents algorithmes. Une fois le calcul terminé, les valeurs stockées correspondent aux communautés auxquelles appartiennent les nœuds. Il est alors possible d’afficher ces communautés :

Communautés issues de l’algorithme fondé sur la centralité des arcs.

Communautés issues de l’algorithme fondé sur la centralité des arcs.

Le fait d’utiliser l’extension Python de igraph interrogera sans doute quelques utilisateurs invétérés de R. Faut-il recoder en Python tous ses codes R et trouver une extension Python pour éventuellement les utiliser sous QGIS ? La réponse est non, puisqu’il est possible de faire interagir QGIS et R à l’aide notamment de la bibliothèque RPy. En effet, RPy est une interface Python pour R. Ainsi, cette interface permet en utilisant le langage Python d’interagir avec R et de bénéficier de l’ensemble des développements réalisés sous R. L’inverse est aussi possible. Pour cela, il faut repartir pour une opération de téléchargement (http://sourceforge.net/projects/rpy/files/OldFiles/) et de compilation. En partant du principe que le package igraph est bien installé sous R (il faut notamment vérifier sa présence dans « C:\Program Files\R\R-(x.xx.x)\library\ »), il est très simple d’exécuter des codes R sous QGIS et par conséquent de les exploiter. Par exemple, on va exécuter à partir de QGIS le code R suivant :

test <- function () {
library(igraph)
g <- barabasi.game(100,m=2)
eb <- edge.betweenness.community(g)
return(eb$bridges)
}

Ce code peut être sauvegardé comme étant le fichier test.r. Pour appeler ce fichier sous QGIS, il est possible d’utiliser la console Python de QGIS. Plus précisément, il suffit de taper les lignes de code suivantes :

>>> from rpy import * # Import de la bibliothèque Rpy
>>> r.source('C:/Users/serge.lhomme/Documents/R/test.r') # Chargement du fichier test.r
{'visible': False, 'value': <Robj object at 0x0CBBDA00>}
>>> resultat=r.test() # Exécution de la fonction test
Message d'avis :
package 'igraph' was built under R version 2.12.2
>>> resultat # Affichage du résultat
[198.0, 196.0, 194.0, 192.0, 190.0, 188.0, 186.0, 184.0, 182.0, 180.0, 178.0, 176.0, 174.0, 
172.0, 170.0, 169.0, 168.0, 167.0, 166.0, 165.0, 164.0, 163.0, 162.0, 161.0, 160.0, 159.0, 
158.0, 157.0, 156.0, 155.0, 154.0, 153.0, 151.0, 150.0, 149.0, 148.0, 147.0, 145.0, 144.0, 
143.0, 140.0, 138.0, 137.0, 136.0, 135.0, 134.0, 133.0, 132.0, 131.0, 130.0, 128.0, 126.0, 
124.0, 122.0, 121.0, 119.0, 118.0, 117.0, 115.0, 114.0, 112.0, 111.0, 110.0, 109.0, 108.0, 
106.0, 105.0, 104.0, 102.0, 101.0, 100.0, 98.0, 96.0, 94.0, 92.0, 90.0, 89.0, 87.0, 85.0, 
83.0, 81.0, 79.0, 77.0, 75.0, 73.0, 71.0, 69.0, 67.0, 65.0, 64.0, 62.0, 61.0, 59.0, 57.0, 
56.0, 52.0, 51.0, 47.0, 45.0]

A partir de ces simples commandes, il est possible d’appliquer ses codes R sous QGIS. Ce qui sera sans doute utile pour certains et ce qui augmente encore les possibilités offertes par QGIS.

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

L’analyse de réseaux avec R, les premiers pas

R est un logiciel libre, multiplateforme et qui permet de réaliser à peu près tous les traitements de données possibles dont, bien entendu, l’analyse de réseaux. Seul inconvénient, il fonctionne à l’aide de scripts et nécessite donc l’apprentissage d’un langage particulier. Pourquoi alors l’utiliser ? Parce qu’il s’agit d’un logiciel très puissant, qu’il permet de tout faire, et surtout parce que, une fois le langage maîtrisé, il permet de gagner un temps fou. Une fois le script écrit, obtenir toute une série de mesures sur un graphe prend quelques secondes alors que la même opération avec un logiciel presse boutons nécessite quelques dizaines de clics… Ce billet s’adresse aux personnes tentées par R mais qui n’osent pas encore franchir le pas.

La première partie explique comment installer R, l’interface RStudio (et son utilité), comment charger les modules (packages) d’analyse de réseaux et le fonctionnement de l’aide. La deuxième partie montre quelques manipulations basiques sur les graphes fournis en exemple avec les modules. Un second billet détaillera les procédures d’importation de ses propres données (sommets, liens et attributs) et les possibilités graphiques du logiciel (mise en ligne prévue pour fin avril).

Installer R et RStudio

Première étape : se rendre sur le site http://cran.r-project.org/ et télécharger la version de R compatible avec votre système d’exploitation. Puis se rendre sur le site http://www.rstudio.com/ et télécharger la dernière version de RStudio. RStudio est une interface graphique qui facilite l’utilisation de R en rendant un certain nombre de fonctions (rubriques d’aide, actualisation des modules etc.) beaucoup plus simples à utiliser. Elle n’est pas indispensable mais elle est fortement recommandée quand on débute avec R.

Une fois les deux logiciels téléchargés, installez-les (sous Windows, clic droit et exécuter en temps qu’administrateur). Les choix proposés par défaut sont généralement pertinents, vous pouvez donc les laisser. Lancer ensuite RStudio et vous obtenez une fenêtre de ce type (la capture a été effectuée sous environnement Windows 7, RStudio version 0.97.336). Quatre fenêtres sont ouvertes : celle en haut à gauche accueille les scripts, c’est-à-dire la suite d’instructions que vous allez exécuter ; les résultats apparaîtront dans la fenêtre en bas à gauche appelée la console. La fenêtre en haut à droite liste les jeux de données utilisés et l’historique des manipulations effectuées. Enfin, la fenêtre en bas à droite héberge les rubriques d’aide, les sorties graphiques et la liste des packages installés.

Interface de RStudio

Charger un package

R est un logiciel modulaire. Certains modules sont inclus par défaut lors de l’installation du logiciel, d’autres plus spécifiques doivent être installés. Pour débuter en analyse de réseaux, deux modules sont indispensables : le package statnet (qui est en réalité un ensemble de packages dépendants les uns des autres) et le package igraph. D’autres packages existent et plusieurs billets de ce blog en présentent certains (voir les billets sur le module intergraph, le module bipartite, le module QuACN ou le module qgraph).

statnet et igraph sont des packages inclus dans la version de base de R mais ils ne sont pas actifs au démarrage. Il convient donc de les charger à l’aide des fonctions library(statnet) et library(igraph). Attention, mais j’y reviendrai pas la suite, ces deux packages ne peuvent pas fonctionner ensemble. Pour exécuter une fonction, deux possibilités existent : la taper directement dans la console puis taper Entrée ; la taper dans un script et taper Ctrl + Entrée pour l’exécuter. Le résultat est exactement le même. Mais tout l’intérêt de R est de créer des scripts (des suites de commandes) qui peuvent être sauvegardés (ce sont de simples fichiers texte ayant l’extension .R) et réutilisés ensuite. Une bonne habitude est donc, à l’ouverture de RStudio, de créer un nouveau script à l’aide des menus déroulants File > Create new R script. Le menu File permet de créer les scripts, de les sauvegarder à l’endroit de son choix, de les ouvrir etc.

Créer un script avec RStudio

Au fait, pourquoi deux packages ? statnet est développé par des sociologues férus de modèles statistiques (ERGM) ; igraph est développé par des physiciens et des informaticiens. On trouve dans les deux les mesures les plus communes en analyse de réseaux mais certaines ne sont proposées que dans l’un de ces deux packages. Par ailleurs, la simplicité des commandes et la clarté des résultats varie d’un package à l’autre. A titre personnel, l’importation des données attributaires me semble beaucoup plus simple avec igraph mais je préfère les visualisations proposées par statnet. Mais ceci est affaire de goût… Autre avantage d’utiliser deux packages, ce qu’on ne parvient pas à faire avec l’un,  on réussit généralement à le faire avec l’autre.

Les rubriques d’aide

Dans RStudio, lorsque que vous chargez un package à l’aide de la commande library(nom_du_package), l’aide s’affiche dans un onglet de la fenêtre Help. Si vous avez besoin de savoir comment fonctionne une instruction, il suffit de la taper dans la console, de taper Ctrl + Entrée et la rubrique s’affiche alors dans la fenêtre Help. Quand les créateurs et/ou créatrices du package ont fait du bon boulot, vous trouvez une définition de la fonction, sa structure (éléments indispensables et optionnels), les éléments pris en entrée et ceux fournis en sortie et enfin un exemple d’utilisation. La rédaction de la documentation étant en grande partie normée, ces rubriques sont généralement de bonne qualité (mais en anglais évidemment…).

Aide d'igraph dans RStudio

Les rubriques d’aide sont  – avec les forums et listes de diffusion consacrés à R – sont vos meilleurs alliés pour progresser rapidement. Lorsque que vous utilisez un package pour la première fois, prendre le temps de regarder les différentes fonctions, d’examiner les jeux de données disponibles, de tester les scripts d’exemple proposés vous fera gagner un temps précieux.

Mais il est temps d’entrer dans le vif du sujet… La suite du billet suppose que vous avez installé R et RStudio… et c’est tout.

Pour les deux packages, les manipulations proposées sont les suivantes : chargement d’un jeu de données, calcul de la densité du graphe, du nombre et de la taille des composantes connexes, et enfin calcul de deux mesures de centralités des sommets (degré et intermédiarité, soit en bon anglais degree et betweenness). Comme indiqué plus haut, les aspects liés à la visualisation et à l’importation de ses propres billets seront abordés dans un second billet.

Manipulations basiques avec statnet

Le petit texte qui suit est un script, c’est-à-dire une liste d’instructions. Les étapes sont toujours les mêmes : nettoyer l’espace de travail (rm = remove), charger le package, charger un jeu de données puis effectuer les opérations souhaitées sur ce jeu de données. Quand on débute (et même après), il est vivement conseillé de commenter ses scripts : il suffit de placer un croisillon (AltGr + 3 sur Windows, Maj + @ sur Mac). Et c’est bien un croisillon et non un dièse1…) et ce qui est tapé ensuite n’est pas pris en compte par le logiciel.

Plusieurs jeux de données sont fournis avec statnet et l’exemple proposé ici utilise le jeu de données nommé faux.magnolia.high. Ce graphe simule les liens d’amitiés sur un campus américain (pour obtenir plus d’informations, taper ?faux.magnolia.high dans la console, Entrée et les détails s’affichent dans la fenêtre Help).

rm(list=ls()) #supprimer tous les objets importés ou créés auparavant
library(statnet) #chargement du package  statnet
data(« faux.magnolia.high ») #chargement du jeu de données
g <- faux.magnolia.high #attribution d’un nom court (facilite la saisie)
g  #informations de base sur le graphe

Taper le nom de l’objet g permet d’obtenir les informations suivantes : nombre de sommets (vertices = 1461), caractéristiques du graphe (ici on apprend qu’il est non-orienté, non multiple, ne comprend pas de boucles et qu’il ne s’agit pas d’un hypergraphe : directed = FALSE hyper = FALSE loops = FALSE multiple = FALSE bipartite = FALSE). On apprend enfin qu’il comprend 974 liens et qu’il n’y a pas de données manquantes (total edges= 974 missing edges= 0 non-missing edges= 974). Dernier point, mais qui ne sera pas utilisé dans ce billet, l’existence d’attributs (sur les sommets et/ou les liens) est indiqué : chaque sommet comprend un nom et des indications portant sur le niveau scolaire, le genre et l’ethnie (Vertex attribute names: Grade Race Sex vertex.names).

gden(g) #calcul de la densité
component.dist(g) #nombre et compositions des composantes connexes

Cette dernière fonction crée trois objets différents : un objet membership qui précise pour chaque sommet la composante connexe à laquelle il appartient ; un objet csize (component size) qui donne la taille de chacune des composantes connexes ; un objet cdist qui décrit la distribution des tailles des composantes connexes. Si je souhaite utiliser ces résultats ensuite – et la remarque s’applique aux opérations suivantes – j’ai tout intérêt à créer un objet qui va stocker ces résultats et me permettre de les réutiliser ensuite. La procédure est simple, je fais précéder l’instruction d’un nom (prendre un nom explicite est recommandé) et du petit symbole <-, ce qui donne la ligne de commande suivante. Les résultats ne s’affichent pas dans la console mais sont stockés – et réutilisables – dans l’objet comp.connexe.

comp.connexe <- component.dist(g)
deg <- degree(g) #calcul des degrés
summary(deg) #informations sur les degrés (min, Q1, médiane, moyenne, Q3 et max)
bet <- betweenness(g) #calcul de la centralité d’intermédiarité
summary(bet) #informations sur la centralité d’intermédiarité
tab <- as.data.frame(cbind(g$vertex.names, deg, bet)) #création d’un tableau

Cette dernière ligne appelle un petit commentaire : je crée un tableau de données (as.data.frame) qui consiste à coller côte à côte 3 colonnes (cbind), ces 3 colonnes étant le nom des sommets (g$vertex.names), leur degré (deg) et leur centralité d’intermédiarité (bet). Cette étape n’est pas obligatoire mais on peut préférer stocker tous les résultats concernant les sommets dans un même tableau plutôt que de multiplier les objets à manipuler.

Manipulations basiques avec igraph

Le mini-script qui suit réplique la même suite d’opérations mais avec le package igraph (et avec un jeu de données différent, le fameux Zachary karate club dataset). Comme vous le verrez, les noms des fonctions se ressemblent parfois fortement. Mais, statnet et igraph ne pouvant être utilisés de façon simultanée, il convient tout d’abord de détacher le package statnet puis de charger le package igraph.

rm(list=ls()) #nettoyer l’espace de travail
detach(package:statnet) #détacher le package statnet
library(igraph) #charger le package igraph
library(igraphdata)#charger les jeux de données du package igraph
data(karate) #charger le jeu de données du Zachary karate club
g <- karate #lui donner un nom plus court
g #principales propriétés

Taper g donne le résultat suivant : IGRAPH U-W- 34 78 — Zachary’s karate club network + attr: name (g/c), Citation (g/c), Author (g/c), Faction (v/n), weight (e/n). Ce qui en termes compréhensibles se traduit de la manière suivante : le graphe est non-orienté (U undirected) et valué (W weighted), il comprend 34 sommets et 78 liens, son nom est Zachary’s karate club network et il comprend un certain nombre d’attributs : sur le graphe (g : nom, auteur et citation), sur les sommets (v comme vertex ) et sur les lien (e comme edge).

graph.density(g) #densité du graphe
comp.connexe <- clusters(g) # composantes connexes

La fonction clusters crée trois objets : un objet membership qui indique à quelle composante appartient chaque sommet ; un objet csize indiquant la taille des composantes connexes et enfin un objet no donnant le nombre de composantes connexes. Le graphe étant ici connexe, les résultats de cette commande sont d’un intérêt relatif.

deg <- degree(g) #degré des sommets
bet <- betweenness(g) #centralité d’intermédiarité
tab <- as.data.frame(cbind(deg, bet)) #création d’un tableau
head(tab,10) #examen des 10 premières lignes du tableau

Et c’est tout pour aujourd’hui… Dernier conseil pour finir : avec R, il est important de prendre son temps et d’examiner les problèmes de manière séquentielle. Si vous abordez R pour la première fois, vous ne pouvez pas en deux heures apprendre à importer vos données, à lancer et interpréter un modèle ERGM puis à produire une superbe visualisation. Mais, avec des recours réguliers aux rubriques d’aide, de petits scripts (abondamment commentés) que vous enrichissez au fur et à mesure (j’ai créé un tableau avec 2 indicateurs, il est facile d’en ajouter…), votre progression sera rapide et efficace.

Ressources en ligne

Ayant déjà souvent écrit sur l’analyse de réseaux avec R – et je ne compte pas m’arrêter là -, je me permets de renvoyer à ce billet publié il y a quelques mois.

1 Robin Cura est la personne  qui m’a permis de comprendre l’étendue de mon ignorance sur cet aspect crucial. Et il a évidemment raison : ♯ est un dièse, # est un croisillon….