Un operador lineal sobre funciones definidas en los vértices de un grafo, típicamente dado por L = D − A donde D es la matriz diagonal de grados y A la matriz de adyacencia; codifica difusión discreta y suavidad local en el grafo.

Principio

Al actuar sobre una función en los vértices, el laplaciano calcula el flujo neto (diferencia entre el valor en un vértice y el promedio de sus vecinos) y su descomposición espectral organiza modos de variación, conectividad y velocidades de difusión.

Demostración

Para un grafo no dirigido ponderado, (Lf)(i)=∑_j w_{ij}(f(i)−f(j)); la multiplicidad del valor propio cero coincide con el número de componentes conexas y el segundo menor valor propio (conectividad algebraica) cuantifica los cuellos de botella.

Aplicación incorrecta

Usar el laplaciano no normalizado sin compensar la heterogeneidad de grados cuando se comparan grafos con grados de vértice muy dispares; esto puede distorsionar el clustering espectral y la interpretación de la difusión.

Consecuencia

Los valores y vectores propios del laplaciano aportan información sobre conectividad, tiempos de mezcla de paseos aleatorios, y pueden emplearse para reducción de dimensionalidad, suavizado y particionado de grafos.

Inversión

Contrastar con la matriz de adyacencia, que registra conexiones por pares sin ponderar diferencias; el espectro de adyacencia enfatiza patrones de conexión directa en lugar de modos suaves.

Límite

El laplaciano combinatorio estándar se define para grafos finitos no dirigidos con pesos no negativos; grafos dirigidos, pesos con signo o grafos infinitos requieren definiciones modificadas (laplaciano normalizado, laplaciano de paseo aleatorio u operadores en ℓ^2).

Tensión semántica

Tensión con la curvatura discreta o operadores basados en resistencia: el laplaciano mide diferencia local y difusión, mientras que la distancia de resistencia enfatiza la resistencia efectiva global y puede producir señales espectrales distintas.

Síntesis

El laplaciano de grafo L = D−A es el operador discreto de segunda diferencia sobre funciones de vértices; su acción codifica la desviación local respecto a la media de vecinos y su espectro organiza conectividad, difusión y suavidad en el grafo.