silico.biotoul.fr
 

M1 BBS Graphes TP Librairies R - igraph

From silico.biotoul.fr

Jump to: navigation, search

Contents

Prise en main de la librairie R - igraph

La librairie igraph met à disposition tout un ensemble de fonctions pour le traitement et la visualisation de graphes. Elle est codée en C. Nous allons utiliser aujourd'hui son interfaçage avec R. Pour la charger :

library(igraph)

Différentes manières de l'installer :

Graphe Cleandb_Luca_1_S_1_1_65_Iso_Tr_1-CC1

Pour charger un graphe (différents format possibles : pajek, newick, ...) :

g = read.graph("http://silico.biotoul.fr/site/images/9/9f/Cleandb_Luca_1_S_1_1_65_Iso_Tr_1-CC1.tgr", directed=FALSE)

Consulter l'aide de la fonction (?read_graph) pour voir les autres formats supportés.


Pour l'afficher, il faut au préalable en effectuer le dessin (layout) :

# soit en une ligne en passant la fonction de dessin :
plot(g, layout=layout.fruchterman.reingold)
 
# soit en sauvegardant ce layout dans une variable :
lfr = layout.fruchterman.reingold(g)
plot(g, layout=lfr, vertex.size=3, vertex.label=NA)

Remarque : le fait de sauvegarder la disposition des sommets, (i) évite de la recalculer pour chaque plot, (ii) permet d'avoir la même disposition à chaque plot (certains algorithmes, tel que FR, ne donnent pas la même disposition à chaque fois).

Consulter l'aide des fonction plot.igraph et layout.fructhterman.reingold pour voir les options ainsi que les autres algorithmes de dessin disponibles.

Vous trouverez la documentation de la librairie sur le site dédié. Pour celle de l'interface R en ligne : https://igraph.org/r/

  • Pour obtenir la liste des sommets : V(g)
  • la liste des arêtes : E(g)
  • Quel est l'ordre du graphe ? Combien a-t-il d'arêtes ?


On peut assigner des étiquettes aux sommets : V(g)$name = vector_of_labels

Charger les étiquettes des sommets :

V(g)$name=as.character(read.table("http://silico.biotoul.fr/site/images/6/61/Cleandb_Luca_1_S_1_1_65_Iso_Tr_1-CC1.cod")[,2])
plot(g, layout=lfr, vertex.size=3, vertex.label=V(g)$name)

Les paramètres de la fonction plot de igraph sont décrits dans la documentation.

On peut redéfinir les paramètres par défaut :

Paramètres par défaut pour l'affichage

igraph.options(vertex.label.cex=.8) # font size
igraph.options(vertex.label.family='sans')
igraph.options(vertex.size=3) 
igraph.options(vertex.color=NA)


Il est possible de stocker de l'information sur le graphe, les sommets et/ou les arêtes avec les fonctions dédiées :

vertex_attr(g, name="name")
vertex_attr(g, name="name", index=10)


  • Quel est le diamètre du graphe ? (cf. diameter ou distances)
  • Lister les points d'articulation (articulation.points)
  • Longueur moyenne des plus courts chemins (sans valuation) (average.path.length)
  • Afficher sa représentation canonique (canonical.permutation) et la matrice d'adjacence correspondante
  • Lister les composantes connexes (clusters) avant et après suppression du point d'articulation
  • Obtenir le line graph (line.graph)

Fichier dressing au format ncol : dressing.ncol, Bellman-Ford.ncol et celui pour Floyd-Warshall Floyd-Warshall.ncol

dressing
Graphe utilisé pour l'algorithme Bellman-Ford
Graphe utilisé pour l'algorithme Floyd-Warshall
  • Effectuer le tri topologique du graphe dressing. Contient-il un circuit ?
  • Parcours en largeur et en profondeur, et Bellman-Ford (bfs, dfs, distances)

Graphe STRINGdb E. coli

Création d'un graphe à partir d'un data.frame (retrouvez vos fichiers 511145.protein.links.detailed.v11.0.txt et 511145.protein.info.v11.0.txt).

Chargement et préparation des données

library(tidyverse)
links.detailed = read_delim("511145.protein.links.detailed.v11.0.txt", delim=" ")
links.detailed
 
links.filtered = links.detailed %>% 
  filter(protein1<protein2 & (coexpression>=800 | experimental>=800)) %>%
  select(protein1, protein2, coexpression, experimental)
links.filtered
 
proteins = read_delim("511145.protein.info.v11.0.txt", delim="\t")
proteins

Création du graphe à partir du data.frame

g = graph_from_data_frame(d = links.filtered, directed = F, vertices = proteins)
V(g)$name = V(g)$preferred_name

Remarque : le paramètre vertices n'est pas nécessaire mais facilite le renommage des sommets (preferred_name plutôt que protein_external_id).


Ne gardon que la plus grande composante connexe

CC = clusters(g)
which ( CC$csize == max(CC$csize) )

Extraction du sous-graphe induit

v5 = which(CC$membership == 5)
g5 = induced_subgraph(g, v5)
fr = layout.fruchterman.reingold(g5)
plot(g5, layout=fr, vertex.label=NA)


  • la betweenness d'un sommet ou d'une arête est le nombre de plus courts chemins passant par le sommet ou l'arête. Utiliser les fonctions betweenness et edge.betweenness pour calculer cette valeur et l'ajouter au dessin.

Pour la centralité des sommets : Pour la centralité des arêtes :


  • Arbre couvrant de poids minimum (minimum.spanning.tree)

Partitionnement de graphe et détection de communautés

Pour partitionner le graphe en communautés, différentes méthodes sont disponibles. Vous allez utilisez la betweenness des arêtes pour effectuer le partitionnement du graphe. Cette méthode sélectionne les arêtes dont la betweenness est la plus importantes afin de former des communautés (clusters).

# community detection with edge-betweenness
com = edge.betweenness.community(g5)
par(cex=.5)
names(com)

Modularité

modularity(com)

Affichage du meilleur partitionnement

plot(com, g5, vertex.size=6, vertex.label=NA, main=paste0("Q = ", round(modularity(com), 3)))

Dessin de graphes

L'algorithme de Fruchterman-Reingold donne un résultats assez stisfaisant généralement sur les réseaux biologiques. Il modélise assez simplement un modèle physique (cf. cours). Nous allons comparer les performances sur une autre structure de grapĥe : un treillis.

lat=graph.lattice(length=10,dim=2)
# layout
lat.FR=layout.fruchterman.reingold(lat)
lat.MDS=layout.mds(lat)
# tracé
plot(lat, layout=lat.FR, vertex.size=3, vertex.label=NA, main='Fruchterman-Reingold')
plot(lat, layout=lat.MDS, vertex.size=3, vertex.label=NA, main='MDS')

Sur un petit graphe, les résultats sont assez comparables. Essayons sur un graphe un peu plus grand (length=30 ou 50)

lat=graph.lattice(length=30,dim=2)
# layout
lat.FR=layout.fruchterman.reingold(lat)
lat.MDS=layout.mds(lat)
# tracé
plot(lat, layout=lat.FR, vertex.size=3, vertex.label=NA, main='Fruchterman-Reingold')
plot(lat, layout=lat.MDS, vertex.size=3, vertex.label=NA, main='MDS')

Annexe

Notebook : Rmd - html - nb.html