Análisis de Grafos

En esta entrada hago una recopilación de varios post de Andrie de Vries. Ya que el ejemplo que realiza se puede replicar sin problema alguno, la muestra de datos es suficientemente grande como para ser interesante y combina varias técnicas para detectar comunidades o clusters, con la finalidad de encontrar los nodos más sobre salientes del grafo.

Una área de investigación importante tanto en matemáticas, en física como en ingeniería; es la investigación en Grafos Grandes o redes largas (Large Graph). Sobre este tema recomiendo la referncia [1]. En lo personal es una área que me gusta y que pese a saber poco, trato de leer y de aprender al respecto, quizás más aspectos teóricos que prácticos; pero suele ser grato tener algunos ejemplos de donde aparecen los objetos matemáticos estudiados.

No puedo, ni pretendo hablar de teoría de grafos o gráficas por que no soy el adecuado para hablar a detalle del tema, pero recomiendo las referencias [2,3] para acercarse al tema desde el lado de algoritmos y desde el punto de vista de matemáticas discretas. Un libro en línea que puede ser una grata introducción a manejar grafos en python se puede ver en la referencia [4].

De que trata el ejemplo.

Hago uso de las idea y parte del código de Andrine Vries para mostrar como procesar un grafo. Este está formado por una muestra de paquetes o librerías de R, así que con más  7000 nodos es interesante aplicar ciertos algoritmos.

Las etapas son las siguientes:

  1. Cargar los datos y explorar parte de ellos.
  2. Aplicar el algoritmos PageRank.
  3. Aplicar técnicas de Cluster para grafos y comparar entre algunos algoritmos.
  4. Mostrar algunas representaciones gráficas sobre el grafo y el impacto de los algoritmos en él.

La idea es explicar el uso de cada librería en los puntos anteriores y el uso de Gephi.

Etapa 1. Generar los datos

Antes de mostrar un ejemplo sencillo de como generar un grafo, la idea de grafo es contar con nodos y con aristas. Donde las aristas conectan a los nodos o se quedan conectando al mismo nodo. Una idea gráfica se puede ver como la siguiente imagen:

usa-7-2

Grafo de libro Fractional Graph Theory

Pero también puede ser algo mucho más extraño, por la cantidad de nodos y la conexión entre las aristas. De modo tal que se pueden ver como:

map-of-internet

Visualización de la Intenet

Entonces la conexión entre redes y grafos pues es natural, prácticamente son lo mismo; pero la perspectiva con la cual la estudian desde el punto de vista de física es distinta a la que se estudia en matemáticas.

En R se tiene la librería miniCRAN con la cual se pueden extraer datos de los paquetes o librerías. Cuando se instala una librería muestra en la mayoría de los casos la solicitud de instalar las librerías con las cuales tiene dependencia en caso de no contar con ellas. Así que hay muchas librerías que tienen dependencia con muchas otras librerías y otras, simplemente con unas cuantas. La mayoría usan las librerías base de R, pero con miniCRAN se pueden ignorar estas y analizar solo las que no son básicas.

#Ejemplo 1
 librería(miniCRAN)

tags<-"ggplot2"

#Se extraen datos de las librerías con las cuales tiene relación de tres modos diferente, considerando o descartando algunas.

pkgDep(tags, suggests=FALSE, enhances=FALSE, includeBasePkgs = TRUE)

pkgDep(tags, suggests=FALSE, enhances=FALSE)

pkgDep(tags, suggests=TRUE, enhances=TRUE)

#Gráfica de las relaciones entre el paquete ggplot2

set.seed(1)

plot(makeDepGraph(tags, includeBasePkgs=FALSE, suggests=TRUE, enhances=TRUE), 
 legendPosEdge = c(-1, 1), legendPosVertex = c(1, 1), vertex.size=30, cex=0.7)

La gráfica que se obtiene es la siguiente:

ggplot2_graphs

Si se replica el código pero para una lista de librerías, se puede pensar en buscar el grafo de ciertas librerías que se usan para tareas relacionadas, ejemplo dplyr y reshape2, ggplot2 y lattice; etc. Pero para mostrar que no todos los paquetes están relacionados se puede considerar en la lista algunas librerías que tienen un uso diferente, como tm y lars.

