Ir al contenido principal

Manejo de grafos con NetworkX en Python

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 en una serie de artículos (aun no sé cuantos). 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.

Comentarios

  1. Hola,
    Muchas gracias por este primer artículo sobre grafos.
    Espero con muchas ganas las próximas entregas!!
    Saludos,

    ResponderEliminar

Publicar un comentario

Entradas populares de este blog

Criptografía en Python con PyCrypto

A la hora de cifrar información con Python, tenemos algunas opciones, pero una de las más fiables es la librería criptográfica PyCrypto, que soporta funciones para cifrado por bloques, cifrado por flujo y cálculo de hash. Además incorpora sus propios generadores de números aleatorios. Seguidamente os presento algunas de sus características y también como se usa.


Regresión lineal y descenso de gradiente con Python

En machine learning, el objetivo principal es encontrar un modelo que explique el comportamiento de un sistema (en el amplio sentido de la palabra). A partir de unos datos de entrenamiento, un sistema de aprendizaje automático ha de ser capaz de inferir un modelo capaz de explicar, al menos en su mayoría, los efectos observados. Pero también aplicar ese aprendizaje. Por ejemplo, un sistema de machine learning muy lucrativo para las empresas anunciantes es aquél que dado un perfil de usuario (datos de entrada A), sea capaz de predecir si pinchará o no (salida B) sobre un anuncio publicitario de, por ejemplo, comida para gatos. No es sencillo crear un modelo capaz de predecir el comportamiento del usuario (o sí), pero en todo caso, existen diferentes técnicas que nos permiten abordar el problema. En el caso del ejemplo que acabamos de ver, el modelo debería ser capaz de clasificar a los usuarios en dos clases diferentes, los que pulsarán y los que no pulsarán el anuncio de comida de ga…

Manipulación de datos con pandas

Cuando uno lee un libro o un artículo sobre machine learning encuentra multitud de explicaciones sobre el algoritmo tal o cual. Sin embargo, no se habla demasiado sobre la manipulación y el limpiado de los datos, que bajo mi punto de vista es tan o incluso más importante que utilizar el algoritmo adecuado. Nuestro aliado en esta tarea es la librería pandas.
En lugar de hacer un recorrido exhaustivo por las funcionalidades de la librería, he preferido hacer uso de ella con un dataset real, para poder ver así, no sólo cuáles son sus funcionalidades, sino también cómo se aplican a datos reales. Así pues, en lugar de usar un dataset de los clásicos, he recurrido a uno real sacado de la web de datos abiertos del Ayuntamiento de Málaga. En concreto vamos a trabajar con el siguiente dataset, que se corresponde con las lecturas energéticas de los cuadros eléctricos durante el mes de marzo de 2017: https://datosabiertos.malaga.eu/dataset/lecturas-cuadros-electricos-marzo-2017.
Como siempre os…