Algoritmos sobre grafos

Recorridos, rutas más cortas y sensibilidad estructural

En esta sección aprenderemos a recorrer una red, encontrar rutas más cortas y analizar cómo cambia su estructura cuando removemos nodos importantes.

Estos algoritmos nos permiten entender la conectividad y la eficiencia de una red, más allá de sus métricas descriptivas.

---

1 Recorridos: BFS y DFS

Los recorridos son la base de muchos algoritmos.

El BFS (Breadth-First Search) explora por capas (vecinos a nivel 1, luego nivel 2, etc.),
mientras que el DFS (Depth-First Search) avanza en profundidad antes de retroceder.

---

1.1 Ejemplo: red de “amistades”

import networkx as nx

# Grafo simple de ejemplo
G = nx.Graph()
G.add_edges_from([
    ("Ana", "Luis"), ("Ana", "Mia"), ("Luis", "Mia"),
    ("Mia", "Jo"), ("Jo", "Sofi"), ("Jo", "Diego"),
    ("Sofi", "Diego"), ("Kai", "Nora")
])

print(f"Nodos: {G.number_of_nodes()}, Aristas: {G.number_of_edges()}")

---

1.2 Recorrido BFS (por capas)

El BFS se usa para encontrar vecinos por nivel o la distancia mínima en número de saltos desde un nodo inicial.

from collections import deque

def bfs_layers(G, start):
    """Devuelve los nodos visitados por nivel (BFS)."""
    visited = {start}
    queue = deque([(start, 0)])
    levels = {}

    while queue:
        node, depth = queue.popleft()
        levels.setdefault(depth, []).append(node)
        for neigh in G.neighbors(node):
            if neigh not in visited:
                visited.add(neigh)
                queue.append((neigh, depth+1))
    return levels

layers = bfs_layers(G, "Ana")
for nivel, nodos in layers.items():
    print(f"Nivel {nivel}: {nodos}")

Interpretación:

• Nivel 0 → nodo inicial.

• Nivel 1 → vecinos directos.

• Nivel 2 → amigos de los amigos, y así sucesivamente.

Este tipo de recorrido se usa, por ejemplo, para:

• Buscar influencia social por proximidad.

• Definir capas de recomendación (“usuarios similares a tus amigos”).

---

1.3 🌿 Recorrido DFS (en profundidad)

El DFS se usa cuando queremos seguir una rama completa antes de retroceder, por ejemplo, para buscar componentes conexos o detectar ciclos.

def dfs(G, start, visited=None):
    """Recorrido en profundidad (DFS)."""
    if visited is None:
        visited = set()
    visited.add(start)
    for neigh in G.neighbors(start):
        if neigh not in visited:
            dfs(G, neigh, visited)
    return visited

visitados = dfs(G, "Ana")
print("Nodos alcanzados desde Ana:", visitados)

Interpretación:

El DFS profundiza en cada conexión hasta agotar los caminos posibles. Es útil para:

• Encontrar componentes conexos (grupos aislados).

• Detectar ciclos o dependencias en estructuras más complejas.

---

2 Rutas más cortas: Dijkstra

Dijkstra busca la ruta de menor costo o distancia entre dos nodos.

En redes sin pesos, equivale a la ruta más corta en número de aristas; en redes con pesos (por ejemplo, distancias reales), minimiza la suma de los pesos.

---

2.1 ✈ Ejemplo: red de ciudades

import networkx as nx

Gmap = nx.Graph()
Gmap.add_weighted_edges_from([
    ("Bogotá", "Medellín", 415),
    ("Bogotá", "Villavicencio", 120),
    ("Bogotá", "Tunja", 150),
    ("Tunja", "Bucaramanga", 300),
    ("Medellín", "Montería", 400),
    ("Medellín", "Bucaramanga", 380),
    ("Villavicencio", "Yopal", 210),
])

nx.shortest_path(Gmap, source="Bogotá", target="Montería", weight="weight")