#Ejemplo 2
library(miniCRAN)

tags<-c("dplyr","reshape2","ggplot2","tm","lattice","data.table","lars")

set.seed(1)

plot(makeDepGraph(tags, includeBasePkgs=FALSE, suggests=TRUE, enhances=TRUE), 
 legendPosEdge = c(-1, 1), legendPosVertex = c(1, 1), vertex.size=15,cex=0.5)

La gráfica que se obtienen es la siguiente:

dplyr-reshape2-data.table-ggplot2-lattice-tm_graphs

Observando la imagen se observa que hay dos nodos; tm y lars, que se muestran “disjuntos” a la red que muestran los otros paquetes. En este caso, se aprecia gráficamente que entre las librerías para procesar datos y generar gráficas existen ciertas relaciones, las cuales pueden ser analizadas.

Entonces la idea es extraer el grafo de todos los paquetes de R hasta hoy 29-09-2015 y aplicar algunos algoritmos para jugar con él. La cantidad de paquetes disponibles es de 7234 hasta hoy, lo cual hace pensar en que una imagen gráfica de dicho grafo es algo complicada para detectar cuales paquetes se aglomeran más que otros, o cuales son casi asilados del resto (como en las imágenes anteriores).

La extracción de los datos se realiza con el siguiente código:

library(miniCRAN)
library(magrittr)

MRAN <- "http://mran.revolutionanalytics.com/snapshot/2015-09-29/"

#Se extrae la matriz con todos los paquetes
pdb <- MRAN %>%
 contrib.url(type = "source") %>%
 available.packages(type="source", filters = NULL)

#Para visualizar el tipo de dato y las primeras 5 filas de la matriz de datos
class(pdb)
head(pdb)

#Se construye un grafo con la matriz

g <- pdb[, "Package"] %>%
 makeDepGraph(availPkgs = pdb, suggests=FALSE, enhances=TRUE, includeBasePkgs = FALSE)

#Se puede ver el tipo de dato
class(g)
head(g)

Etapa 2.Aplicación de PageRank

Por el tamaño del grafo resulta conveniente aplicar algún tipo de algoritmo para detectar algo sobre la relación entre paquetes. La idea de aplicar el algoritmo PageRank para detectar los paquetes que tienen más relevancia en la red.

Para ver detalles sobre el algoritmo les recomiendo la referencia [5]. En breve la idea del algoritmo es asignar un valor numérico a cada paquete y por medio de eso poder definir cuales tienen mayor relevancia según el valor que se le asignó que es un modo de sintetizar el peso o impacto del paquete en los otros paquetes. Esto no le hace el merito adecuado a dicho algoritmo, pero los detalles teóricos se salen de poder explicarse en la entrada.

Aplicando el algoritmo que se tienen implementado en la librería igraph, se obtienen los siguientes resultados:

#Aplicación de pageRank
library(igraph)

#Se aplica el algoritmo
pr <- g %>%
 page.rank(directed = FALSE) %>%
 use_series("vector") %>%
 sort(decreasing = TRUE) %>%
 as.matrix %>%
 set_colnames("page.rank")

head(pr, 10)
# Los 10 paquetes más importantes
#   page.rank
#Rcpp 0.021333171
#MASS 0.019112827
#Matrix 0.009390048
#ggplot2 0.009136545
#mvtnorm 0.008061911
#lattice 0.007902018
#survival 0.007814334
#plyr 0.007025619
#sp 0.004832534
#XML 0.004669243

Haciendo una representación gráfica del orden implementado por el algoritmo PageRank, se obtienen lo siguiente:

#Top 10
set.seed(40)
pr %>%
 head(10) %>%
 rownames %>%
 makeDepGraph(pdb) %>%
 plot(main="Top de paquetes", cex=0.5)

#Top 30
set.seed(40)
pr %>%
 head(30) %>%
 rownames %>%
 makeDepGraph(pdb) %>%
 plot(main="Top 30 de paquetes", cex=0.5)

Las gráficas que se obtienen son las siguientes:

top_10

Top_30

