Inicio · Parte 17 — Frontera matemática para IA e investigación

354 — Spectral graph theory

frontera-investigacion clase 14 de 20 4 horas demostración spectral_graph_theory

El signo del vector de Fiedler dice por dónde partir el grafo en dos.

Fórmulas

L = D − A;  autovalores 0 = λ₁ ≤ λ₂ ≤ …
λ₂ = conectividad algebraica
partición por el signo del autovector de λ₂

Desarrollo

El agrupamiento espectral resuelve un problema difícil mediante una relajación continua. Partir un grafo minimizando el número de aristas cortadas es un problema combinatorio NP-difícil; relajarlo a variables continuas lo convierte en un problema de autovectores, que se resuelve en tiempo polinómico.

El autovector asociado al segundo autovalor —el vector de Fiedler— es la solución de esa relajación, y el signo de cada componente indica a qué lado del corte asignar cada nodo. En el ejemplo, cuatro nodos tienen componente negativa y cuatro positiva, y esa partición corresponde exactamente a la estructura de comunidades del grafo.

La conectividad algebraica λ₂ cuantifica cuán bien separado está el grafo. Un valor pequeño —0,29 en el ejemplo, frente a autovalores posteriores de 2 y 4— indica que existe un corte barato y que la partición es significativa. Si λ₂ fuera comparable a los demás, el corte sería arbitrario.

El método se generaliza a más de dos grupos usando los primeros k autovectores como coordenadas y aplicando k-means en ese espacio. Su ventaja sobre k-means directo es que funciona con grupos no convexos, que es justamente donde k-means falla. Su límite es el coste: calcular autovectores de un grafo enorme requiere métodos iterativos como los de la parte 11.

Ejemplo trabajado

Grafo de 8 nodos partido por el vector de Fiedler.

8 nodos, 11 aristas

autovalores del Laplaciano:
  [0,0 ; 0,29072464 ; 2,0 ; 2,80606343 ; 4,0 ; 4,0 ; 4,0 ; 4,90321193]

multiplicidad de 0: 1  →  grafo conexo             ✓
conectividad algebraica: 0,29072464

vector de Fiedler:
  [−0,432487 ; −0,369619 ; −0,369619 ; −0,199295 ;
    0,199295 ;  0,369619 ;  0,369619 ;  0,432487]

partición por signo:
  grupo A: nodos 0, 1, 2, 3
  grupo B: nodos 4, 5, 6, 7

λ₂ = 0,29 frente a λ₃ = 2,0: el corte es claro.

Qué calcula el laboratorio

Clustering espectral: el vector de Fiedler separa el grafo.

python classes/part-17-frontera-matematica-para-ia-e-investigacion/354-spectral-graph-theory/lab.py
compmath run 354

Salidas del laboratorio (11)

nodos
aristas
autovalores_ordenados
conectividad_algebraica
grafo_conexo
vector_de_Fiedler
particion
aristas_cortadas
corte_minimo_esperado
particion_correcta
cota_de_Cheeger

Muestra de la ejecución real

{
  "nodos": 8,
  "aristas": 11,
  "autovalores_ordenados": [
    0.0,
    0.29072464,
    2.0,
    2.80606343,
    4.0,
    4.0,
    4.0,
    4.90321193
  ],
  "conectividad_algebraica": 0.29072464,
  "grafo_conexo": true,
  "vector_de_Fiedler": [
    -0.432487,
    -0.369619,
    -0.369619,
    -0.199295,
    0.199295,
    0.369619,
    0.369619,
    0.432487
  ]
}

Errores comunes

Aplicar el método a grafos no conexos sin tratar cada componente por separado.
Interpretar la partición cuando λ₂ es comparable a los autovalores siguientes.
Calcular todos los autovectores cuando solo hacen falta los primeros.

Dónde se usa

Detección de comunidades, segmentación de imágenes, partición de mallas, análisis de redes sociales y agrupamiento de datos no convexos.

Idea rectora de la parte

La geometría de la información dota al espacio de parámetros de una métrica natural.

Error a evitar

Invertir una matriz de covarianza sin jitter numérico.

Conexión con IA

Score matching fundamenta los modelos de difusión; el transporte óptimo aparece en flow matching; la teoría estadística del aprendizaje explica el scaling.

Bibliografía de la clase

von Luxburg, U. A tutorial on spectral clustering, Statistics and Computing, 2007 — Álgebra lineal y Grafos y redes: el tema de esta clase · DOI 10.48550/arxiv.0711.0189 verificado en DataCite (2026-08-19).
Shi, J.; Malik, J. Normalized cuts and image segmentation, IEEE TPAMI, 2000 — Grafos y redes: el tema de esta clase · DOI 10.1109/34.868688 verificado en Crossref (2026-08-19).

Archivos de la clase

← 353 Score matching 355 Causal inference →