Interpretación:

Devuelve la secuencia óptima de ciudades minimizando la distancia total. Puedes también obtener la distancia:

nx.shortest_path_length(Gmap, source="Bogotá", target="Montería", weight="weight")

Aplicaciones:

• Planificación de rutas logísticas.

• Reducción de tiempos de desplazamiento o costos.

• Elección de caminos óptimos en redes de comunicación.

---

3 Subgrafos inducidos por atributo

Podemos extraer partes de una red según una propiedad (por ejemplo, nodos de una misma comunidad, o cafés con rating alto).

# Ejemplo: subgrafo de nodos con nombres que contienen "a"
subset = [n for n in G.nodes if "a" in n.lower()]
G_sub = G.subgraph(subset)
print("Nodos en subgrafo:", G_sub.nodes())

Interpretación:

Esto permite filtrar la red según atributos o condiciones. En análisis reales puede ser:

• Filtrar estudiantes de un mismo programa.

• Seleccionar ciudades de una misma región.

• Aislar cafés con rating superior a 4.5.

---

4 Análisis de sensibilidad: ¿qué pasa si quito un nodo puente?

Algunas redes dependen fuertemente de ciertos nodos para mantenerse conectadas. Cuando se eliminan, pueden aumentar las distancias o incluso fragmentarse.

import numpy as np

def impacto_remocion(G, nodo):
    """Evalúa cambio en componentes y rutas promedio al remover un nodo."""
    comps_antes = list(nx.connected_components(G))
    num_antes = len(comps_antes)
    Gcc = G.subgraph(max(comps_antes, key=len)).copy()
    asp_antes = nx.average_shortest_path_length(Gcc)

    G2 = G.copy()
    G2.remove_node(nodo)
    comps_despues = list(nx.connected_components(G2))
    num_despues = len(comps_despues)
    Gcc2 = G2.subgraph(max(comps_despues, key=len)).copy()
    asp_despues = nx.average_shortest_path_length(Gcc2)

    print(f"🔹 Nodo removido: {nodo}")
    print(f"Componentes: {num_antes} → {num_despues}")
    print(f"ASP (longitud promedio): {asp_antes:.2f} → {asp_despues:.2f}")
    print(f"Diferencia: Δ componentes = {num_despues - num_antes}, Δ ASP = {asp_despues - asp_antes:.2f}")

# Probar con el nodo "Mia" (puente entre dos zonas)
impacto_remocion(G, "Mia")

Interpretación:

• Si aumentan los componentes, el nodo era crítico para mantener conectada la red.

• Si sube el ASP, su ausencia hace las rutas promedio más largas (la red se “estira”).

Este tipo de análisis cuantifica la vulnerabilidad estructural: qué tan dependiente es una red de sus nodos puente.

Estos conceptos permiten estudiar eficiencia y robustez en redes reales, desde infraestructuras y transporte hasta redes sociales o académicas.

---

5 ☕ Rutas, subgrafos y sensibilidad estructural de la red de cafés en Bogotá

Datos generales de la red:

• Nodos: 60
• Aristas: 240
• Tipo de relación: proximidad geográfica (modelo k-vecinos más cercanos, k = 6).
• Cada nodo representa un café en Bogotá, con atributos de nombre y rating.

Ejemplo de nodos:

(0, {'nombre': 'Érase una vez café de especialidad', 'rating': 4.9})
(1, {'nombre': 'Arte y pasión Café: Escuela de baristas', 'rating': 4.7})
(2, {'nombre': 'Agüita Negra Café de especialidad', 'rating': 4.9})

---

5.1 Ruta óptima inicial (Dijkstra)

Se calculó la ruta más corta entre dos cafés estratégicos:

Mundano Coffee Shop → Varietale Javeriana → Diosa Café → Café Amor Perfecto Chapinero Alto
Distancia (radianes): 0.00044 ≈ 2.83 km

Interpretación:

