El laberinto de Falken

El aprendizaje computacional es un área de investigación que en los últimos años ha tenido un auge importante, sobre todo gracias al aprendizaje profundo (Deep Learning). Pero no todo son redes neuronales. Paralelamente a estas técnicas, más bien basadas en el aprendizaje de patrones, también hay un auge de otras técnicas, digamos, más basadas en el aprendizaje simbólico. Si echamos la vista algunos años atrás, podemos considerar que quizá, la promesa de la web semántica como gran base de conocimiento ha fracasado, pero no es tan así. Ha ido transmutándose y evolucionando hacia bases de conocimiento basadas en ontologías a partir de las cuales es posible obtener nuevo conocimiento. Es lo que llamamos razonamiento automático y empresas como Google ya lo utilizan para ofrecerte información adicional sobre tus búsquedas. Ellos lo llaman Grafos de Conocimiento o Knowledge Graphs.


Gracias a estos grafos de conocimiento, Google puede ofrecerte información adicional sobre tu búsqueda, además de los enlaces a las páginas web. Por ejemplo, en la imagen siguiente vemos que si buscamos Marie Curie, Google nos ofrece datos sobre Marie, y otras personas con las que está relacionada.


Para entender como funcionan estos grafos de conocimiento necesitamos tener algunos conceptos previos bien asentados de los que quiero hablaros hoy. Así que para empezar y, como toda esta información se almacena en grandes grafos, hoy vengo hablaros de eso, de grafos.

¿Qué es un grafo?

Matemáticamente, un grafo es un par ordenado \(G=(V,A)\) donde V es un conjunto de vértices (o nodos) y A un conjunto de aristas que relacionan elementos entre sí. Gráficamente se representan como círculos (que son los vértices) unidos por líneas (que son las aristas). Mediante los grafos podemos describir multitud de procesos, situaciones, relaciones, estructuras, etc. Por ejemplo, un grafo nos puede servir para representar los enlaces moleculares de un elemento químico.


Hay situaciones en las que nos interesa especificar que una relación (arista) tiene una dirección concreta. Por ejemplo, en el siguiente grafo se representan los diferentes estados de un semáforo, cuyas aristas tienen definidas una dirección concreta. Por ejemplo, es posible pasar del color amarillo al rojo, pero no al contrario. Este tipo de grafos se llaman digrafos o grafos dirigidos.


Las aristas, además de ser dirigidas, pueden tener un valor o un peso que aporta cierta información acerca de las relaciones. Son los llamados grafos ponderados. En el siguiente grafo, que representa una red de carreteras, vemos que cada arista contiene la distancia en kilómetros que separa cada ciudad. Esto es útil para, por ejemplo, poder calcular la ruta más corta entre dos puntos del grafo.


Os resumo algunas de las métricas básicas de un grafo: el orden del grafo es el número vértices que lo forman, mientras que la medida del grafo es el número de aristas.
El grado de un vértice es el número de aristas que inciden en él. Coincide con el número de vértices adyacentes (por ejemplo, un vértice de grado=0 sería un vértice aislado).
La teoría de grafos es un campo amplio de las matemáticas, así que en vez de aburriros con más términos, iremos definiendo el resto de conceptos que vayamos necesitando sobre la marcha.

Manejo de grafos con NetworkX en Python

Hechas las presentaciones formales, vamos a remangarnos y a ver cómo podemos gestionar grafos en Python, para lo que nos valdremos de la librería NetworkX (hay otras, pero como había que elegir una me he quedado con la que me parecía más sencilla, aunque no necesariamente mejor que las otras). Con el siguiente código vamos a crear un pequeño grafo que relaciona a Kevin Bacon con otros actores con los que ha trabajado (basándonos en la curiosa teoría de los seis grados de separación que cualquier actor tiene con Kevin Bacon).

import networkx as nx

G = nx.Graph() # crear un grafo

#Añadir nodos
G.add_node("Kevin Bacon")
G.add_node("Tom Hanks")
G.add_nodes_from(["Meg Ryan", "Parker Posey", "Lisa Kudrow"])