Se observa que el grafo de los primeros 10 es más o menos claro, pero que el de los primeros 30 ya empieza a mostrar cierta complejidad o se muestra más complicado para determinar visualmente algunos aspectos, pese a eso se aprecian en la imagen un par de paquetes asilados.

Etapa 3.-Detectando comunidades.

Los clusters, son parte de las técnicas de aprendizaje no supervidado en Machine Learning. Existen muchas técnicas o algoritmos, algunos al paso del tiempo ya sea por la eficiencia computacional o por el tipo de resultados que han permitido obtener terminan siendo predominantes o persistir ante la aparición de nuevas técnicas o algoritmos.

En la entrada “Análisis de Cluster, un ejemplo sencillo” mostré como usar dicha técnica con unos conjuntos de datos. La situación cambia un poco cuando se trabaja sobre grafos o redes, ya que se tiene en particular un tipo de datos (el grafo) sobre el cual se hace uso de sus propiedades para definir los algoritmos para detectar clusters.

En las referencias [6,7,8,9] se puede leer varios exploraciones experimentales sobre el tipo de algoritmos que más predominan en las investigaciones y al implementar dichos algoritmos. Aplico dos algoritmos para detectar comunidades o clusters en el grafo y mido la similaridad entre las dos comunidades con la medida de similaridad de Jaccard para comparar los resultados obtenidos entre los dos algoritmos.

Siguiendo a Andrie de Vries, solo tomo el 80% de la red de los cuales se eligen los nodos más importantes según el algoritmo PageRank.

#Se aplica al mismo grafo ordenado por PageRank pk
#Se selecciona el 80% de los datos

cutoff <- quantile(pr[, "page.rank"], probs = 0.2)
popular <- pr[pr[, "page.rank"] >= cutoff, ] 
toKeep <- names(popular)

vids <- V(g)[toKeep]
gs <- induced.subgraph(g, vids = toKeep)

#Aplicación del primer algoritmo walktrap community
#Se obtienen 2118 comunidades

cl <- walktrap.community(gs, steps = 3)

#Se ordenas
topClusters <- table(cl$membership) %>% 
 sort(decreasing = TRUE) %>% 
 head(25)

#Se gráfica el comportamiento de los cluster o de las comunidades

plot(topClusters, main="Tamaño Cluster", ylab="Numero de cluster", type="b", lwd=2)

#Se aplica el segundo algoritmo, infoMaps community
#Se obtienen 2280 comunidades

cl1 <- infomap.community(gs)

topClusters1 <- table(cl1$membership) %>% 
 sort(decreasing = TRUE) %>% 
 head(25)

plot(topClusters1, main="Tamaño de Clusters", ylab="Numero de clusters", type="b", lwd=2)

Cluster_walktrap

InfoMaps_clusters

Las gráficas muestran el comportamiento de los cluster o comunidades, lo cual muestra que se pueden elegir los primero 10 clusters como los más importantes. Siguiendo a Andrie de Vries se eligen los 10 clusters más importantes.

Para comparar el comportamiento entre los dos algoritmos; además de que el primero detecta 2118 comunidades y el segundo 2280, comparo los 10 cluster más importantes por medio del índice de similaridad de Jaccard. Para los que tienen nociones de teoría de conjuntos, la idea es muy sencilla es comparar cuantos elementos están en la intersección dividido entre los elementos en la unión. Esto da una medida de similaridad, con la cual comparo entre las 10 comunidades más importantes por algoritmo.

#Eligiendo los 10 clusters más importantes

cluster <- function(i, clusters, pagerank, n=10){
 group <- clusters$names[clusters$membership == i]
 pagerank[group, ] %>% sort(decreasing = TRUE) %>% head(n)
}

#Para walktrap
z1 <- lapply(names(topClusters)[1:10], cluster, clusters=cl, pagerank=pr, n=20)

#Para infoMaps
z2 <- lapply(names(topClusters1)[1:10], cluster, clusters=cl1, pagerank=pr, n=20)

#Comparación entre los cluster de cada algoritmo

Jaccard<-function(A,B){
 a=length(intersect(A,B))
 b=length(union(A,B))
 a/b
 }
s=vector(length=10)

for(i in 1:10){
 L1=names(z1[[i]])
 L2=names(z2[[i]])
 s[i]=Jaccard(L1,L2)
 }