• La ruta cubre aproximadamente 2.8 km, un recorrido razonablemente corto dentro de la zona Chapinero-Centro.

• Los nodos Varietale Javeriana y Diosa Café actúan como puentes intermedios: conectan microzonas dentro del cluster norte-centro.

• En términos de estructura, estos cafés acortan rutas entre sectores y son candidatos a nodos de intermediación.

---

5.2 Subgrafo inducido por atributo

Se extrajo la subred formada únicamente por cafés con rating ≥ 4.5.

Nodos: 54
Aristas: 195

Interpretación:

• La mayoría de los cafés mantienen calificaciones altas, lo que genera una red densa incluso tras filtrar.

• La subred conserva la conectividad principal: 54 de 60 nodos y 195 de 240 enlaces, mostrando que los cafés mejor valorados están bien distribuidos y no conforman un grupo aislado.

• Esto sugiere homogeneidad en la calidad percibida, sin segregación marcada por rating.

---

5.3 Análisis de sensibilidad — impacto de remover nodos clave

Se evaluó la robustez estructural al eliminar cafés detectados previamente como posibles brokers.

Café removido	Componentes antes→después	ASP antes→después	Δ Componentes	Δ ASP	Interpretación
Mundano Coffee Shop	1 → 2	5.301 → 3.599	+1	−1.702	Crítico: su eliminación fragmenta la red. Mantiene la conectividad entre zonas norte y central; su ausencia divide la red principal.
Diosa Café	1 → 1	5.301 → 5.365	0	+0.064	Redundante: no rompe la red, pero alarga rutas mínimas. Aporta eficiencia local, pero hay caminos alternativos.
Café Amor Perfecto Chapinero Alto	1 → 1	5.301 → 5.364	0	+0.063	Redundante: similar al anterior, con efecto leve. Su rol es local; su pérdida no afecta la conectividad global.

---

5.3.1 Interpretación global

1. Ruta óptima inicial (≈ 2.83 km) atraviesa cafés con alta intermediación; su estructura es eficiente.

2. Subgrafo por rating conserva la conectividad → los cafés mejor valorados forman una red fuerte y continua.

3. Sensibilidad:

   • Mundano Coffee Shop es crítico: su remoción genera fragmentación (1→2 componentes).
   • Diosa Café y Amor Perfecto son redundantes: su eliminación no rompe la red, solo incrementa levemente las distancias.
   • El aumento de ASP (+0.06) es bajo, evidenciando resiliencia estructural.

La red de cafés presenta buena robustez: la mayoría de los nodos de alta centralidad no son únicos ni insustituibles. Sin embargo, la existencia de un nodo crítico (Mundano Coffee Shop) sugiere que la conectividad urbana depende de pocos puntos estratégicos que enlazan subzonas. Desde la perspectiva de análisis de redes:

• La estructura muestra redundancia controlada (alta tolerancia a fallos locales).

• El estudio de rutas cortas y remoción ayuda a identificar vulnerabilidades urbanas y zonas con mejor cobertura.

# =====================================================
# ☕ Algoritmos sobre la red de cafés en Bogotá
# =====================================================

import networkx as nx
import pandas as pd
import numpy as np
from sklearn.neighbors import NearestNeighbors

# -----------------------------------------
# 1️⃣ Cargar los datos y construir el grafo
# -----------------------------------------
df = pd.read_csv("cafes_bogota.csv")

coords = np.radians(df[["lat", "lon"]].dropna().to_numpy())
k = 6  # número de vecinos cercanos

nbrs = NearestNeighbors(n_neighbors=k+1, metric="haversine").fit(coords)
dist, idx = nbrs.kneighbors(coords)

G_cafe = nx.Graph()
for i, row in df.dropna(subset=["lat","lon"]).reset_index(drop=True).iterrows():
    G_cafe.add_node(i, nombre=row["nombre"], rating=row["rating"])

