Análisis de Grafos en Python y NetworkX

Importancia del análisis de grafos

PyShop tiene 3000 pedidos guardados en una tabla. Con un Counter sabes en un segundo qué producto se vende más: los audífonos inalámbricos, en 441 pedidos. Pero la tabla no responde otras preguntas que importan para la tienda: qué productos se compran juntos, cuál conecta mundos que de otra forma no se tocan, qué grupos de productos forman los clientes sin que nadie los haya diseñado. Esas preguntas son sobre relaciones, y las relaciones se estudian con grafos.

Qué preguntas responde un grafo

En la red de PyShop cada nodo es un producto y cada arista une dos productos que aparecieron juntos en al menos 25 pedidos; el peso de la arista es cuántas veces ocurrió. Con esa estructura se responden cuatro tipos de preguntas:

• ¿Quién es clave? Las medidas de centralidad ordenan los nodos según su posición: cuántos vecinos tienen, por cuántos caminos pasan, qué tan cerca están de todos.
• ¿Qué grupos hay? La detección de comunidades encuentra conjuntos de nodos muy conectados entre sí y poco con el resto.
• ¿Qué tan lejos están dos nodos? El camino más corto cuenta los pasos entre ellos; el diámetro, el camino más largo de todos esos caminos cortos.
• ¿Qué tan frágil es la red? Los puentes y los puntos de articulación son las aristas y los nodos cuya eliminación la parte en pedazos.

Por qué una tabla no basta

El siguiente bloque usa las funciones generar_pedidos y red_productos del curso (están en datos.py y en cada notebook). Compara lo que dice la tabla con lo que dice la red:

from collections import Counter
import networkx as nx
from datos import generar_pedidos, red_productos

pedidos = generar_pedidos()
ventas = Counter(p for pedido in pedidos for p in pedido)
print(ventas.most_common(2))

G = red_productos(pedidos)
print(G.number_of_nodes(), G.number_of_edges())
print(nx.shortest_path(G, "tapete de yoga", "laptop"))
bc = nx.betweenness_centrality(G)
print(max(bc, key=bc.get), round(bc["bocina bluetooth"], 3))

Salida:

[('audifonos inalambricos', 441), ('celular gama media', 406)]
41 136
['tapete de yoga', 'bocina bluetooth', 'aspiradora robot', 'laptop']
bocina bluetooth 0.261

La red tiene 41 productos y 136 aristas. El producto con mayor intermediación (la fracción de caminos más cortos que pasan por él) es la bocina bluetooth, con 0.261. En ventas ocupa el lugar 19, con 241 pedidos. Ninguna suma ni promedio sobre la tabla la habría señalado: su importancia viene de que se compra con artículos de audio, de hogar y de deportes, y por eso aparece en el camino de un tapete de yoga a una laptop. Esa es la idea central del curso: la posición de un nodo en la red es información que no está en ninguna fila.

Una primera medida de la red completa es la densidad, la fracción de aristas posibles que existen. Con $n$ nodos y $m$ aristas en un grafo no dirigido:

$$D = \frac{2m}{n(n-1)} = \frac{2 \cdot 136}{41 \cdot 40} \approx 0.166$$

Solo existe 1 de cada 6 pares posibles.

Dónde se usa el análisis de grafos

• Buscadores web. Brin y Page describieron en 1998 el prototipo de Google, que usaba la estructura de enlaces entre páginas para ordenar resultados con PageRank. En el curso lo calcularás con nx.pagerank.
• Redes sociales. Wayne Zachary registró en 1977 las amistades de un club de karate que se dividió en dos. Ese grafo viene en NetworkX (nx.karate_club_graph()) y servirá para comprobar si los algoritmos de comunidades recuperan la división real.
• Epidemiología. En una red de contactos los nodos son personas y las aristas, contactos o contagios. La guía oficial de NetworkX sobre hantavirus reconstruye como grafo dirigido la cadena de transmisión de un brote en Argentina publicado en el New England Journal of Medicine, con «superpropagadores».
• Fraude. Las cuentas de un anillo de fraude suelen verse normales una por una; lo que las delata es lo que comparten (dispositivos, direcciones, medios de pago). Detectar comunidades densas en esa red es una técnica habitual.
• Biología. Jeong, Mason, Barabási y Oltvai (Nature, 2001) analizaron la red de interacción de proteínas de la levadura y encontraron que eliminar una proteína con muchas conexiones tiene más probabilidad de ser letal para la célula.
• Recomendación. El proyecto SNAP de Stanford publica una red de productos de Amazon de 2003 (262,111 productos y 1,234,877 aristas) construida con la sección «los clientes que compraron este artículo también compraron». Es la misma idea que la red de PyShop, a otra escala.

Mapa del curso

Instalas NetworkX y aprendes a leer su documentación; creas y manipulas grafos; mides su estructura y la importancia de cada nodo con cinco medidas de centralidad; dibujas la red y la divides en comunidades. El proyecto final junta todo en un análisis de la red de PyShop con recomendaciones.

Trampas comunes

• Confundir lo más vendido con lo más importante. Los audífonos inalámbricos lideran en ventas; la bocina bluetooth lidera como puente. Son preguntas distintas.
• Olvidar que la red depende de cómo se construye. Con un mínimo de 1 pedido en común la red de PyShop tiene 594 aristas y densidad 0.724; con 25, 136 aristas y 0.166. El umbral es una decisión que se justifica.
• Leer causalidad en una arista. Que dos productos se compren juntos no significa que uno provoque la compra del otro.

Antes de construir cualquier red, escribe la pregunta que quieres responder y qué serán los nodos, las aristas y los pesos. Esa decisión determina todo lo que viene después.