Esta materia no es un curso de grafos per se. El universo del estudio de grafos es enorme en sí mismo (como pasa con muchos temas en esta materia). Por nuestra parte nos va a interesar como herramienta para visualizar y medir relaciones entre los datos. En este sentido, podemos pensar al grafo como una forma de representar datos. Dependiendo de la estrategia de representación, los grafos pueden corresponderse con listas (semiestructurados), tablas (estructurados) o pares de tablas.
Un grafo (también red) es una estructura MUY general en la cual podemos representar relaciones entre objetos. En general lo representamos a través de dos conjuntos: uno de vértices (o nodos) \(V\) y uno de ejes (o conexiones) \(E\). Los vértices representan los objetos que nos interesa estudiar (pueden ser personas, animales, productos o lo que se les ocurra) y los ejes sus relaciones (retweets o espacios laborales compartidos para personas, cadenas tróficas entre animales, ingredientes compartidos entre productos, por nombrar algunas cosas). Lo poderoso de la representación mediante grafos es que permite visualizar la estructura que da soporte a los objetos, y la existencia de una batería enorme de métodos para caracterizar esta estructura. Por ejemplo, hay herramientas para identificar la importancia de cada vértice, los grupos más fuertemente conectados en la red, conexiones que faltan, resistencia de la red a fallos y muchas otras cosas.
La estructura de la red permite incluir más información que sólo los vértices y los ejes. Esto se suele incluir como atributos de los nodos y los ejes (por ejemplo, podríamos querer incluir la edad de las personas como atributo de los vértices, o la cantidad de retweets de una persona a otra como atributo de los ejes).
En nuestro caso, vamos a hacer un análisis exploratorio sobre una red para ver las posibilidades de visualización y caracterización de las correlaciones que implica la estructura de la red sobre sus elementos.
Para construir nuestro grafo vamos a usar los datos del API de tragos que vimos en clases pasadas. Por esto, nuestro primer paso va a ser descargar todos los tragos y sus ingredientes. Vamos a descargar iterativamente la información de todos los tragos con letras en letters
:
require(jsonlite)
bebidas = NULL
url_base = 'http://www.thecocktaildb.com/api/json/v1/1/search.php?f='
letra = 'a'
for(letra in letters){
print(paste('Letra:',letra))
dwld = fromJSON(paste(url_base,letra,sep=''))$drinks
bebidas = rbind(bebidas,dwld)
print(paste('Había',nrow(dwld),'bebidas'))
}
[1] "Letra: a"
[1] "Había 25 bebidas"
[1] "Letra: b"
[1] "Había 25 bebidas"
[1] "Letra: c"
[1] "Había 25 bebidas"
[1] "Letra: d"
[1] "Había 18 bebidas"
[1] "Letra: e"
[1] "Había 10 bebidas"
[1] "Letra: f"
[1] "Había 24 bebidas"
[1] "Letra: g"
[1] "Había 25 bebidas"
[1] "Letra: h"
[1] "Había 17 bebidas"
[1] "Letra: i"
[1] "Había 11 bebidas"
[1] "Letra: j"
[1] "Había 13 bebidas"
[1] "Letra: k"
[1] "Había 16 bebidas"
[1] "Letra: l"
[1] "Había 22 bebidas"
[1] "Letra: m"
[1] "Había 25 bebidas"
[1] "Letra: n"
[1] "Había 6 bebidas"
[1] "Letra: o"
[1] "Había 13 bebidas"
[1] "Letra: p"
[1] "Había 24 bebidas"
[1] "Letra: q"
[1] "Había 8 bebidas"
[1] "Letra: r"
[1] "Había 24 bebidas"
[1] "Letra: s"
[1] "Había 25 bebidas"
[1] "Letra: t"
[1] "Había 25 bebidas"
[1] "Letra: u"
[1] "Había bebidas"
[1] "Letra: v"
[1] "Había 13 bebidas"
[1] "Letra: w"
[1] "Había 11 bebidas"
[1] "Letra: x"
[1] "Había bebidas"
[1] "Letra: y"
[1] "Había 2 bebidas"
[1] "Letra: z"
[1] "Había 13 bebidas"
bebidas
nrow(bebidas)
[1] 420
Con esto logramos descargar la información de todos nuestros tragos disponibles. El problema es que si se fijan, la información de los ingredientes de las bebidas no está presente de forma clara. Por ejemplo, la primer bebida incluye 4 ingredientes, pero tenemos 15 columnas dedicadas a ingredientes.
bebidas[1,grep('Ingredient',colnames(bebidas))]
sum(!is.na(bebidas[1,grep('Ingredient',colnames(bebidas))]))
[1] 4
length(grep('Ingredient',colnames(bebidas)))
[1] 15
Esto es algo que ocurre normalmente cuando convertimos a un formato tabular información de conexiones: dado que no todos los tragos tienen la misma cantidad de conexiones (no tienen la misma cantidad de ingredientes), nuestro dataset tiene mucho espacio vacío dentro.
¿Cómo podemos llevar esta información a un formato más cómodo? Les dejo dos ideas:
R
. La representación es muy similar a un CSV: en cada fila incorporamos la información que describe un eje: su cola y su cabeza. Mirando la primer fila del dataset que descargamos, podríamos visualizarla así:A1,Gin
A1,Grand Marnier
A1,Lemon Juice
A1,Grenadine
A la izquierda siempre tenemos un vertice “bebida” y a la derecha un vértice “ingrediente”.
Mientras que el listado de ejes comprime la información, sólo indicando las conexiones que están presentes, mientras que la matriz de adyacencia la expande indicando qué ocurre para cualquier combinación posible de vértices.
Volviendo a nuestro caso particular, veamos como llevarlo a un listado de ejes. Como ejercicio, vamos a hacer usando las herramientas de tidyverse
.
require(tidyverse)
Vamos a llevar el dataset original a una lista de ejes:
print(paste('Empezamos con',nrow(bebidas),'filas'))
[1] "Empezamos con 420 filas"
beb_tidy = bebidas %>% # Al dataframe de bebidas
select(strDrink,strIngredient1:strIngredient15) %>% # Le seleccionamos los nombres de bebidas y sus ingredientes
group_by(strDrink) %>% #Avisamos que queremos agrupar las operaciones por bebida
unite('strIngredients',strIngredient1:strIngredient15,na.rm=TRUE,sep=',') #Unimos las columnas de ingredientes pegandolas con comas
print(paste('Ahora tenemos',nrow(beb_tidy),'filas y', ncol(beb_tidy),'columnas'))
[1] "Ahora tenemos 420 filas y 2 columnas"
beb_ejes = beb_tidy %>% # Al nuevo dataframe
separate_rows(strIngredients,sep=',') # Lo separamos en filas distintas por cada ingrediente
print(paste('Obtenemos finalmente',nrow(beb_ejes),'ejes'))
[1] "Obtenemos finalmente 1698 ejes"
El único cuidado que no tuvimos hasta acá y nos puede traer problemas es que haya nombres repetidos entre bebidas y ingredientes:
intersect(beb_ejes$strDrink,beb_ejes$strIngredients)
[1] "Limeade" "Rose"
Para sacarnos ese problema de encima, ponemos en mayúscula los nombres de las bebidas y en minúscula la de los ingredientes:
beb_ejes = beb_ejes %>% # Al dataset de ejes
mutate(strDrink = toupper(strDrink),strIngredients=tolower(strIngredients)) # Cambiamos la columna strDrink a mayúscula y strIngredients a minúscula
intersect(beb_ejes$strDrink,beb_ejes$strIngredients)
character(0)
Con esto construido, podemos responder algunas preguntas muy sencillas, aún sin pensar todavía en la red. Por ejemplo, ¿cuál es la bebida que más ingredientes usa? ¿cuál menos? ¿cuántos ingredientes usan cada bebida?
beb_ejes %>%
count(strDrink,name='nIngredients') %>% # Contamos cuantas veces aparece cada bebida, ese es su total de ingredientes
arrange(desc(nIngredients)) # Lo ordenamos en orden descendente
beb_ejes %>% # Lo mismo pero en orden ascendente
count(strDrink,name='nIngredients') %>%
arrange(nIngredients)
beb_ejes %>%
count(strDrink,name='nIngredients') %>% # Contamos ingredientes
ungroup() %>% #Desagrupamos para hacer sumarios
summarise(media=mean(nIngredients),stdev=sd(nIngredients),min=min(nIngredients),max=max(nIngredients)) # Calculamos algunas medidas
beb_ejes %>% # Hacemos un histograma de la cantidad de apariciones de cada ingrediente
count(strDrink,name='nIngredients') %>%
ggplot(mapping=aes(x=nIngredients)) +
geom_histogram(binwidth = 1,fill='white',col='black') +
geom_boxplot(width=10,color='blue',lwd=1.5)
La bebida que más ingredientes usa es Egg Nog #4 (¿ponche de huevo?) con 11 ingredientes, y la que menos se disputa entre muchos candidatos, con 2 ingredientes. En promedio las bebidas tienen 4 ingredientes, con un desvío de 1.5 ingredientes (o sea que podemos resumir que el grueso de los datos tienen entre 2.5 y 5.5 ingredientes).
Repitan este análisis pero en vez de mirar desde el punto de vista del trago, mirenlo desde los ingredientes. ¿Hay alguna coincidencia entre los valores que obtienen?
Habiendo explorado brevemente lo que nos dice la lista de ejes por sí sola, avancemos con la vizualización de la estructura que resulta. Para esto vamos a aprovechar dos paquetes buenísimos de R
para trabajar con redes: igraph
y tidygraph
. igraph
tiene la mayor parte de lo que cualquier análisis de redes puede necesitar, mientras que tidygraph
nos permite aprovechar igraph
y tidyverse
a la vez.
# Si aún no los instalaron:
# install.packages('igraph')
# install.packages('tidygraph')
require(igraph)
require(tidygraph)
Ahora vamos a armar nuestro objeto grafo usando tidygraph
e igraph
.
g = beb_ejes %>%
graph_from_data_frame(directed = FALSE) %>% # Esta función toma el listado y lo convierte en un objeto grafo
as_tbl_graph() # Este lo mueve a formato "tidy"
g
# A tbl_graph: 716 nodes and 1698 edges
#
# An undirected multigraph with 1 component
#
# Node Data: 716 × 1 (active)
name
<chr>
1 A1
2 ABC
3 ACE
4 ADAM
5 AT&T
6 ACID
# … with 710 more rows
#
# Edge Data: 1,698 × 2
from to
<int> <int>
1 1 421
2 1 422
3 1 423
# … with 1,695 more rows
Fijense que llevar beb_ejes
a un tbl_graph
obtenemos un objeto que tiene los dos tipos de información que mencionamos antes: los nodos o vértices ( nodes ) y los ejes ( edges ) en forma de una matriz. Fijense que obtenemos varias medidas resumen desde el punto de partida: tenemos 747 vértices, y 1698 ejes.
Vamos a agregar un poquito extra de información en nuestro grafo, para que incluya el hecho de que nuestros vértices son de distinto tipo:
g = g %>%
activate(nodes) %>% # Así le decimos que opere sobre el dataframe de nodos
mutate(type=ifelse(is.element(name,beb_ejes$strDrink),'Drink','Ingredient')) # Agregamos el tipo de nodo que es
g
# A tbl_graph: 716 nodes and 1698 edges
#
# A bipartite multigraph with 1 component
#
# Node Data: 716 × 2 (active)
name type
<chr> <chr>
1 A1 Drink
2 ABC Drink
3 ACE Drink
4 ADAM Drink
5 AT&T Drink
6 ACID Drink
# … with 710 more rows
#
# Edge Data: 1,698 × 2
from to
<int> <int>
1 1 421
2 1 422
3 1 423
# … with 1,695 more rows
## Podemos chusmear el resultado acá
g %>% activate(nodes) %>% as.data.frame() # Para visualizarlo entero, lo movemos a dataframe
g %>% activate(edges) %>% as.data.frame()
NA
Fijense que luego de esta operación, tidygraph
ya detecto que nuestro grafo es bipartite
(bipartito). Esto significa que todas las conexiones ocurren entre vértices de distinto tipo (en este caso, Drink
y Ingredient
).
Hagamos una primer visualización del grafo
# install.packages('ggraph') # Si aún no lo tienen instalado.
require(ggraph)
g %>%
ggraph() + # Pasamos el grafo a ggraph (ggplot para grafos)
geom_edge_link(edge_width=.1,alpha=0.5) + # Indicamos grosor de los ejes y transparencia
geom_node_point(mapping = aes(color=type,shape=type),size = 1) + # Pedimos color y forma basandose en el tipo de nodo.
theme_graph()
Using `stress` as default layout
# Si graficamos "arriba" un tipo de nodo y "abajo" al otro:
g %>% activate(nodes) %>%
mutate(type=type=='Drink') %>% # La función de layout necesita que sea un vector lógico el "type"
ggraph(layout='igraph',algorithm='bipartite') +
geom_edge_link(edge_width=.1,alpha=0.3) +
geom_node_point(mapping = aes(color=type,shape=type),size = 1) +
theme_graph()
Observen como la forma en la que acomodamos los vértices (el layout del grafo) nos permite observar estructura en los datos: al acomodar los distintos tipos de vértices (Ingredient
arriba y Drink
) abajo, la gráfica nos sugiere que no todas las bebidas se conectan por igual a todos los ingredientes, y que no todos los ingredientes se vinculan por igual a todas las bebidas: hay “grupos” que están más conectados que otros.
Usen la documentación de igraph
sobre layouts para encontrar los diferentes layouts
?ggraph # Lean al final de todo en Details
?layout # Lean al final de todo en See Also
Cambiando el argumento de la función de ggraph
exploren distintos layouts ¿alguno le ayuda a encontrar estructura en los datos? ¿qué observa?
Previamente calculamos la cantidad de ingregientes que cada bebida lleva. Si lo pensamos en términos de la red, esto equivale a hablar de la cantidad de conexiones que tiene cada bebida. A esta magnitud (la cantidad de conexiones que tiene un vértice) se la denomina grado de un vértice, y es la medida de centralidad en una red más común: nos dice de una forma muy simple cuan conectado está un vértice al resto. Una vez definida la red, es muy fácil calcular el grado de cada vértice usando las funciones de igraph
:
degree(g,v='EGG NOG #4')
EGG NOG #4
11
Podemos replicar el gráfico que armamos antes contando ejes a mano:
grados = g %>% degree(v=V(g)$type=='Drink') #Así le pedimos el grado de TODAS las BEBIDAS
ggplot(data=data.frame(grados),mapping=aes(x=grados)) + geom_histogram(binwidth = 1) # Pedimos ancho de bin =1 para que nos muestre separado cada grado
Más interesante aún, podemos buscar la distribución de grado de cada tipo de nodo (bebida o ingrediente) y ver si observamos alguna diferencia
g = g %>% activate(nodes) %>%
mutate(grado=degree(g)) # Ahora sí, directamente agregamos una columna que sea de grados.
g %>% activate(nodes) %>% as.data.frame() %>%
ggplot(mapping=aes(x=grado,fill=type)) +
geom_histogram(binwidth = 1)
g %>% activate(nodes) %>% as.data.frame() %>%
ggplot(mapping=aes(x=grado,fill=type)) +
geom_histogram(binwidth = 1) + xlim(c(0,10))
Estas distribuciones son claramente muy distintas: mientras que las bebidas se concentran alrededor de de 4 ingredientes, los ingredientes varían mucho más: algunos pocos son usados en una miriada de bebidas, mientras que la mayoría sólo se usa en unas pocas bebidas.
Incorporar esta información al dibujo del grafo puede ser un poco dificil, sobre todo en imágenes estáticas como estas:
g %>%
ggraph() +
geom_edge_link(edge_width=.1,alpha=0.5) +
geom_node_point(mapping = aes(color=type,shape=type,size=grado)) + # Pedimos que el size del nodo refiera al grado, y la hacemos a los más grandes más transparentes.
theme_graph()
Using `stress` as default layout
Por eso también suele ser muy útil explorar herramientas para visualización dinámica. En esta área tenemos el paquete visNetwork
# install.packages('visNetwork')
require(visNetwork)
Loading required package: visNetwork
Registered S3 method overwritten by 'htmlwidgets':
method from
print.htmlwidget tools:rstudio
Si bien este paquete en sí mismo permite construir redes y explorarlas, desde nuestra perspectiva de usuaries de igraph
nos interesa simplemente graficar nuestras redes de forma interactiva.
# visIgraph(g) esto ya nos muestra la red pero de forma poco interesante
g %>% activate(nodes) %>%
mutate(label=name,color=ifelse(type=='Drink','red','blue'),size=grado,shape=ifelse(type=='Drink','square','triangle')) %>% #Agregamos directamente columnas con color, forma y tamaño para que los lea visNetwork
visIgraph(layout='layout_nicely',physics=TRUE) %>% # Convertimos a visNetwork y pedimos que tenga movimiento físico
visPhysics(barnesHut=list('damping'=1)) # Hacemos que el movimiento sea leeeento
NA
En cualquier caso, una visualización óptima cuando se incluyen muchos vértices puede ser muy dificultosa.
Si nuestro objetivo es entender cómo se relacionan las bebidas entre sí a través de los ingredientes, pero en sí no nos importan los ingredientes, podemos representar la red original ( bipartita ) como una red monopartita, donde conectamos entre sí a las bebidas que comparten ingredientes. Nuevamente, acá vamos a enfocarnos en la exploración del dataset más que en las técnicas para calcularla (aunque pueden preguntar si les da curiosidad). Con igraph
lo hacemos como
gD = g %>% activate(nodes) %>%
mutate(type=(type=='Drink')) %>% # Igraph necesita que el type sea lógico
bipartite_projection(which='true') %>%
as_tbl_graph()
gD
# A tbl_graph: 420 nodes and 14371 edges
#
# An undirected simple graph with 1 component
#
# Node Data: 420 × 2 (active)
name grado
<chr> <dbl>
1 A1 4
2 ABC 3
3 ACE 5
4 ADAM 3
5 AT&T 3
6 ACID 2
# … with 414 more rows
#
# Edge Data: 14,371 × 3
from to weight
<int> <int> <dbl>
1 1 3 2
2 1 5 1
3 1 13 1
# … with 14,368 more rows
Fijense que igraph
nos borro el atributo type
(que ya no sería útil ya que la red es monopartita) y agrego un atributo weight
a los ejes, que lo que mide es la cantidad de ingredientes en común entre dos bebidas. También se crearon muchísimos ejes nuevos (ahora tenemos del orden de 14000!). La visualización directa de esta red no ayuda mucho, de nuevo debido al número de nodos:
gD %>%
ggraph() +
geom_edge_link(mapping=aes(edge_width=weight,alpha=1/weight)) + # Ponemos el ancho del link en función al peso de ese link
geom_node_point(mapping = aes(size=grado,alpha=1/grado),color='blue') +
theme_graph()
Using `stress` as default layout
Podemos filtrar aquellos ejes que sólo tengan peso mayor a cierto valor:
gD %>%
activate(edges) %>%
filter(weight>3) %>% # Nos quedamos sólo con los ejes que representen al menos tres ingredientes
ggraph() +
geom_edge_link(mapping=aes(edge_width=weight,alpha=1/weight)) +
geom_node_point(color='blue') +
theme_graph()
Using `stress` as default layout
Podemos hacer un histograma sobre los pesos de las conexiones, para ver si las bebidas son parecidas o muy distintas entre sí:
gD %>% activate(edges) %>% as.data.frame() %>%
ggplot(mapping=aes(x=weight)) +
geom_histogram(binwidth = 1,fill='white',col='black')
Este gráfico nos muestra que la mayoría de las bebidas comparten pocos ingredientes. Sin embargo, también hay algunas conexiones grandes, que representan más de 10 ingredientes compartidos.
Basandose en el histograma, prueben hacer cortes sobre los pesos de los ejes y vean las estructuras que se forman. ¿Qué representan los grupos que obtienen? Elijan un número mínimo de ingredientes compartidos para que dos bebidas sean parecidas y apoyandose en el gráfico, identifiquen que grupos de bebidas obtienen. La función clusters
de igraph
les puede ser muy útil. Retorna un vector con las componentes conexas de la red.
(gD %>% activate(edges) %>% filter(weight>2) %>% # Tiramos ejes chicos
clusters())$membership %>% # Pedimos la "membresía" (a qué componente pertenecen) de los nodos
sort() %>% head(n=15)
# Exploren el resultado de clusters!
Repitan el analisis sobre la red monopartita pero de ingredientes en vez de bebidas. ¿Qué representan las conexiones en esa red? ¿Cuál es el ingrediente más versatil?
Por último vamos a hacer un análisis de homofilia en la red de bebidas. Para eso, vamos a considerar las categorías de los distintos tragos. Necesitamos volver al dataset original para recuperar esta información
table(bebidas$strCategory) # Estas son las categorías
Beer Cocktail Cocoa Coffee / Tea Homemade Liqueur Milk / Float / Shake
8 88 5 23 6 6
Ordinary Drink Other/Unknown Punch / Party Drink Shot Soft Drink / Soda
198 23 23 34 6
gD = gD %>% activate(nodes) %>%
mutate(Category=bebidas$strCategory[match(toupper(bebidas$strDrink),name)]) # Agregamos las categorías haciendo un match con el dataframe original
gD %>% activate(nodes) %>% as.data.frame() # Para explorarlo
Con esta información, la pregunta es: ¿Las bebidas de igual categoría comparten más ingredientes que con las de otras categorías?
Para calcular esto nos vamos a volver a ensuciar un poco las manos codeando:
cates = unique(bebidas$strCategory) # Agarramos las categorías
M = matrix(0,nrow=length(cates),ncol=length(cates)) # En esta matriz vamos a guardar el peso de las relaciones entre categorías
ejes = gD %>% activate(edges) %>% as.data.frame() # Agarramos los ejes
nodos = gD %>% activate(nodes) %>% as.data.frame() # y nodos
colnames(M) = rownames(M) = cates # Ponemos nombres a la matriz
for(i in 1:nrow(ejes)){ # Recorremos todos los ejes
eje = ejes[i,] # Agarramos cada fila de ejes
Cfrom = nodos[eje$from,'Category'] # Vemos la categoría del punto de partida
Cto = nodos[eje$to,'Category'] # Igual pero de punto de llegada
M[min(Cfrom,Cto),max(Cfrom,Cto)] = M[min(Cfrom,Cto),max(Cfrom,Cto)] + eje$weight # Guardamos el valor actualizado, sumado lo nuevo.
M[max(Cfrom,Cto),min(Cfrom,Cto)] = M[min(Cfrom,Cto),max(Cfrom,Cto)]
}
M
Cocktail Shot Ordinary Drink Other/Unknown Coffee / Tea Beer Punch / Party Drink Soft Drink / Soda
Cocktail 2324 288 3770 286 133 58 410 48
Shot 288 108 594 54 87 27 102 10
Ordinary Drink 3770 594 5287 656 308 124 958 128
Other/Unknown 286 54 656 119 96 15 181 32
Coffee / Tea 133 87 308 96 198 4 105 5
Beer 58 27 124 15 4 8 24 8
Punch / Party Drink 410 102 958 181 105 24 131 23
Soft Drink / Soda 48 10 128 32 5 8 23 5
Homemade Liqueur 90 37 209 66 118 3 72 0
Cocoa 19 11 45 20 35 0 35 0
Milk / Float / Shake 26 33 73 17 34 2 20 2
Homemade Liqueur Cocoa Milk / Float / Shake
Cocktail 90 19 26
Shot 37 11 33
Ordinary Drink 209 45 73
Other/Unknown 66 20 17
Coffee / Tea 118 35 34
Beer 3 0 2
Punch / Party Drink 72 35 20
Soft Drink / Soda 0 0 2
Homemade Liqueur 28 17 1
Cocoa 17 13 20
Milk / Float / Shake 1 20 10
Exploren y visualicen esta matriz. ¿Qué representa la diagonal en esta matriz? ¿Y los otros elementos? ¿Cuales son las categorías más relacionadas? ¿Hay alguna categoría que se vincule más con otras que con sí misma? ¿Cuál se relaciona en menor proporción?