1. Introducción

Los grafos son estructuras fundamentales en ciencias de la computación, análisis de redes sociales, bioinformática y optimización de rutas. Cuando se representan mediante matrices de adyacencia, el álgebra lineal se convierte en la herramienta perfecta para diseñar algoritmos eficientes.

En este artículo combinaremos:

• Representación matricial de grafos con NumPy.
• Algoritmos clásicos (BFS, Dijkstra, PageRank) usando operaciones vectoriales.
• Visualización interactiva con Matplotlib (2D y 3D) y comparativas con Plotly y NetworkX.

2. Prerrequisitos

Instala las dependencias con pip:

pip install numpy matplotlib networkx scipy plotly

Se asume conocimiento básico de Python y de conceptos de grafos (nodos, aristas, ponderación).

3. Fundamentos de Álgebra Lineal para Grafos

Una matriz de adyacencia A ∈ ℝⁿˣⁿ codifica todas las conexiones del grafo:

• A[i, j] = w si existe una arista de i a j con peso w.
• Para grafos no dirigidos, A es simétrica.

Operaciones útiles:

• Multiplicación de matrices (A @ x) → propaga información a vecinos.
• Potencias de A (A**k) → número de caminos de longitud k.
• Descomposición espectral (eig) → bases para PageRank y clustering.

Ejemplo de creación de una matriz de adyacencia:

import numpy as np
# Grafo dirigido con 5 nodos
A = np.array([
    [0, 2, 0, 0, 1],
    [0, 0, 3, 0, 0],
    [4, 0, 0, 5, 0],
    [0, 0, 0, 0, 2],
    [0, 1, 0, 0, 0]
], dtype=float)
print(A)

4. Visualización básica con Matplotlib

Matplotlib no está especializado en grafos, pero combinándolo con NetworkX podemos obtener diagramas claros.

import matplotlib.pyplot as plt
import networkx as nx
G = nx.from_numpy_array(A, create_using=nx.DiGraph)
pos = nx.spring_layout(G, seed=42)  # layout determinista
plt.figure(figsize=(8,6))
nx.draw_networkx_nodes(G, pos, node_color='steelblue', node_size=500)
nx.draw_networkx_edges(G, pos, arrowstyle='->', arrowsize=15, edge_color='gray')
nx.draw_networkx_labels(G, pos, font_color='white')
plt.title('Grafo dirigido representado con Matplotlib')
plt.axis('off')
plt.tight_layout()
plt.show()

Resultado: un diagrama limpio con nodos numerados y flechas que indican la dirección y peso de cada arista.

5. Algoritmos clásicos usando álgebra lineal

def bfs_matrix(A, source):
    n = A.shape[0]
    visited = np.zeros(n, dtype=bool)
    frontier = np.zeros(n, dtype=bool)
    frontier[source] = True
    order = []
    while frontier.any():
        visited |= frontier
        order.append(np.where(frontier)[0].tolist())
        # Propagar a vecinos no visitados
        frontier = (A @ frontier) > 0
        frontier &= ~visited
    return order
print('Orden BFS:', bfs_matrix(A, 0))

from scipy.sparse import csr_matrix
from heapq import heappush, heappop
def dijkstra_sparse(A, src):
    n = A.shape[0]
    dist = np.full(n, np.inf)
    dist[src] = 0
    visited = np.zeros(n, dtype=bool)
    pq = [(0, src)]
    while pq:
        d, u = heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        neighbors = A[u].nonzero()[1]
        for v in neighbors:
            w = A[u, v]
            if d + w < dist[v]:
                dist[v] = d + w
                heappush(pq, (dist[v], v))
    return dist
A_sparse = csr_matrix(A)
print('Distancias desde 0:', dijkstra_sparse(A_sparse, 0))

5.3. PageRank mediante descomposición espectral

PageRank es esencialmente el autovector dominante de la matriz de transición estocástica.

def pagerank(A, alpha=0.85, eps=1e-8, max_iter=100):
    n = A.shape[0]
    # Normalizar filas para obtener probabilidad de transición
    row_sum = A.sum(axis=1, keepdims=True)
    P = np.divide(A, row_sum, where=row_sum!=0)
    # Matriz de Google
    G = alpha * P + (1 - alpha) / n * np.ones((n, n))
    r = np.ones(n) / n
    for _ in range(max_iter):
        r_new = G.T @ r
        if np.linalg.norm(r_new - r, 1) < eps:
            break
        r = r_new
    return r / r.sum()
pr = pagerank(A)
print('PageRank:', np.round(pr, 4))

6. Visualizaciones avanzadas

from mpl_toolkits.mplot3d import Axes3D
fig = plt.figure(figsize=(9,7))
ax = fig.add_subplot(111, projection='3d')
pos3d = nx.spring_layout(G, dim=3, seed=42)
for i, (x,y,z) in enumerate(pos3d.values()):
    ax.scatter(x, y, z, s=200, c='steelblue')
    ax.text(x, y, z, str(i), color='white')
for u,v in G.edges():
    x = [pos3d[u][0], pos3d[v][0]]
    y = [pos3d[u][1], pos3d[v][1]]
    z = [pos3d[u][2], pos3d[v][2]]
    ax.plot(x, y, z, c='gray')
ax.set_title('Representación 3D del grafo')
plt.show()

import plotly.express as px
import pandas as pd
df = pd.DataFrame(A, index=range(A.shape[0]), columns=range(A.shape[1]))
fig = px.imshow(df, text_auto=True, color_continuous_scale='Viridis')
fig.update_layout(title='Matriz de adyacencia (Heatmap)')
fig.show()

7. Comparativa rápida: Matplotlib vs Plotly vs NetworkX

8. Buenas prácticas, rendimiento y seguridad

8.1. Uso de matrices dispersas

Para grafos con millones de nodos, scipy.sparse.csr_matrix reduce el consumo de memoria en >90 % y acelera multiplicaciones.

8.2. Vectorización vs bucles Python

Siempre que sea posible, reemplaza bucles for por operaciones numpy o scipy.sparse. Ejemplo:

# Bucle lento
for i in range(n):
    out[i] = np.dot(A[i], x)
# Vectorizado
out = A @ x

8.3. Seguridad en entornos multi‑usuario

Si el servicio de visualización se expone vía web (p. ej., Dash), valida siempre los datos de entrada para evitar inyección de código. Usa jsonschema o pydantic para sanitizar.

8.4. Profiling y benchmarking

Utiliza cProfile o line_profiler para identificar cuellos de botella. En grafos grandes, el mayor gasto suele estar en la generación de la matriz de adyacencia.

import cProfile, pstats
cProfile.run('pagerank(A)', 'pr_profile')
stats = pstats.Stats('pr_profile')
stats.sort_stats('cumtime').print_stats(10)

9. Troubleshooting común

• Grafos desconectados: PageRank converge a valores idénticos; añada un "teleport" con alpha para evitar cuellos de botella.
• Division by zero en normalización: Use where=row_sum!=0 en np.divide como se mostró.
• Renderizado lento en Matplotlib: Reduzca node_size, desactive edge_labels y use fig.canvas.draw_idle() en notebooks.
• Memoria agotada con matrices densas: Cambie a csr_matrix y use operaciones @ sobre objetos dispersos.

10. Conclusión

Combinar álgebra lineal y Matplotlib permite implementar algoritmos de grafos de forma concisa, escalar a miles de nodos con matrices dispersas y generar visualizaciones que facilitan el análisis y la presentación.

Explora también GraphFrames en Spark o Neo4j para casos de uso a gran escala, pero la base que hemos cubierto sigue siendo la piedra angular para prototipos y entornos académicos.