El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
HOME Mis cursos Finalizados
◄ Anterior
◄

Aplicaciones de Grafos en Redes Sociales

Siguiente ►
►

En la lección anterior encadenaste optimización, asignación y rutas para la operativa de Rutalia. Ahora cambiamos de dominio: las redes sociales, probablemente el mayor consumidor de algoritmos de grafos del mundo. La buena noticia es que no hay casi nada nuevo que aprender de mecánica: el BFS de 03-02, el union-find de 01-04, Dijkstra de 03-03 y el clustering jerárquico de 05-05 son exactamente las piezas que usan estos sistemas. Lo nuevo es el modelado: qué pregunta de negocio ("¿quién es influyente?", "¿a quién le sugiero como amigo?") se traduce a qué propiedad del grafo. Desarrollaremos una pieza estrella —PageRank— y trabajaremos sobre una red sintética con usuarios ficticios U-nnn, inspirada en la comunidad de repartidores y clientes de Rutalia.

Contenido

  1. Una red social es un grafo (y las decisiones de modelado importan)
  2. Construir la red sintética: preferencia de enlace y hubs
  3. Mundo pequeño: el experimento de los 6 grados con BFS
  4. Componentes y comunidades
  5. Centralidades: ¿quién importa en la red?
  6. PageRank: el surfista aleatorio, desarrollado
  7. Recomendación de amistades: amigos en común y Jaccard
  8. Difusión y viralidad: BFS como modelo de propagación
  9. Privacidad: lo que no debes hacer con datos sociales reales

Una red social es un grafo (y las decisiones de modelado importan)

El modelado base es directo: cada usuario es un nodo y cada relación una arista. Pero la primera decisión ya tiene consecuencias algorítmicas:

Red Relación Tipo de grafo Consecuencia
Facebook, LinkedIn amistad / contacto (mutua) no dirigido "amigos en común" es simétrico; componentes con union-find
Twitter/X, Instagram, TikTok seguir (no mutua) dirigido grado de entrada ≠ salida; influencia = aristas entrantes
WhatsApp / mensajería conversaciones con frecuencia no dirigido ponderado los pesos alimentan Dijkstra (03-03) para "cercanía real"
Comunidad de Rutalia repartidor atiende habitualmente a cliente bipartito emparejamiento (03-06) y recomendación por co-ocurrencia

Es la misma disyuntiva de representación que viste en 03-01 (lista vs matriz de adyacencia) elevada al nivel semántico: antes elegías cómo almacenar el grafo; ahora eliges qué es el grafo. En esta lección usaremos un grafo no dirigido (relaciones mutuas) salvo en PageRank, donde el sentido de la arista es la esencia.

Construir la red sintética: preferencia de enlace y hubs

Las redes sociales reales no son aleatorias uniformes: unos pocos nodos acumulan muchísimas conexiones (hubs) y la mayoría tiene pocas. El mecanismo generador clásico es la preferencia de enlace (preferential attachment, modelo de Barabási-Albert): cada usuario nuevo tiende a conectarse con quien ya está bien conectado — "los ricos se hacen más ricos". Lo implementamos con un truco elegante: mantener una lista donde cada nodo aparece una vez por cada arista que toca; muestrear uniformemente de esa lista equivale a muestrear proporcionalmente al grado.

import random
from collections import deque, defaultdict

random.seed(7)

def red_preferencial(n, m=2):
    """Red de n usuarios; cada nuevo usuario crea m enlaces
    con probabilidad proporcional al grado (Barabási-Albert)."""
    ady = defaultdict(set)
    bolsa = []                       # cada nodo aparece tantas veces como su grado
    nodos = [f"U-{i:03d}" for i in range(1, n + 1)]
    # núcleo inicial: los m+1 primeros, todos conectados entre sí
    for i in range(m + 1):
        for j in range(i + 1, m + 1):
            ady[nodos[i]].add(nodos[j]); ady[nodos[j]].add(nodos[i])
            bolsa += [nodos[i], nodos[j]]
    for k in range(m + 1, n):
        nuevo = nodos[k]
        destinos = set()
        while len(destinos) < m:
            destinos.add(random.choice(bolsa))   # proporcional al grado
        for d in destinos:
            ady[nuevo].add(d); ady[d].add(nuevo)
            bolsa += [nuevo, d]
    return ady

