Grafique la ciencia de datos con Python/NetworkX

Estamos inundados de datos. Las bases de datos y las hojas de cálculo en constante expansión están llenas de información comercial oculta. ¿Cómo podemos analizar datos y extraer conclusiones cuando hay tantos? Los gráficos (redes, no gráficos de barras) proporcionan un enfoque elegante.

A menudo usamos tablas para representar información de forma genérica. Pero los gráficos usan una estructura de datos especializada: en lugar de una fila de tabla, un nodo representa un elemento. Un borde conecta dos nodos para indicar su relación.

Esta estructura de datos de gráficos nos permite observar datos desde ángulos únicos, razón por la cual la ciencia de datos de gráficos se utiliza en todos los campos, desde la biología molecular hasta las ciencias sociales:

Entonces, ¿cómo pueden los desarrolladores aprovechar la ciencia de datos de gráficos? Pasemos al lenguaje de programación de ciencia de datos más utilizado: Python.

Primeros pasos con los gráficos de "Teoría de grafos" en Python

Los desarrolladores de Python tienen varias bibliotecas de datos gráficos disponibles, como NetworkX, igraph, SNAP y graph-tool. Dejando a un lado los pros y los contras, tienen interfaces muy similares para manejar y procesar estructuras de datos de gráficos de Python.

Usaremos la popular biblioteca NetworkX. Es fácil de instalar y usar, y es compatible con el algoritmo de detección de la comunidad que usaremos.

Crear un nuevo gráfico con NetworkX es sencillo:

 import networkx as nx G = nx.Graph()

Pero G todavía no es un gran gráfico, ya que carece de nodos y bordes.

Cómo agregar nodos a un gráfico

Podemos agregar un nodo a la red encadenando el valor de retorno de Graph() con .add_node() (o .add_nodes_from() para múltiples nodos en una lista). También podemos agregar características o atributos arbitrarios a los nodos pasando un diccionario como parámetro, como mostramos con node 4 y node 5 :

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

Esto generará:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

Pero sin bordes entre nodos, están aislados y el conjunto de datos no es mejor que una simple tabla.

Cómo agregar bordes a un gráfico

Similar a la técnica para los nodos, podemos usar .add_edge() con los nombres de dos nodos como parámetros (o .add_edges_from() para múltiples bordes en una lista), y opcionalmente incluir un diccionario de atributos:

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

La biblioteca NetworkX admite gráficos como estos, donde cada borde puede tener un peso. Por ejemplo, en un gráfico de red social donde los nodos son usuarios y los bordes son interacciones, el peso podría significar cuántas interacciones ocurren entre un par de usuarios determinado, una métrica muy relevante.

NetworkX enumera todos los bordes cuando se usa G.edges , pero no incluye sus atributos. Si queremos atributos de borde, podemos usar G[node_name] para obtener todo lo que está conectado a un nodo o G[node_name][connected_node_name] para obtener los atributos de un borde en particular:

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

Esto generará:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

Pero leer nuestro primer gráfico de esta manera no es práctico. Afortunadamente, hay una representación mucho mejor.

Cómo generar imágenes a partir de gráficos (y gráficos ponderados)

Visualizar un gráfico es fundamental: Nos permite ver las relaciones entre los nodos y la estructura de la red de forma rápida y clara.

Una llamada rápida a nx.draw(G) es todo lo que se necesita:

Hagamos los bordes más pesados ​​correspondientemente más gruesos a través de nuestra llamada nx.draw() :

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

Proporcionamos un grosor predeterminado para los bordes sin peso, como se ve en el resultado:

Nuestros métodos y algoritmos gráficos están a punto de volverse más complejos, por lo que el siguiente paso es utilizar un conjunto de datos más conocido.

Grafique la ciencia de datos utilizando datos de la película Star Wars: Episodio IV

Para facilitar la interpretación y comprensión de nuestros resultados, utilizaremos este conjunto de datos. Los nodos representan personajes importantes y los bordes (que no se ponderan aquí) significan la aparición conjunta en una escena.

Nota: El conjunto de datos es de Gabasova, E. (2016). Red social de Star Wars. DOI: https://doi.org/10.5281/zenodo.1411479.

Primero, visualizaremos los datos con nx.draw(G_starWars, with_labels = True) :

Los personajes que suelen aparecer juntos, como R2-D2 y C-3PO, aparecen estrechamente conectados. En cambio, podemos ver que Darth Vader no comparte escenas con Owen.

Diseños de visualización de Python NetworkX

¿Por qué cada nodo está ubicado donde está en el gráfico anterior?

Es el resultado del algoritmo spring_layout predeterminado. Simula la fuerza de un resorte, atrayendo nodos conectados y repeliendo los desconectados. Esto ayuda a resaltar los nodos bien conectados, que terminan en el centro.

NetworkX tiene otros diseños que utilizan diferentes criterios para posicionar los nodos, como circular_layout :

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

El resultado:

Este diseño es neutral en el sentido de que la ubicación de un nodo no depende de su importancia: todos los nodos se representan por igual. (El diseño circular también podría ayudar a visualizar componentes conectados separados, subgráficos que tienen una ruta entre dos nodos, pero aquí, el gráfico completo es un gran componente conectado).

Ambos diseños que hemos visto tienen un grado de desorden visual porque los bordes son libres de cruzar otros bordes. Pero Kamada-Kawai, otro algoritmo dirigido por fuerza como spring_layout , posiciona los nodos para minimizar la energía del sistema.

Esto reduce el cruce de bordes, pero tiene un precio: es más lento que otros diseños y, por lo tanto, no es muy recomendable para gráficos con muchos nodos.