for i in range(len(coords)):
    for jpos in idx[i,1:]:
        j = int(jpos)
        if i != j:
            G_cafe.add_edge(i, j, weight=dist[i, np.where(idx[i]==jpos)[0][0]])

print(f"Nodos: {G_cafe.number_of_nodes()}, Aristas: {G_cafe.number_of_edges()}")
print("Ejemplo de nodos:", list(G_cafe.nodes(data=True))[:3])

# --------------------------------------------------
# 2️⃣ Ruta más corta (Dijkstra) entre dos cafeterías
# --------------------------------------------------
def ruta_mas_corta(nombre1, nombre2):
    name_to_id = {G_cafe.nodes[i]["nombre"]: i for i in G_cafe.nodes()}
    if nombre1 not in name_to_id or nombre2 not in name_to_id:
        print("⚠️ Alguno de los nombres no existe en el grafo.")
        return
    src, tgt = name_to_id[nombre1], name_to_id[nombre2]
    ruta = nx.shortest_path(G_cafe, source=src, target=tgt, weight="weight")
    distancia = nx.shortest_path_length(G_cafe, source=src, target=tgt, weight="weight")
    print(f"Ruta más corta entre '{nombre1}' y '{nombre2}':")
    print(" → ".join(G_cafe.nodes[i]["nombre"] for i in ruta))
    print(f"Distancia (radianes): {distancia:.5f} ≈ {distancia*6371:.2f} km")

# Ejemplo
ruta_mas_corta("Mundano Coffee Shop", "Café Amor Perfecto Chapinero Alto")

# -------------------------------------------------------
# 3️⃣ Subgrafo inducido: cafés con rating >= 4.5
# -------------------------------------------------------
subset = [i for i in G_cafe.nodes() if G_cafe.nodes[i]["rating"] >= 4.5]
G_sub = G_cafe.subgraph(subset)
print(f"\nSubgrafo de cafés con rating ≥ 4.5:")
print(f"Nodos: {G_sub.number_of_nodes()}, Aristas: {G_sub.number_of_edges()}")

# -------------------------------------------------------
# 4️⃣ Análisis de sensibilidad: impacto de remoción
# -------------------------------------------------------
def impacto_remocion(G, nombre_cafe):
    name_to_id = {G.nodes[i]["nombre"]: i for i in G.nodes()}
    if nombre_cafe not in name_to_id:
        print("⚠️ El café no existe en la red.")
        return
    nodo = name_to_id[nombre_cafe]

    comps_antes = list(nx.connected_components(G))
    num_antes = len(comps_antes)
    Gcc = G.subgraph(max(comps_antes, key=len)).copy()
    asp_antes = nx.average_shortest_path_length(Gcc)

    G2 = G.copy()
    G2.remove_node(nodo)
    comps_despues = list(nx.connected_components(G2))
    num_despues = len(comps_despues)
    Gcc2 = G2.subgraph(max(comps_despues, key=len)).copy()
    asp_despues = nx.average_shortest_path_length(Gcc2)

    print(f"\n🔹 Café removido: {nombre_cafe}")
    print(f"Componentes: {num_antes} → {num_despues}")
    print(f"ASP (camino promedio): {asp_antes:.3f} → {asp_despues:.3f}")
    print(f"Δ Componentes = {num_despues - num_antes}, Δ ASP = {asp_despues - asp_antes:.3f}")

# Ejemplos con los “brokers” detectados
impacto_remocion(G_cafe, "Mundano Coffee Shop")
impacto_remocion(G_cafe, "Diosa Café")
impacto_remocion(G_cafe, "Café Amor Perfecto Chapinero Alto")

6 Código completo

# =====================================================
# 🌐 Algoritmos sobre grafos: BFS, DFS, Dijkstra y sensibilidad
# =====================================================

import networkx as nx
import numpy as np
from collections import deque