library(ggplot2)
t=1:10
qplot(x=t,y=s,geom=c("line", "point"), main="Similaridad entre los dos algoritmos", xlab="Número de Cluster",ylab="Valor de Similaridad")

Similaridad

Se observa que en los dos algoritmos en el primer cluster se tienen más similaridad, la lista de librerías por algoritmo son las siguientes:

#Para el algoritmo Walktrap
names(z1[[1]])
 [1] "MASS" "Matrix" "mvtnorm" "lattice" 
 [5] "survival" "igraph" "coda" "nlme" 
 [9] "rgl" "boot" "RColorBrewer" "numDeriv" 
[13] "Hmisc" "mgcv" "cluster" "gtools" 
[17] "car" "fields" "lme4" "xtable" 

#Para el algoritmo infoMaps
names(z2[[1]])
 [1] "Rcpp" "plyr" "XML" "stringr" 
 [5] "reshape2" "foreach" "jsonlite" "rJava" 
 [9] "cluster" "car" "fields" "lme4" 
[13] "corpcor" "e1071" "doParallel" "vegan" 
[17] "quadprog" "rpart" "randomForest" "plotrix"

La interpretación o explicación de los resultados puede varias, ejemplo en los conjuntos de librerías anteriores aparece una combinación entre librerías para procesar datos, para graficar, para aplicar modelos predictivos o de clasificación, etc.

Para visualizar el grafo de las librerías, la intención era mostrarlo con Gephi pero tuve un problema con el programa y hasta que después repare o vea que es lo que tiene comparto la visualización de toda la red. Pero con igraph se puede hacer una imagen buena de como se comportan los cluster en la red.

#Uso de igraph, parte de código de Andrei de Vries

#Se carga la librería
library(igraph)

# Se preparan los datos para construir la gráfica

cl$degree <-(degree(gs)[cl$names])
cl$cluster<-unname(ave(cl$degree, cl$membership,FUN=function(x)names(x)[which.max(x)]))
V(gs)$name <- cl$cluster

E(gs)$weight <- 1
V(gs)$weight <- 1

gcon<-contract.vertices(gs, cl$membership,vertex.attr.comb = list(weight = "sum", name = function(x)x[1], "ignore"))

gcon<-simplify(gcon, edge.attr.comb = list(weight = "sum", function(x)length(x)))

gcc<-induced.subgraph(gcon, V(gcon)$weight > 20)

V(gcc)$degree<-unname(degree(gcc))

#construcción de la gráfica
par(mar = rep(0.1, 4)) 
g.layout<-layout.kamada.kawai(gcc)
plot.igraph(gcc, edge.arrow.size = 0.1, layout = g.layout, vertex.size = 0.5 * (V(gcc)$degree))

La imagen de grafo que se obtiene es el siguiente:

Grafo1_vis

Se muestra en la imagen como la librería con círculos mayores tienen mayor relevancia en la parte de la red, por su puesto que no están las 7000 librerías representadas pero esta imagen da idea de cuales son las librerías más importantes o las más usadas, partiendo de la clasificación hecha con el algoritmo walktrap y pagerank.

Espero la entrada de una idea como tratar en general datos que pueden ser analizados como un grafo, cabe mencionar que cuando se analiza un corpus de textos o un texto, este también puede ser analizado y explorado visualizando su matriz de términos como la matriz asociada a un grafo y eso hace que se tengan más herramientas para analizar lo que sucede con dicho texto o la relevancia de sus tópicos.

Referencias:

  1. Large Network and graph limits.Lásló Lovasz
  2. Estructura de datos y algoritmos.
  3. Graph Theory
  4. http://interactivepython.org/runestone/static/pythonds/index.html
  5. http://www.mmds.org/
  6. http://www-personal.umich.edu/~mejn/papers/epjb.pdf
  7. http://arxiv.org/abs/1004.3539
  8. http://deim.urv.cat/~clara.granell/publications/ijcss_clara.pdf
  9. http://www.syssec-project.eu/m/page-media/3/moradi-sea12.pdf
Anuncios

Responder

Por favor, inicia sesión con uno de estos métodos para publicar tu comentario:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s