5.3 · Minería de grafos a escala

¿Por qué minería de grafos?

Muchos de los datasets más grandes del mundo no son tablas, son grafos: la web (páginas y enlaces), las redes sociales (personas y relaciones), las redes de citas científicas, las transacciones financieras o las redes de transporte. Analizar su estructura responde preguntas como: ¿qué páginas son más importantes?, ¿quiénes son los usuarios más influyentes?, ¿qué grupos de cuentas podrían ser fraude coordinado?

El reto es la escala: el grafo de la web tiene miles de millones de nodos. Un algoritmo de grafos clásico en una sola máquina no es viable; hacen falta procesamiento distribuido y algoritmos diseñados para iterar sobre vecindades sin recorrer el grafo entero.

Representación de grafos

Las formas habituales de representar un grafo G = (V, E):

En sistemas distribuidos (GraphX, GraphFrames) el grafo se almacena como dos colecciones: un DataFrame/RDD de vértices (id, atributos) y otro de aristas (origen, destino, atributos), particionados por el clúster.

Los grafos reales suelen ser dispersos: cada nodo se conecta con una fracción ínfima del total. Por eso la matriz de adyacencia completa casi nunca se usa a gran escala.

PageRank: medir la importancia

PageRank (el algoritmo original de Google) asigna a cada página una puntuación de importancia basada en los enlaces que recibe: un enlace desde una página importante vale más que uno desde una página marginal.

La idea es el navegante aleatorio: con probabilidad d (el damping factor, típicamente 0.85) sigue un enlace al azar de la página actual; con probabilidad 1 − d “se teletransporta” a cualquier página del grafo. El PageRank de cada nodo es la fracción de tiempo que el navegante pasa en él a largo plazo.

La fórmula iterativa para el nodo v:

PR(v) = (1 - d) / N  +  d · Σ  PR(u) / outDegree(u)
                           u → v

• N: número total de nodos.
• La suma recorre todos los nodos u que enlazan a v.
• Cada u reparte su PageRank a partes iguales entre sus enlaces salientes.

El proceso: se inicializa PR(v) = 1/N para todos, se aplica la fórmula repetidamente y los valores convergen tras unas pocas decenas de iteraciones.

graph TD
A["Página A<br/>PR inicial 1/4"] -->|"reparte PR/2"| B["Página B"]
A -->|"reparte PR/2"| C["Página C"]
B -->|"reparte todo su PR"| C
C -->|"reparte todo su PR"| A
D["Página D<br/>(sin salidas)"] -.->|"teletransportacion 1-d"| A
C -->|"PR alto: recibe de A y B"| CC["C converge como la mas importante"]

Dos detalles prácticos:

• Nodos colgantes (sin enlaces salientes, como D): no reparten nada y “fugarían” masa de PageRank. Se soluciona redistribuyendo su puntuación entre todos los nodos (equivalente a la teletransportación).
• Damping factor d: controla el equilibrio entre seguir la estructura del grafo (d alto) y explorar al azar (d bajo). El valor 0.85 es el estándar histórico.

Detección de comunidades

Una comunidad es un grupo de nodos densamente conectados entre sí y poco conectados con el resto: grupos de amigos, áreas temáticas de la web, células de fraude.

Algoritmos clásicos a escala:

• Label Propagation: cada nodo adopta la etiqueta mayoritaria de sus vecinos, iterativamente, hasta estabilizarse. Muy barato y paralelizable; resultado aproximado.
• Louvain: optimiza la modularidad (mide cuánto más densas son las conexiones internas de las comunidades frente a un grafo aleatorio). Más preciso, más costoso.
• Componentes conexas: el caso más simple; agrupa nodos alcanzables entre sí.

GraphX y GraphFrames

Ambos siguen el modelo Pregel (“piensa como un vértice”): en cada superpaso, cada vértice recibe mensajes de sus vecinos, actualiza su estado y envía mensajes nuevos. Este patrón hace que algoritmos como PageRank se ejecuten de forma natural en paralelo, con cada nodo del clúster encargado de un subconjunto de vértices.

Aplicaciones

• Búsqueda web: PageRank y sus variantes (personalizado, temático) para ordenar resultados.
• Redes sociales: detección de influencers (centralidad), sugerencia de amigos (conteo de triángulos, vecinos comunes), comunidades.
• Detección de fraude: anillos de cuentas que se transfieren dinero entre sí forman comunidades sospechosamente densas.
• Biología: redes de interacción de proteínas para identificar genes esenciales.

Ejercicio: PageRank iterativo

grafo = {
  "A": ["B", "C"],
  "B": ["C"],
  "C": ["A"],
  "D": ["C"],
}

d = 0.85
N = len(grafo)
iteraciones = 20

# Inicializar todos los nodos con 1/N
pr = {nodo: 1.0 / N for nodo in grafo}

for i in range(iteraciones):
  nuevo = {nodo: (1 - d) / N for nodo in grafo}
  for u, vecinos in grafo.items():
      reparto = pr[u] / len(vecinos)
      for v in vecinos:
          nuevo[v] += d * reparto
  pr = nuevo

# Resultados ordenados de mayor a menor PageRank
for nodo, valor in sorted(pr.items(), key=lambda x: x[1], reverse=True):
  print(f"{nodo}: {valor:.4f}")

print(f"Suma total (debe ser ~1): {sum(pr.values()):.4f}")

Comprueba lo aprendido

Resumen

• Los grafos a escala se representan distribuidos como colecciones de vértices y aristas (listas de adyacencia o de aristas, nunca matrices densas).
• PageRank mide la importancia por los enlaces recibidos, repartiendo el peso entre enlaces salientes y usando el damping factor (0.85) con teletransportación para garantizar convergencia.
• Los nodos colgantes requieren redistribuir su masa para no perder PageRank.
• La detección de comunidades (label propagation, Louvain) encuentra grupos densamente conectados: amigos, temas, fraude.
• GraphX y GraphFrames ejecutan estos algoritmos en Spark siguiendo el modelo Pregel de paso de mensajes entre vértices.
• Aplicaciones: buscadores web, redes sociales, detección de fraude y biología computacional.

📚 Lecturas y fuentes