red = red_preferencial(300)
grados = sorted(((len(v), u) for u, v in red.items()), reverse=True)
print("Top 5 hubs:", [(u, g) for g, u in grados[:5]])
print("Grado mediano:", sorted(len(v) for v in red.values())[150])

El resultado típico: los hubs superan las 30-40 conexiones mientras el usuario mediano tiene 2-4. Esa desigualdad extrema (distribución de "cola larga") es la firma de las redes sociales reales, y explica por qué el marketing busca hubs y por qué un fallo en un hub (o su cuenta comprometida) afecta a media red.

Mundo pequeño: el experimento de los 6 grados con BFS

En 1967 Milgram pidió a personas de Nebraska hacer llegar una carta a un desconocido de Boston pasándola solo entre conocidos: la mediana fue ~6 saltos. En nuestro grafo, "número de saltos entre dos usuarios" es exactamente la distancia en aristas, y el algoritmo para calcularla desde un origen es el BFS de 03-02 — sin cambios, solo reinterpretado.

def bfs_distancias(red, origen):
    """Distancias en saltos desde origen (BFS de 03-02, tal cual)."""
    dist = {origen: 0}
    cola = deque([origen])
    while cola:
        u = cola.popleft()
        for v in red[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                cola.append(v)
    return dist

# Distancia media entre 200 parejas al azar
nodos = list(red)
muestras = []
for _ in range(200):
    a, b = random.sample(nodos, 2)
    d = bfs_distancias(red, a)
    if b in d:
        muestras.append(d[b])
print(f"Distancia media: {sum(muestras)/len(muestras):.2f} saltos, máxima: {max(muestras)}")

Con 300 usuarios y solo 2 enlaces por usuario nuevo, la distancia media ronda 3-4 saltos y casi nunca supera 6. Esa es la propiedad de mundo pequeño: el diámetro crece como O(log n), no como O(n), porque los hubs actúan de atajos. Consecuencia práctica: cualquier cosa que se propague por la red (información, rumores, malware) puede alcanzar a casi todos en muy pocos pasos — lo cuantificaremos en la sección de difusión.

Componentes y comunidades

Componentes conexas — ¿la red está entera o fragmentada? Dos herramientas que ya tienes: BFS/DFS repetidos (03-02) o union-find (01-04), que además soporta el caso incremental (las amistades llegan como un stream de eventos y quieres saber en todo momento si dos usuarios están conectados, sin recalcular nada). En redes con preferencia de enlace todo acaba en una componente gigante; en redes reales suele haber una componente gigante (~90 % de usuarios) y polvo de componentes minúsculas.

Comunidades son otra cosa: grupos dentro de la misma componente con muchas aristas internas y pocas hacia fuera (la pandilla del barrio, los compañeros de trabajo). Dos enfoques con piezas del curso:

  • Aglomerativo (abajo-arriba). Es el clustering jerárquico de 05-05 aplicado al grafo: si defines la similitud entre usuarios como el Jaccard de sus vecindarios (lo veremos en recomendación) y fusionas los pares más similares, el dendrograma revela comunidades. Recuerda la equivalencia que descubriste en 05-05: single-linkage = Kruskal (03-04); aquí el "bosque que se va fusionando" son las comunidades creciendo.
  • Divisivo (arriba-abajo): la idea de Girvan-Newman. En lugar de unir lo similar, corta lo que separa. Las aristas "puente" entre comunidades tienen una propiedad medible: muchos caminos mínimos pasan por ellas (si solo hay un puente entre dos barrios, todo camino inter-barrio lo cruza). Esa medida se llama betweenness (intermediación) de arista y se calcula con BFS desde cada nodo. El algoritmo conceptual:
flowchart TD
    A[Calcular betweenness<br>de cada arista con BFS] --> B[Eliminar la arista<br>de mayor betweenness]
    B --> C{¿Se partió el grafo<br>en más componentes?}
    C -->|no| A
    C -->|sí| D[Cada componente<br>es una comunidad candidata]
    D -->|seguir cortando<br>para comunidades más finas| A

No lo implementaremos completo (el cálculo eficiente de betweenness es delicado y O(n·m) por iteración lo hace caro en redes grandes — por eso en producción se usan métodos más rápidos como Louvain, que optimizan una medida llamada modularidad), pero la intuición es lo transferible: comunidad = región densa; frontera = aristas por donde se cuelan todos los caminos.

Centralidades: ¿quién importa en la red?

"Importante" no es una sola cosa. Cada definición matemática de centralidad responde a una pregunta de negocio distinta:

Centralidad Definición Se calcula con Pregunta que responde
Grado nº de conexiones contar (O(1) por nodo) ¿Quién tiene más audiencia directa?
Cercanía inverso de la distancia media al resto BFS desde el nodo (03-02); Dijkstra si hay pesos (03-03) ¿Quién difunde algo más rápido a toda la red?
Intermediación fracción de caminos mínimos que pasan por el nodo BFS desde todos los nodos ¿Quién es el puente cuya caída fragmenta la red?
PageRank importancia recursiva: te apuntan nodos importantes iteración de punto fijo (siguiente sección) ¿Quién es influyente de verdad, no solo popular? 
def cercania(red, u):
    d = bfs_distancias(red, u)
    alcanzados = [x for x in d.values() if x > 0]
    return len(alcanzados) / sum(alcanzados) if alcanzados else 0.0

top_grado = max(red, key=lambda u: len(red[u]))
top_cerca = max(red, key=lambda u: cercania(red, u))
print("Mayor grado:", top_grado, "| mayor cercanía:", top_cerca)

En redes con hubs, grado y cercanía suelen coincidir en la cúspide, pero se separan en cuanto la red tiene estructura de comunidades: un nodo de grado modesto situado entre dos comunidades puede tener cercanía (y sobre todo intermediación) altísima. Ese matiz —popular ≠ bien situado— es el que motiva la siguiente sección.

PageRank: el surfista aleatorio, desarrollado

El grado cuenta cuántos te apuntan; PageRank pondera quiénes. Nació para ordenar la web (una recomendación de una página importante vale más que cien de páginas irrelevantes) y se usa igual en redes sociales: un "sigue" de un usuario influyente pesa más que diez de cuentas vacías. Aquí el grafo es dirigido: la arista u→v significa "u sigue a v" (o "u enlaza a v").

La idea del surfista aleatorio. Imagina un usuario que navega eternamente: en cada paso, con probabilidad d (el damping, típicamente 0,85) salta a un seguido/enlace al azar del nodo actual, y con probabilidad 1−d se teletransporta a un nodo cualquiera de la red (se "aburre" y empieza de nuevo). El PageRank de un nodo es la fracción del tiempo que el surfista pasa en él a largo plazo. El teletransporte no es un adorno: sin él, el surfista quedaría atrapado en callejones sin salida y en ciclos, y el proceso no convergería a nada útil.

Formulación iterativa. Traducimos la historia a una ecuación de punto fijo, con N nodos:

PR(v) = (1 - d)/N  +  d * Σ  PR(u) / salida(u)     para cada u que apunta a v

Cada nodo reparte su rango a partes iguales entre sus salidas; el término (1−d)/N es el teletransporte. Se itera desde un reparto uniforme hasta que los valores dejan de moverse — la misma filosofía de iteración hasta punto fijo que viste en Bellman-Ford (03-03) y en k-means (05-05).

def pagerank(salidas, d=0.85, iters=100, tol=1e-10):
    """salidas: dict nodo -> conjunto de nodos a los que apunta."""
    nodos = set(salidas) | {v for s in salidas.values() for v in s}
    N = len(nodos)
    pr = {u: 1.0 / N for u in nodos}          # reparto inicial uniforme
    for _ in range(iters):
        nuevo = {u: (1 - d) / N for u in nodos}
        for u in nodos:
            destinos = salidas.get(u, set())
            if destinos:
                cuota = pr[u] / len(destinos)     # reparte su rango
                for v in destinos:
                    nuevo[v] += d * cuota
            else:
                # nodo sin salidas ("colgante"): reparte a toda la red,
                # como si el surfista se teletransportara siempre desde él
                for v in nodos:
                    nuevo[v] += d * pr[u] / N
        if sum(abs(nuevo[u] - pr[u]) for u in nodos) < tol:
            break
        pr = nuevo
    return pr

# Red dirigida de ejemplo: quién sigue a quién
sigue = {
    "U-001": {"U-002"},
    "U-002": {"U-003"},
    "U-003": {"U-001"},
    "U-004": {"U-003"},
    "U-005": {"U-003"},
    "U-006": {"U-003"},
    "U-007": {"U-004"},          # sigue al que sigue al hub
}
pr = pagerank(sigue)
for u, r in sorted(pr.items(), key=lambda kv: -kv[1]):
    print(f"{u}: {r:.4f}")

Observa el resultado: U-003 gana con claridad (le apuntan cuatro nodos), pero lo interesante es lo demás. U-001 puntúa más alto que U-004 pese a que a ambos les apunta un solo nodo — porque a U-001 le apunta el propio U-003, que es importante, mientras que a U-004 le apunta el periférico U-007. Eso es exactamente "no cuenta cuántos te apuntan, sino quiénes", y ningún recuento de grado lo captura. Detalles del código que importan:

  • Nodos colgantes (sin salidas): si no repartieran su rango, el sistema "perdería masa" en cada iteración. La solución estándar es que repartan a toda la red.
  • Convergencia: garantizada con d < 1; con d = 0,85 bastan unas decenas de iteraciones. Cada iteración cuesta O(nodos + aristas): PageRank escala a grafos de miles de millones de aristas (así se calculaba sobre toda la web).
  • El damping como perilla: d → 1 da más peso a la estructura de enlaces (y converge más lento); d → 0 aplana todo hacia el uniforme.

Recomendación de amistades: amigos en común y Jaccard

"Personas que quizá conozcas" es, en su núcleo, un problema de caminos de longitud 2: si U-042 y U-107 no son amigos pero comparten 8 amigos, probablemente se conozcan. Contar amigos comunes favorece a los hubs (comparten amigos con todo el mundo); la similitud de Jaccard corrige ese sesgo normalizando por el tamaño de los vecindarios:

J(a, b) = |vecinos(a) ∩ vecinos(b)| / |vecinos(a) ∪ vecinos(b)|
def recomendaciones(red, u, k=5):
    """Top-k candidatos a amistad para u: no-amigos a distancia 2,
    ordenados por similitud de Jaccard de vecindarios."""
    candidatos = set()
    for amigo in red[u]:
        candidatos |= red[amigo]          # amigos de mis amigos
    candidatos -= red[u] | {u}            # fuera los que ya son amigos, y yo
    puntuados = []
    for c in candidatos:
        inter = len(red[u] & red[c])
        union = len(red[u] | red[c])
        puntuados.append((inter / union, inter, c))
    puntuados.sort(reverse=True)
    return [(c, f"J={j:.2f}", f"{n} en común") for j, n, c in puntuados[:k]]

print(recomendaciones(red, "U-050"))

Es la misma maniobra que hiciste en k-NN (05-01): definir una similitud y rankear por ella. Cambia el espacio (vecindarios de un grafo en lugar de coordenadas numéricas), no el método. En 06-04 reutilizarás exactamente esta idea con matrices usuario-ítem para recomendar productos.

Difusión y viralidad: BFS como modelo de propagación

¿Qué pasa cuando un usuario publica algo y cada contacto lo comparte con cierta probabilidad? El modelo más simple es un BFS probabilístico: la información avanza por niveles (los niveles del BFS son "horas" o "rondas" de propagación), pero cada arista solo la transmite con probabilidad p.

def difusion(red, origen, p=0.3, rondas=6):
    """Simula propagación: cada contacto comparte con probabilidad p."""
    alcanzados = {origen}
    frontera = {origen}
    historia = [1]
    for _ in range(rondas):
        nueva = set()
        for u in frontera:
            for v in red[u]:
                if v not in alcanzados and random.random() < p:
                    nueva.add(v)
        alcanzados |= nueva
        frontera = nueva
        historia.append(len(alcanzados))
        if not frontera:
            break
    return historia

print("Alcance por ronda desde un hub:  ", difusion(red, grados[0][1]))
print("Alcance por ronda desde la periferia:", difusion(red, grados[-1][1]))

Dos fenómenos aparecen al ejecutarlo varias veces: partir de un hub dispara el alcance en las primeras rondas (por eso las campañas buscan nodos de PageRank alto), y existe un umbral: con p pequeño la difusión se apaga sola; superado cierto valor, alcanza a casi toda la componente en pocas rondas — la propiedad de mundo pequeño trabajando a favor (marketing) o en contra (desinformación, virus). Los modelos serios de epidemiología sobre redes (SIR y compañía) son refinamientos de esta misma simulación.

Privacidad: lo que no debes hacer con datos sociales reales

Todo lo anterior lo hicimos sobre usuarios ficticios U-nnn, y no es casualidad. Un grafo social real es dato personal, y de los delicados: revela relaciones, hábitos y círculos de una persona incluso si sus atributos están "anonimizados" (la estructura de conexiones de alguien puede bastar para reidentificarlo). Si algún día analizas redes reales —incluso internas de una empresa, como la red de interacciones entre repartidores y clientes—:

  • Base legal y finalidad primero: en Europa, el RGPD exige un fundamento jurídico y una finalidad declarada antes de tocar el dato; "es que era interesante" no es una finalidad.
  • Agrega y minimiza: para la mayoría de preguntas de negocio (¿cuántas comunidades hay?, ¿cuál es la distancia media?) bastan métricas agregadas; no necesitas —ni debes— mirar individuos.
  • Cuidado con la reidentificación: quitar nombres no anonimiza un grafo; los patrones de conexión son huellas dactilares.
  • Centralidades sobre personas son decisiones sobre personas: usar PageRank interno para evaluar empleados, por ejemplo, entra en el terreno de las decisiones automatizadas con efectos sobre individuos, que requieren transparencia y supervisión humana (lo retomamos en 06-04).

Como norma de trabajo: desarrolla y valida con datos sintéticos (como aquí), y cuando pases a datos reales, hazlo con el marco legal y de gobernanza de datos de tu organización, no por libre.

Errores Comunes y Consejos

  • Elegir mal dirigido/no dirigido. Modelar "seguir" como amistad mutua (o viceversa) invalida todos los análisis posteriores: PageRank sobre un grafo simetrizado degenera casi en el grado. La primera decisión de modelado es la más barata de corregir al principio y la más cara después.
  • Confundir componente con comunidad. Componente es un hecho topológico (hay o no hay camino); comunidad es una cuestión de densidad relativa y siempre depende de un criterio. No existe "la" partición en comunidades verdadera.
  • Olvidar los nodos colgantes en PageRank. Sin el reparto especial, la suma de rangos decae en cada iteración y los resultados dejan de ser comparables. Comprueba siempre que sum(pr.values()) ≈ 1.
  • Recomendar por amigos comunes sin normalizar. Sin Jaccard (u otra normalización), recomendarás hubs a todo el mundo — correcto según la métrica, inútil para el usuario.
  • Sacar conclusiones de una sola simulación de difusión. Es un proceso aleatorio: reporta media y dispersión de muchas ejecuciones, como hiciste con los algoritmos genéticos en 02-04.
  • Consejo: antes de calcular nada sofisticado, imprime lo básico — nº de nodos, aristas, distribución de grados, tamaño de la componente gigante. Cinco líneas que detectan el 90 % de los errores de carga o modelado.

Ejercicios

  1. Robustez de la red. Sobre la red de 300 usuarios, simula dos ataques: (a) eliminar los 10 nodos de mayor grado; (b) eliminar 10 nodos al azar. Tras cada uno, mide con union-find o BFS el tamaño de la componente gigante. ¿Cuál fragmenta más la red? ¿Qué implica para proteger una infraestructura social (o para vacunar en una epidemia)?
  2. PageRank con compra de seguidores. Parte de la red dirigida sigue del ejemplo y añade 20 cuentas nuevas U-9xx que solo siguen a U-007. Recalcula PageRank. ¿Cuánto sube U-007? ¿Sube también U-004 (a quien U-007 sigue)? Explica por qué este "ataque" funciona peor de lo que el atacante espera y qué parámetro lo amortigua.
  3. Recomendador evaluado. Diseña una evaluación del recomendador de amistades: oculta aleatoriamente el 10 % de las aristas de la red, genera top-5 recomendaciones para cada usuario afectado y mide qué fracción de las aristas ocultas aparece recomendada (recall). Compara "amigos en común" contra Jaccard.

Soluciones

  1. El ataque dirigido a hubs es devastador: la componente gigante suele perder una fracción grande de sus nodos o romperse en pedazos, mientras que 10 eliminaciones aleatorias apenas se notan (casi siempre caen nodos de grado 2-3). Es la doble cara de las redes de cola larga: robustas ante fallos aleatorios, frágiles ante ataques dirigidos. En epidemiología, la lectura es que inmunizar hubs (personas de alto contacto) rinde mucho más que inmunizar al azar.
  2. U-007 sube claramente (pasa de rango mínimo a rango notable: 20 cuentas le transfieren su (1−d)/N amplificado), y U-004 también sube — el rango fluye por la arista U-007→U-004 y de ahí a U-003: la inflación se propaga pero diluyéndose en cada salto (factor d y reparto entre salidas). Funciona peor de lo esperado porque las cuentas nuevas solo aportan el rango de teletransporte (nadie las apunta), y el damping d limita cuánto rango "fabricado" puede acumularse. Es, a pequeña escala, la carrera del spam de enlaces contra los buscadores; las defensas reales añaden además detección de patrones anómalos (¡clasificación de 05-02!).
  3. Esquema: ocultas = muestra aleatoria del 10 % de aristas → quítalas de red → para cada usuario con aristas ocultas, genera top-5 → recall = |recomendadas ∩ ocultas| / |ocultas|. Es el equivalente en grafos del train/test que usaste en 05-02: nunca evalúes con información que el modelo pudo ver. Jaccard suele ganar en redes con hubs porque "amigos en común" llena el top-5 con los mismos nodos populares para todo el mundo; si tu red sintética es pequeña y densa, la diferencia puede ser modesta — otra razón para reportar medias sobre varias semillas.

Conclusión

Has analizado una red social de principio a fin sin aprender casi ningún algoritmo nuevo: BFS (03-02) te dio distancias, mundo pequeño, cercanía y el modelo de difusión; union-find (01-04) las componentes; el clustering jerárquico (05-05) y la idea de Girvan-Newman, las comunidades; y la única pieza desarrollada desde cero —PageRank— resultó ser otra iteración de punto fijo de la familia que ya conocías de Bellman-Ford y k-means. La lección de fondo del caso de estudio: en un dominio nuevo, el trabajo es mapear preguntas de negocio a propiedades del grafo, elegir la definición correcta (¿dirigido?, ¿qué centralidad?, ¿qué normalización?) y respetar los límites éticos y legales del dato. En la próxima lección el reto cambia de forma: no es la estructura del problema sino su tamaño — qué pasa con la búsqueda y la ordenación cuando los 200 millones de registros históricos de Rutalia no caben en la memoria de ninguna máquina.

◄ Anterior
◄
Siguiente ►
►
El Proyecto | Sobre nosotros | Contribuir | Donaciones | Licencia
© Copyright 2026. Todos los derechos reservados