Chapitre 1 Manipulation de graphes avec igraph
Le but de ce tutoriel est de se familiariser avec les principales fonctions du package igraph. On trouvera un descriptif de ce package à l’adresse http://igraph.org/r/. On pourra également consulter le tutoriel (très complet) suivant : http://kateto.net/networks-r-igraph.
Nous commençons par charger le package
1.1 Construction de graphes avec igraph
Comme pour des données classiques, il est possible de construire des graphes directement dans R ou de les importer à partir de fichiers externes.
1.1.1 Quelques fonctions R pour construire des graphes
L’approcher la plus naturelle est de définir un graphe à partir d’une liste d’arêtes :
Si la liste d’arêtes est donnée sous forme de noms, il n’est pas nécessaire d’indiquer le nombre de nœuds.
Différentes options sont proposées dans la fonction graph :
n
: le nombre maximal de nœudsisolates
: ajout de nœuds isolésdirected
: graphes dirigés ou non- …
Par exemple
Il existe également des fonctions spécifiques qui peuvent aider à la construction de graphes, par exemple make_full_graph :
Il est également possible “d’additionner” des graphes
L’opérateur pipe permet une lecture du code plus lisible
Il est également facile d’ajouter des arêtes avec add_edges :
Exercice 1.1 (Quelques graphes spécifiques) Tester et expliquer les fonctions make_empty_graph, make_ring et make_star.
On remarque que :
- make_empty_graph produit un graphe sans arête ;
- make_ring donne un graphe en cercle ;
- make_star donne un graphe en étoile : tous les nœuds sont connectés à un même nœud.
1.1.2 Construction à partir d’un fichier externe
Le plus souvent, on aura à récupérer des données récoltées dans des fichiers txt
ou csv
pour construire le graphe.
Exercice 1.2 (Importation) On considère le jeu de données Friendship-network_data_2013.csv qui se trouve sur le site http://www.sociopatterns.org/datasets/high-school-contact-and-friendship-networks/. Ces données concernent des relations entre étudiants.
Importer les données à l’aide de read.table.
Ce fichier contient 2 colonnes et chaque colonne contient une arête. Visualiser le graphe. On pourra utiliser graph_from_data_frame.
amis <- graph_from_data_frame(friends,directed=T) amis IGRAPH de22539 DN-- 134 668 -- + attr: name (v/c) + edges from de22539 (vertex names): [1] 1 ->55 1 ->205 1 ->272 1 ->494 1 ->779 1 ->894 3 ->1 [8] 3 ->28 3 ->147 3 ->272 3 ->407 3 ->674 3 ->884 27->63 [15] 27->173 28->202 28->327 28->353 28->407 28->429 28->441 [22] 28->492 28->545 32->440 32->624 32->797 32->920 34->151 [29] 34->277 34->502 34->866 45->48 45->79 45->335 45->496 [36] 45->601 45->674 45->765 46->117 46->196 46->257 46->268 [43] 48->45 48->79 48->496 55->1 55->170 55->205 55->252 [50] 55->272 55->779 55->883 55->894 61->797 63->27 63->125 + ... omitted several edges plot(amis)
On considère un graphe permettant de visualiser des connexions entre médias :
- les nœuds sont définis dans le fichier
Dataset1-Media-Example-NODES.csv
- les arêtes dans le fichier
Dataset1-Media-Example-EDGES.csv
.
Importer ces fichiers.
nodes <- read.csv("data/Dataset1-Media-Example-NODES.csv", header=T) links <- read.csv("data/Dataset1-Media-Example-EDGES.csv", header=T) head(nodes) id media media.type type.label 1 s01 NY Times 1 Newspaper 2 s02 Washington Post 1 Newspaper 3 s03 Wall Street Journal 1 Newspaper 4 s04 USA Today 1 Newspaper 5 s05 LA Times 1 Newspaper 6 s06 New York Post 1 Newspaper audience.size 1 20 2 25 3 30 4 32 5 20 6 50 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
- les nœuds sont définis dans le fichier
Construire le graphe
igraph
associé à ces deux fichiers à l’aide de graph_from_data_frame.La fonction read_graph peut s’adapter à de nombreux formats de graphe :
read_graph(file, format = c("edgelist", "pajek", "ncol", "lgl", "graphml", "dimacs", "graphdb", "gml", "dl"), …)
On considère par exemple le fichier lesmis.gml disponible ici. Les nœuds correspondent aux personnages du roman et une arête est présente si deux personnages apparaissent dans le même chapitre. Le poids de l’arête est déterminé par le nombre de chapitres où les deux personnages sont présents. Importer le graphe à l’aide de read_graph et visualiser le.
1.1.3 Matrice d’adjacence
Enfin un graphe peut également s’identifier avec 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
On pourra utiliser dans ce cas la fonction graph_from_adjacency_matrix pour convertir la matrice en un objet igraph
:
On peut bien entendu faire l’opération inverse et calculer la matrice d’ajacence d’un graphe :
1.2 Visualisation d’un graphe
Un des intérêts principaux du graph mining et de visualiser les connexions entre les nœuds à l’aide d’un graphe. Se pose bien entendu la question (difficile) de la position des nœuds dans le plan pour obtenir la visualisation la plus pertinente du graphe. On peut ensuite s’interroger sur des outils classiques qui vont permettre de colorier les nœuds, d’utiliser différents symboles pour les arêtes, etc…
1.2.1 Network layouts : algorithmes usuels de visualisation
Un graphe peut être visualisé à l’aide de plusieurs algorithmes. On pourra trouver un descriptif ici. On se contentera de donner différents layouts pour l’exemple suivant :
Deux algorithmes sont connus pour avoir des visualisations jugées “esthétiques”. L’idée, très rapidement, est d’essayer d’obtenir la position des nœuds et des arêtes de façon uniforme dans le plan. Pour plus d’informations sur ce sujet difficile on pourra consulter cet article.
Enfin la fonction tktplot
1.2.2 Personnalisation du graphe
Il est bien entendu possible de modifier les couleurs, tailles… des nœuds et arêtes. Deux stratégies sont possibles avec igraph :
- utiliser les options de plot.igraph : vertex.color, vertex.shape, vertex.size, vertex.label… et edge.color, edge.label, edge.width…
- travailler sur les nœuds et arêtes séparément à l’aide des fonctions V() et E().
La fonction plot.igraph :
plot(G,
vertex.color="yellow",vertex.size=15,vertex.label.color="blue",
edge.color="red",edge.width=5)
On peut également modifier les paramètre des nœuds
et des arêtes
On a ainsi
vertex_attr(G1)
$color
[1] "red" "red" "red" "red" "red" "red" "red" "red" "red"
[10] "red" "red" "red" "red" "red" "red" "red" "red" "red"
[19] "red"
$size
[1] 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15
[19] 15
edge_attr(G1)
$color
[1] "blue" "blue" "blue" "blue" "blue" "blue" "blue" "blue"
[9] "blue" "blue" "blue" "blue" "blue" "blue" "blue" "blue"
[17] "blue" "blue" "blue" "blue" "blue" "blue" "blue" "blue"
[25] "blue" "blue" "blue" "blue" "blue" "blue" "blue" "blue"
[33] "blue" "blue" "blue" "blue" "blue" "blue" "blue" "blue"
[41] "blue" "blue" "blue" "blue"
$size
[1] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
[29] 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
et on peut visualiser le graphe (sans option dans plot.igraph) :
Exercice 1.3 (Gérer les couleurs avec igraph)
Construire un graphe avec 3 composantes connexes de taille 10, 14 et 8.
Colorier les nœuds de chaque composante d’une couleur différente.
Relier les composantes en ajoutant 2 arêtes (et pas plus).
Utiliser une couleur et une taille différente pour les deux arêtes crées.
Exercice 1.4 (Customiser un graphe) On considère le graphe net sur les médias défini dans l’exercice 1.2. Représenter le graphe en ajoutant :
- le nom des nœuds (media)
- une couleur différente en fonction du type de média
- une taille de nœud différente en fonction de l’audience
- une taille d’arête différente en fonction du poids (
weight
) - une couleur d’arête différente en fonction du type (
type
).
On regarde tout d’abord les attributs des noeuds et arêtes du graphe :
vertex_attr(net)
$name
[1] "s01" "s02" "s03" "s04" "s05" "s06" "s07" "s08" "s09"
[10] "s10" "s11" "s12" "s13" "s14" "s15" "s16" "s17"
$media
[1] "NY Times" "Washington Post"
[3] "Wall Street Journal" "USA Today"
[5] "LA Times" "New York Post"
[7] "CNN" "MSNBC"
[9] "FOX News" "ABC"
[11] "BBC" "Yahoo News"
[13] "Google News" "Reuters.com"
[15] "NYTimes.com" "WashingtonPost.com"
[17] "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"
[5] "Newspaper" "Newspaper" "TV" "TV"
[9] "TV" "TV" "TV" "Online"
[13] "Online" "Online" "Online" "Online"
[17] "Online"
$audience.size
[1] 20 25 30 32 20 50 56 34 60 23 34 33 23 12 24 28 33
edge_attr(net)
$weight
[1] 10 12 22 21 22 21 21 11 12 22 23 20 11 11 21 23 21 21
[19] 21 22 21 21 21 23 21 22 22 21 21 2 5 1 1 2 2 3
[37] 1 1 1 1 2 2 4 2 4 4 4 1 1 1 1 1
$type
[1] "hyperlink" "hyperlink" "hyperlink" "hyperlink"
[5] "mention" "mention" "mention" "mention"
[9] "mention" "hyperlink" "hyperlink" "mention"
[13] "hyperlink" "hyperlink" "mention" "hyperlink"
[17] "hyperlink" "mention" "mention" "mention"
[21] "hyperlink" "hyperlink" "hyperlink" "hyperlink"
[25] "hyperlink" "hyperlink" "mention" "mention"
[29] "hyperlink" "hyperlink" "hyperlink" "hyperlink"
[33] "mention" "hyperlink" "mention" "hyperlink"
[37] "mention" "hyperlink" "mention" "hyperlink"
[41] "mention" "mention" "hyperlink" "hyperlink"
[45] "hyperlink" "mention" "hyperlink" "hyperlink"
[49] "mention" "hyperlink" "hyperlink" "mention"
On effectue une première représentation avec :
plot(net,vertex.label=V(net)$media, vertex.color=V(net)$media.type,
vertex.size=V(net)$audience.size, edge.width=E(net)$weight)
On peut améliorer l’esthétique du graphe en redéfinissant les épaisseurs des arêtes ou les tailles des flèches ou encore en mettant des abréviations pour les noms de média…
1.3 Statistiques descriptives sur les graphes
Comme pour tout les types de données, il est souvent crucial de calculer des indicateurs descriptifs sur les graphes. Nous présentons les indicateurs standards tels que le diamètre, la densité, les degrés de centralité et d’intermédiarité…
Exercice 1.5 (Quelques descripteurs) On considère toujours le graphe des exercices précédents sur les média (net
).
Calculer les nombre de nœuds, d’arêtes, le diamètre et la densité du graphe.
Combien y a t-il de triangles dans le graphes ? On pourra calculer ce nombre de plusieurs façons.
La fonction
renvoie, pour chaque noeud, le nombre de triangles dont il fait partie. On déduit ainsi que le nombre de triangles vaut
On peut aussi l’obtenir avec
ou encore en cherchant les cliques de taille 3 :
Calculer la transitivité.
Quels sont les nœuds connectés avec le nœud 3 ? On pourra utiliser neighbors.
Étudier les composantes connexes du graphe.
components(net) $membership s01 s02 s03 s04 s05 s06 s07 s08 s09 s10 s11 s12 s13 s14 s15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 s16 s17 1 1 $csize [1] 17 $no [1] 1
C’est facile : il y en a une seule de taille 17.
Calculer les degrés des nœuds et représenter les avec un barplot. On pourra utiliser degree puis degree_distribution.
deg <- degree(net) deg s01 s02 s03 s04 s05 s06 s07 s08 s09 s10 s11 s12 s13 s14 s15 10 7 13 9 5 8 5 6 5 5 3 6 4 4 6 s16 s17 3 5
df <- data.frame(deg=deg) library(tidyverse) ggplot(df)+aes(x=deg)+geom_bar(fill="blue")+theme_classic()
Pour le barplot, il est préférable d’utiliser la distribution des degrés :
Calculer les degrés de proximité et d’intermédiarité et ordonner les observations en fonction de ces degrés.
df.deg <- data.frame(prox,ord.prox=1:vcount(net)) |> arrange(desc(prox)) df.int <- data.frame(inter,ord.inter=1:vcount(net)) |> arrange(desc(inter)) bind_cols(df.deg,df.int) prox ord.prox inter ord.inter s07 0.006134969 7 145.833333 3 s03 0.005208333 3 91.333333 4 s08 0.004672897 8 66.000000 17 s10 0.004504505 10 49.000000 5 s02 0.003584229 2 48.000000 10 s15 0.003184713 15 45.500000 12 s05 0.002754821 5 34.000000 1 s01 0.002666667 1 23.666667 2 s04 0.002645503 4 21.500000 6 s13 0.002341920 13 21.500000 13 s17 0.002272727 17 14.000000 8 s09 0.001808318 9 2.333333 15 s12 0.001508296 12 1.000000 14 s14 0.001457726 14 0.500000 7 s06 0.001342282 6 0.000000 9 s16 0.001338688 16 0.000000 11 s11 NaN 11 0.000000 16
Exercice 1.6 (Centralité et intermédiarité) On considère le graphe suivant.
Calculer en utilisant la définition les degrés de centralité et d’intermédiarité des nœuds de \(G\). Retrouver ces valeurs à l’aide de fonctions R.
Pour la centralité :
- le noeud 1 est à une distance 1 des quatre autres, son degré est donc 1/4.
- 2 est à une distance 1 de 1, et à distance 2 des autres. Son degré est donc 1/7
- idem pour 3 et 4.
Pour l’intermédiarité :
- Tous les plus courts chemins passent par 1 ! Le degrés est donc égal au nombre de couples de noeuds, c’est-à-dire 6 !
- Pour les autres points, on remarque qu’aucun plus court chemin ne passe par eux, leur degré est donc nul.
On peut bien entendu retrouver ces résultats :
Exercice 1.7 (Comparaison de nœuds) On considère le graphe karate que l’on peut récupérer dans le package igraphdata :
En étudiant les différents critères d’importance des nœuds, identifier les nœuds importants et interpréter.
deg <- degree(karate)
prox <- closeness(karate)
inter <- betweenness(karate)
df.deg <- tibble(deg=deg,prox=prox,inter=inter)
deg.rank <- tibble(deg=order(deg,decreasing = TRUE),
prox=order(prox,decreasing = TRUE),
inter=order(inter,decreasing = TRUE))
deg.rank
# A tibble: 34 × 3
deg prox inter
<int> <int> <int>
1 34 1 1
2 1 34 34
3 33 20 20
4 3 32 32
5 2 13 33
6 4 21 3
7 32 29 25
8 9 2 2
9 14 33 18
10 24 9 6
# ℹ 24 more rows
Les noeuds 1 et 34 se trouvent toujours aux deux premières places, ce sont les deux présidents des clubs : les liens avec les membres de leurs clubs sont forts. L’individu 20 est également très bien placé, on remarque qu’il est lié aux deux présidents, c’est donc un intermédiaire très important.
C’est également le cas du 32 :
neighbors(karate,32)
+ 6/34 vertices, named, from 4b458a1:
[1] Mr Hi Actor 25 Actor 26 Actor 29 Actor 33 John A
On remarquera enfin que le 33 possède un grand nombre de liens, et donc un degrés élevé :
1.4 Autres packages pour visualiser les graphes
1.4.1 Graphes dynamiques avec visNetwork
Nous avons vu que le package igraph propose une visualisation statique d’un réseau. Pour donner un caractère dynamique à ce type de représentation, on pourra utiliser le package visNetwork. Une représentation standard visNetwork s’effectue en spécifiant les nœuds et connexions d’un graphe. Voici quelques exemples d’utilisation.
set.seed(1234)
nodes <- data.frame(id = 1:15, label = paste("Id", 1:15),
group=sample(LETTERS[1:3], 15, replace = TRUE))
edges <- data.frame(from = trunc(runif(15)*(15-1))+1,to = trunc(runif(15)*(15-1))+1)
library(visNetwork)
visNetwork(nodes,edges)
Exercice 1.8 (Interactions entre médias) On considère à nouveau le graphe sur les médias
nodes <- read.csv("data/Dataset1-Media-Example-NODES.csv", header=T, as.is=T)
links <- read.csv("data/Dataset1-Media-Example-EDGES.csv", header=T, as.is=T)
head(nodes)
id media media.type type.label
1 s01 NY Times 1 Newspaper
2 s02 Washington Post 1 Newspaper
3 s03 Wall Street Journal 1 Newspaper
4 s04 USA Today 1 Newspaper
5 s05 LA Times 1 Newspaper
6 s06 New York Post 1 Newspaper
audience.size
1 20
2 25
3 30
4 32
5 20
6 50
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
L’objet nodes
représente les nœuds du graphe et l’objet links
les arêtes. On définit l’objet graphe
avec
et on peut le visualiser en faisant un plot
de cet objet
Visualiser ce graphe avec VisNetwork. On pourra utiliser la fonction toVisNetworkData
Ajouter une option qui permette de sélectionner le type de media (Newspaper, TV ou Online).
Utiliser une couleur différente pour chaque type de media.
Il suffit de donner le nom
group
à la variable media.type.Faire des flèches d’épaisseur différente en fonction du poids (weight). On pourra également ajouter l’option visOptions(highlightNearest = TRUE).
Il suffit de donner le nom value à la variable weight.
names(media.VN1$edges)[3] <- "value" visNetwork(nodes=media.VN1$nodes,edges=media.VN1$edges) |> visOptions(selectedBy = "labels",highlightNearest = TRUE)
1.4.2 Graphes ggplot avec ggnet
Les fonctions ggnet et ggnet2 du package GGally
permettent de tracer des graphes ggplot. On pourra trouver un descriptif clair à l’url suivante https://briatte.github.io/ggnet/.
On construit un premier graphe que l’on visualise avec igraph.
Pour visualiser ce graphe en ggplot il faut le transformer en objet network :
On peut maintenant utiliser les fonctions ggnet et ggnet2.
On retrouver bien entendu la plupart des options standards pour visualiser les noeuds et arêtes, par exemple