1.4 TP – Package igraph

Le but de ce TP est de se familiariser avec le package igraph de R.

Tutoriels sur igraph: http://igraph.org/r/

Pour les curieux, si vous souhaitez connaitre encore plus de fonctions proposées par igraph, vous pouvez regardez ce tutoriel: http://kateto.net/networks-r-igraph

Les données utilisées dans ce TP sont disponibles sur en ligne.

Package igraph

Installer le package igraph

install.packages("igraph")

Chargez la library igraph:

library(igraph)

Créer un graphe à la main

en donnant une liste d’arêtes

listAretes <- c(1,2, 1,3, 2,3, 3,5, 2,4, 4,5, 5,6, 4,6, 4,7, 6,7)
g1 <- graph(edges=listAretes, directed=FALSE)
plot(g1)

La liste d’arêtes est en format de vecteur ou de matrice à deux lignes.

On obtient un graphe de type igraph:

class(g1)
## [1] "igraph"

En indiquant le nombre \(n\) de noeuds du graphe:

g2 <- graph(edges=listAretes, n=9, directed=FALSE)
plot(g2)

Les noeuds ne sont pas nécessairement de type numerique:

listAretesNom <- c("Eric", "Erwan", "Erwan","Ana")
g3 <- graph(edges=listAretesNom)
plot(g3)

Avec des noeuds isolés:

g4 <- graph(edges=listAretesNom, isolates="Paul")
plot(g4)

en important un data.frame contenant la liste d’arêtes:

Fichier de données disponible sur le site: http://www.sociopatterns.org/datasets/high-school-contact-and-friendship-networks/

Données concernant les relations entre étudiants.

friends <- read.table(file='Friendship-network_data_2013.csv')
head(friends)
##   V1  V2
## 1  1  55
## 2  1 205
## 3  1 272
## 4  1 494
## 5  1 779
## 6  1 894
amis <- graph_from_data_frame(friends, directed=TRUE) 
amis
## IGRAPH 81942b8 DN-- 134 668 -- 
## + attr: name (v/c)
## + edges from 81942b8 (vertex names):
##  [1] 1 ->55  1 ->205 1 ->272 1 ->494 1 ->779 1 ->894 3 ->1   3 ->28  3 ->147
## [10] 3 ->272 3 ->407 3 ->674 3 ->884 27->63  27->173 28->202 28->327 28->353
## [19] 28->407 28->429 28->441 28->492 28->545 32->440 32->624 32->797 32->920
## [28] 34->151 34->277 34->502 34->866 45->48  45->79  45->335 45->496 45->601
## [37] 45->674 45->765 46->117 46->196 46->257 46->268 48->45  48->79  48->496
## [46] 55->1   55->170 55->205 55->252 55->272 55->779 55->883 55->894 61->797
## [55] 63->27  63->125 63->173 70->101 70->132 70->240 70->425 70->447 72->407
## [64] 72->674 72->857 79->45  79->48  79->335 79->496 79->601 79->674 79->765
## + ... omitted several edges
class(amis)
## [1] "igraph"
plot(amis)

ou en important plusieurs data.frame:

Données concernant les médias:

nodes <- read.csv("Dataset1-Media-Example-NODES.csv", header=TRUE, as.is=TRUE)
head(nodes)
##    id               media media.type type.label audience.size
## 1 s01            NY Times          1  Newspaper            20
## 2 s02     Washington Post          1  Newspaper            25
## 3 s03 Wall Street Journal          1  Newspaper            30
## 4 s04           USA Today          1  Newspaper            32
## 5 s05            LA Times          1  Newspaper            20
## 6 s06       New York Post          1  Newspaper            50
links <- read.csv("Dataset1-Media-Example-EDGES.csv", header=TRUE, as.is=TRUE)
head(links)
##   from  to weight      type
## 1  s01 s02     10 hyperlink
## 2  s01 s02     12 hyperlink
## 3  s01 s03     22 hyperlink
## 4  s01 s04     21 hyperlink
## 5  s04 s11     22   mention
## 6  s05 s15     21   mention
net <- graph_from_data_frame(d=links, vertices=nodes, directed=TRUE) 
class(net)
## [1] "igraph"
plot(net)