Este tiene una función de dibujo especializada:

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

Eso produce esta forma en su lugar:

Sin ninguna intervención especial, el algoritmo colocó a los personajes principales (como Luke, Leia y C-3PO) en el centro y a los menos prominentes (como Camie y el general Dodonna) en el borde.

Visualizar el gráfico con un diseño específico puede darnos algunos resultados cualitativos interesantes. Aún así, los resultados cuantitativos son una parte vital de cualquier análisis de ciencia de datos, por lo que necesitaremos definir algunas métricas.

Análisis de Nodos: Grado y PageRank

Ahora que podemos visualizar claramente nuestra red, nos puede interesar caracterizar los nodos. Existen múltiples métricas que describen las características de los nodos y, en nuestro ejemplo, de los personajes.

Una métrica básica para un nodo es su grado: cuántos bordes tiene. El grado del nodo de un personaje de Star Wars mide con cuántos otros personajes compartió una escena.

La función degree() puede calcular el grado de un carácter o de toda la red:

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

La salida de ambos comandos:

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

La clasificación de los nodos de mayor a menor según el grado se puede hacer con una sola línea de código:

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

La salida:

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

Al ser solo un total, el grado no tiene en cuenta los detalles de los bordes individuales. ¿Un borde dado se conecta a un nodo aislado o a un nodo que está conectado con toda la red? El algoritmo PageRank de Google agrega esta información para medir qué tan "importante" es un nodo en una red.

La métrica de PageRank se puede interpretar como un agente que se mueve aleatoriamente de un nodo a otro. Los nodos mejor conectados tienen más rutas que los atraviesan, por lo que el agente tenderá a visitarlos con más frecuencia.

Dichos nodos tendrán un PageRank más alto, que podemos calcular con la biblioteca NetworkX:

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

Esto imprime el rango de Luke y nuestros personajes ordenados por rango:

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

Owen es el personaje con el PageRank más alto, superando a Luke, que tenía el grado más alto. El análisis: Aunque Owen no es el personaje que más escenas comparte con otros personajes, es un personaje que comparte escenas con muchos personajes importantes como el propio Luke, R2-D2 y C-3PO.

En mayor contraste, C-3PO, el personaje con el tercer grado más alto, es el que tiene el PageRank más bajo. A pesar de que C-3PO tiene muchas conexiones, muchas de ellas son con personajes sin importancia.

La conclusión: el uso de múltiples métricas puede brindar una visión más profunda de las diferentes características de los nodos de un gráfico.

Algoritmos de detección de la comunidad

Al analizar una red, puede ser importante separar las comunidades : grupos de nodos que están muy conectados entre sí pero mínimamente conectados con nodos fuera de su comunidad.

Hay varios algoritmos para esto. La mayoría de ellos se encuentran dentro de algoritmos de aprendizaje automático no supervisados ​​porque asignan una etiqueta a los nodos sin necesidad de que hayan sido etiquetados previamente.

Uno de los más famosos es la propagación de etiquetas . En él, cada nodo comienza con una etiqueta única, en una comunidad de uno. Las etiquetas de los nodos se actualizan iterativamente de acuerdo con la mayoría de las etiquetas de los nodos vecinos.

Las etiquetas se difunden a través de la red hasta que todos los nodos comparten una etiqueta con la mayoría de sus vecinos. Grupos de nodos estrechamente conectados entre sí terminan teniendo la misma etiqueta.

Con la biblioteca NetworkX, ejecutar este algoritmo requiere solo tres líneas de Python:

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

La salida:

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

En esta lista de conjuntos, cada conjunto representa una comunidad. Los lectores familiarizados con la película notarán que el algoritmo logró separar perfectamente a los "buenos" de los "malos", diferenciando a los personajes de manera significativa sin usar ninguna etiqueta o metadatos verdaderos (comunitarios).

Perspectivas inteligentes utilizando Graph Data Science en Python

Hemos visto que comenzar con las herramientas de ciencia de datos de gráficos es más sencillo de lo que parece. Una vez que representamos los datos como un gráfico usando la biblioteca NetworkX en Python, unas pocas líneas de código pueden ser esclarecedoras. Podemos visualizar nuestro conjunto de datos, medir y comparar las características de los nodos y agrupar los nodos de manera sensata a través de algoritmos de detección de la comunidad.

Tener la habilidad de extraer conclusiones y conocimientos de una red usando Python permite a los desarrolladores integrarse con herramientas y metodologías que se encuentran comúnmente en las canalizaciones de servicios de ciencia de datos. Desde los motores de búsqueda hasta la programación de vuelos y la ingeniería eléctrica, estos métodos se aplican fácilmente a una amplia variedad de contextos.

Lectura recomendada sobre ciencia de datos gráficos

Algoritmos de detección de la comunidad
Zhao Yang, René Algesheimer y Claudio Tessone. "Un análisis comparativo de algoritmos de detección comunitaria en redes artificiales". Informes científicos, 6, no. 30750 (2016).

Graficar aprendizaje profundo
Tomás Kipf. "Redes convolucionales gráficas". 30 de septiembre de 2016.

Aplicaciones de la ciencia de datos gráficos
Albanese, Federico, Leandro Lombardi, Esteban Feuerstein, and Pablo Balenzuela. "Predicción de personas cambiantes mediante la minería de texto y el aprendizaje automático de gráficos en Twitter". (24 de agosto de 2020): arXiv:2008.10749 [cs.SI].

Cohen, Elior. "Reunión PyData Tel Aviv: Node2vec". YouTube. 22 de noviembre de 2018. Vídeo, 21:09. https://www.youtube.com/watch?v=828rZgV9t1g.