# -----------------------------------------------------
# 1️⃣ Grafo de ejemplo (amistades)
# -----------------------------------------------------
G = nx.Graph()
G.add_edges_from([
    ("Ana", "Luis"), ("Ana", "Mia"), ("Luis", "Mia"),
    ("Mia", "Jo"), ("Jo", "Sofi"), ("Jo", "Diego"),
    ("Sofi", "Diego"), ("Kai", "Nora")
])
print(f"Nodos: {G.number_of_nodes()}, Aristas: {G.number_of_edges()}")

# -----------------------------------------------------
# 2️⃣ BFS (Breadth-First Search) - vecinos por nivel
# -----------------------------------------------------
def bfs_layers(G, start):
    visited = {start}
    queue = deque([(start, 0)])
    levels = {}
    while queue:
        node, depth = queue.popleft()
        levels.setdefault(depth, []).append(node)
        for neigh in G.neighbors(node):
            if neigh not in visited:
                visited.add(neigh)
                queue.append((neigh, depth+1))
    return levels

print("\n=== BFS desde Ana ===")
layers = bfs_layers(G, "Ana")
for nivel, nodos in layers.items():
    print(f"Nivel {nivel}: {nodos}")

# -----------------------------------------------------
# 3️⃣ DFS (Depth-First Search)
# -----------------------------------------------------
def dfs(G, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for neigh in G.neighbors(start):
        if neigh not in visited:
            dfs(G, neigh, visited)
    return visited

print("\n=== DFS desde Ana ===")
visitados = dfs(G, "Ana")
print("Nodos alcanzados:", visitados)

# -----------------------------------------------------
# 4️⃣ Rutas más cortas (Dijkstra)
# -----------------------------------------------------
Gmap = nx.Graph()
Gmap.add_weighted_edges_from([
    ("Bogotá", "Medellín", 415),
    ("Bogotá", "Villavicencio", 120),
    ("Bogotá", "Tunja", 150),
    ("Tunja", "Bucaramanga", 300),
    ("Medellín", "Montería", 400),
    ("Medellín", "Bucaramanga", 380),
    ("Villavicencio", "Yopal", 210),
])

path = nx.shortest_path(Gmap, source="Bogotá", target="Montería", weight="weight")
dist = nx.shortest_path_length(Gmap, source="Bogotá", target="Montería", weight="weight")
print("\n=== Ruta más corta (Dijkstra) ===")
print("Ruta:", " → ".join(path))
print("Distancia total (km):", dist)

# -----------------------------------------------------
# 5️⃣ Subgrafos inducidos por atributo (ejemplo simple)
# -----------------------------------------------------
subset = [n for n in G.nodes if "a" in n.lower()]
G_sub = G.subgraph(subset)
print("\n=== Subgrafo con nodos que contienen 'a' ===")
print("Nodos:", list(G_sub.nodes()))

# -----------------------------------------------------
# 6️⃣ Análisis de sensibilidad: impacto de remover un nodo puente
# -----------------------------------------------------
def impacto_remocion(G, nodo):
    """Evalúa cambio en componentes y rutas promedio al remover un nodo."""
    comps_antes = list(nx.connected_components(G))
    num_antes = len(comps_antes)
    Gcc = G.subgraph(max(comps_antes, key=len)).copy()
    asp_antes = nx.average_shortest_path_length(Gcc)

    G2 = G.copy()
    G2.remove_node(nodo)
    comps_despues = list(nx.connected_components(G2))
    num_despues = len(comps_despues)
    Gcc2 = G2.subgraph(max(comps_despues, key=len)).copy()
    asp_despues = nx.average_shortest_path_length(Gcc2)

    print(f"\n🔹 Nodo removido: {nodo}")
    print(f"Componentes: {num_antes} → {num_despues}")
    print(f"ASP (longitud promedio): {asp_antes:.2f} → {asp_despues:.2f}")
    print(f"Diferencia: Δ componentes = {num_despues - num_antes}, Δ ASP = {asp_despues - asp_antes:.2f}")

# Probar con el nodo “Mia” (puente entre zonas)
impacto_remocion(G, "Mia")