à partir d’un fichier dont le format est adapté à igraph

La fonction read_graph adaptée à certains formats de graphe:

read_graph(file, format = c("edgelist", "pajek", "ncol", "lgl", "graphml", "dimacs", "graphdb", "gml", "dl"), ...)

Graphe des personnages des Misérables: lien si co-occurrence dans un chapitre The file lesmis.gml contains the weighted network of coappearances of characters in Victor Hugo’s novel Les Miserables. Nodes represent characters as indicated by the labels and edges connect any pair of characters that appear in the same chapter of the book. The values on the edges are the number of such coappearances. http://www-personal.umich.edu/~mejn/netdata/

miserab <- read_graph(file='lesmis.gml', format="gml") 
class(miserab)
## [1] "igraph"
plot(miserab)

en important une matrice d’adjacence

C’est plus rare, mais possible: créer un graphe à partir d’une matrice d’adjacence:

A <- matrix(c(0,0,0,0,0,0,1,1,0,1,0,1,0,1,1,0), 4, 4)
A
##      [,1] [,2] [,3] [,4]
## [1,]    0    0    0    0
## [2,]    0    0    1    1
## [3,]    0    1    0    1
## [4,]    0    1    1    0
plot(graph_from_adjacency_matrix(A, mode='undirected'))

Matrice d’adjacence

On peut convertir un graphe en matrice d’adjacence:

Aamis <- as_adj(amis)
dim(Aamis)
## [1] 134 134

Attention, par défaut, as_adj crée une matrice sparse et certaines opérations classiques ne sont pas possibles:

is.matrix(Aamis)
## [1] FALSE
class(Aamis)
## [1] "dgCMatrix"
## attr(,"package")
## [1] "Matrix"
t(Aamis)
## Error in t.default(Aamis): l'argument n'est pas une matrice

Pour y remédier, il suffit d’utliser l’option sparse=FALSE:

Aamis <- as_adj(amis, sparse=FALSE)
is.matrix(Aamis)
## [1] TRUE

Propiétés de base d’un graphe

Familiarisez vous avec les fonctions suivantes en les appliquant sur les graphes crées ci-dessus. Prenez l’habitude d’utiliser la documentation du package (help()) et de la LIRE !

vcount()
ecount()
V()
E()
is.directed()

Visualisation de graphes

Network layouts: algorithmes usuels de visualisation

Référence pour les différentes visualisations http://igraph.org/c/doc/igraph-Layout.html Attention, les fonctions proposées sont parfois obsolètes. Se référer à l’aide de igraph.

plot(amis)

plot(amis, layout=layout_as_star)

plot(amis, layout=layout.circle)

plot(amis, layout=layout_randomly)

Deux algorithmes de visualisation populaires pour avoir des visulatisations jugées “esthétiques”. Si vous souhaitez plus d’infos: https://halshs.archives-ouvertes.fr/halshs-00839905/document

plot(amis, layout=layout.fruchterman.reingold)

plot(amis, layout=layout.kamada.kawai)

Embellir ses figures avec igraph

Pour voir toutes les option de plot() tapez ?igraph.plotting.

Les options les plus courantes sont les suivantes:

  • vertex.color, vertex.shape, vertex.size, vertex.label coleur, forme, taille et étiquettes des noeuds
  • edge.color, edge.label couleur et étiquettes des arêtes
plot(net)

plot(net, edge.arrow.size=.4)

plot(net, vertex.color="orange", edge.color="blue", vertex.label.color="black", edge.arrow.size=.4)