#Añadir aristas
G.add_edge("Kevin Bacon", "Tom Hanks")
G.add_edge("Kevin Bacon", "Meg Ryan")
G.add_edges_from([("Tom Hanks", "Meg Ryan"), ("Tom Hanks", "Parker Posey")])
G.add_edges_from([("Parker Posey", "Meg Ryan"), ("Parker Posey", "Lisa Kudrow")])

Con nx.Graph() creamos el grafo (podemos usar nx.DiGraph() para crear un grafo dirigido). Para añadir nodos usamos add_node() para añadir un sólo nodo o add_nodes_from() para añadir varios de una vez. Para las aristas usamos add_edge() o add_edges_from() dependiendo de si queremos agregar una o varias aristas.
Si queremos saber el número de nodos y aristas, o qué elementos lo componen, podemos hacerlo fácilmente con:

print(len(G.nodes))
print(len(G.edges))
print(G.nodes)
print(G.edges)

5
6
['Kevin Bacon', 'Tom Hanks', 'Meg Ryan', 'Parker Posey', 'Lisa Kudrow']
[('Kevin Bacon', 'Tom Hanks'), ('Kevin Bacon', 'Meg Ryan'), ('Tom Hanks', 'Meg Ryan'), ('Tom Hanks', 'Parker Posey'), ('Meg Ryan', 'Parker Posey'), ('Parker Posey', 'Lisa Kudrow')]

Es posible asignar atributos tanto a los nodos como a las aristas. Por ejemplo, podemos especificar que Tom Hanks tiene dos Oscars. Respecto a las aristas, como representan que un actor ha trabajado con otro, podemos añadir un atributo que sea la película en la que ambos han coincidido. Un uso muy habitual que tienen los atributos sobre las aristas es indicar el peso si se trata de un grafo ponderado, mediante el atributo weight.

# asignar atributos a nodos y aristas
G.nodes["Tom Hanks"]["oscars"] = 2
G.edges["Kevin Bacon", "Tom Hanks"]["pelicula"] = "Apolo 13"
G.edges["Kevin Bacon", "Meg Ryan"]["pelicula"] = "En carne viva"
G.edges["Parker Posey", "Meg Ryan"]["pelicula"] = "Algo para recordar"
G.edges["Parker Posey", "Tom Hanks"]["pelicula"] = "Tienes un email"
G.edges["Parker Posey", "Lisa Kudrow"]["pelicula"] = "Esperando la hora"
print(G.nodes(data=True))
print(G.edges(data=True))
print(G["Kevin Bacon"])

[('Kevin Bacon', {}), ('Tom Hanks', {'oscars': 2}), ('Meg Ryan', {}), ('Parker Posey', {}), ('Lisa Kudrow', {})]
[('Kevin Bacon', 'Tom Hanks', {'pelicula': 'Apolo 13'}), ('Kevin Bacon', 'Meg Ryan', {'pelicula': 'En carne viva'}), ('Tom Hanks', 'Meg Ryan', {}), ('Tom Hanks', 'Parker Posey', {'pelicula': 'Tienes un email'}), ('Meg Ryan', 'Parker Posey', {'pelicula': 'Algo para recordar'}), ('Parker Posey', 'Lisa Kudrow', {'pelicula': 'Esperando la hora'})]
{'Tom Hanks': {'pelicula': 'Apolo 13'}, 'Meg Ryan': {'pelicula': 'En carne viva'}}

Si quieremos mostrar gráficamente el resultado podemos usar graphviz.

import graphviz

A = nx.nx_agraph.to_agraph(G)
A.layout('dot')
#A.draw('salida.png') # guardar como png

graphviz.Source(A.to_string()) # mostrar en jupyter

Si queremos almacenar nuestro grafo en disco, NetworX tiene una familia de funicones write_*() que facilitan esta operación. Aunque el más habitual es graphml se pueden almacenar en diferentes formatos (como GML, JSON, Pajek, YAML, etc.)

# guardar grafo
nx.write_graphml(G, "actores.graphml")

Para cargar el grafo usamos

# cargar grafo
G2 = nx.read_graphml("actores.graphml")
print(G2.nodes)

Os he contado los rudimentos básicos del manejo de la librería NetworkX. Obviamente esto es sólo una pequeña parte de lo que puede hacer, pero nos vale como introducción. En próximos artículos os seguiré hablando de grafos y os contaré más cosas interesantes.