Si on veut utiliser des infos supplémentaires pour colorier les noeuds en fonction du type de média, la taille des noeuds en fonction de l’audience, l’épaisseur des arêtes en fonction de leur poids… On trouve ces infos ici:

vertex_attr(net)
## $name
##  [1] "s01" "s02" "s03" "s04" "s05" "s06" "s07" "s08" "s09" "s10" "s11" "s12"
## [13] "s13" "s14" "s15" "s16" "s17"
## 
## $media
##  [1] "NY Times"            "Washington Post"     "Wall Street Journal"
##  [4] "USA Today"           "LA Times"            "New York Post"      
##  [7] "CNN"                 "MSNBC"               "FOX News"           
## [10] "ABC"                 "BBC"                 "Yahoo News"         
## [13] "Google News"         "Reuters.com"         "NYTimes.com"        
## [16] "WashingtonPost.com"  "AOL.com"            
## 
## $media.type
##  [1] 1 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 3
## 
## $type.label
##  [1] "Newspaper" "Newspaper" "Newspaper" "Newspaper" "Newspaper" "Newspaper"
##  [7] "TV"        "TV"        "TV"        "TV"        "TV"        "Online"   
## [13] "Online"    "Online"    "Online"    "Online"    "Online"   
## 
## $audience.size
##  [1] 20 25 30 32 20 50 56 34 60 23 34 33 23 12 24 28 33
V(net)$media
##  [1] "NY Times"            "Washington Post"     "Wall Street Journal"
##  [4] "USA Today"           "LA Times"            "New York Post"      
##  [7] "CNN"                 "MSNBC"               "FOX News"           
## [10] "ABC"                 "BBC"                 "Yahoo News"         
## [13] "Google News"         "Reuters.com"         "NYTimes.com"        
## [16] "WashingtonPost.com"  "AOL.com"
edge_attr(net)
## $weight
##  [1] 10 12 22 21 22 21 21 11 12 22 23 20 11 11 21 23 21 21 21 22 21 21 21 23 21
## [26] 22 22 21 21  2  5  1  1  2  2  3  1  1  1  1  2  2  4  2  4  4  4  1  1  1
## [51]  1  1
## 
## $type
##  [1] "hyperlink" "hyperlink" "hyperlink" "hyperlink" "mention"   "mention"  
##  [7] "mention"   "mention"   "mention"   "hyperlink" "hyperlink" "mention"  
## [13] "hyperlink" "hyperlink" "mention"   "hyperlink" "hyperlink" "mention"  
## [19] "mention"   "mention"   "hyperlink" "hyperlink" "hyperlink" "hyperlink"
## [25] "hyperlink" "hyperlink" "mention"   "mention"   "hyperlink" "hyperlink"
## [31] "hyperlink" "hyperlink" "mention"   "hyperlink" "mention"   "hyperlink"
## [37] "mention"   "hyperlink" "mention"   "hyperlink" "mention"   "mention"  
## [43] "hyperlink" "hyperlink" "hyperlink" "mention"   "hyperlink" "hyperlink"
## [49] "mention"   "hyperlink" "hyperlink" "mention"
plot(net, vertex.label=V(net)$media, edge.arrow.size=.4)

plot(net, vertex.label=V(net)$media, edge.arrow.size=.4, vertex.color=V(net)$media.type)

plot(net, vertex.label=V(net)$media, edge.arrow.size=.4, vertex.color=V(net)$media.type, vertex.size=V(net)$audience.size)

plot(net, vertex.label=V(net)$media, vertex.color=V(net)$media.type, vertex.size=V(net)$audience.size, edge.width=E(net)$weight)

Exercice 1

Cherchez sur le web des graphes et importez-les sur votre machine (vous garderez l’adresse de récupération des données en commentaire dans votre fichier). Variez les formats d’origine si vous pouvez, et le type de graphe (dirigé ou non). Déterminer l’ordre et la taille des graphes et visualiser-les.

Voici une liste de serveurs proposant des données réelles de graphes: