¿Por qué construir gráfico de Laplaciano en arracimar espectral?

Question

¿Alguien sabe de dosis está lo crear gráfico de Laplaciano de la matriz de similitud que nos trae en arracimar espectral? o ¿por qué lo creamos? Aquí está el algoritmo: gráfico Laplaciano es: L = D-W. ,D: matriz de grado de gráfico de semejanza, W = matriz de adyacencia ponderada

Answer 1

El conjunto de valores propios de una matriz de adyacencia es el espectro de la gráfica correspondiente. El espectro es un factor muy importante en el estudio de la similitud entre los dos gráficos. Si dos grafos son similares, entonces la matriz de adyacencia de una puede ser visto como una permutación operador implementado en el otro, de forma que sus valores propios son el mismo (tenga en cuenta que dos matrices tienen el mismo autovalores no necesariamente conducen a los dos gráficos son similares).

Así que si hacemos un mapa de cada gráfico nodo a un valor mediante la asignación de una función de $f$ a ellos, los vectores propios de la matriz de adyacencia $A$ puede ser una buena opción (esta es también la razón por vectores propios se calculan en espectral de la agrupación de los procedimientos). Y también puede ser escrita en forma matricial

$$\mathbf{f}^T \mathbf{A} \mathbf{f} = \sum_{e_{ij}} f(i) f(j)$$

Si tenemos en cuenta la incidencia de la matriz en total, el gráfico de asignación de se $f\rightarrow\nabla f$:

$$(\nabla \mathbf{f})(e_{ij}) = f(v_j)-f(v_i)$$

esta mapas en los bordes, y $L = D - A$, es sólo $\nabla ^T \nabla$, se asignarán en el gráfico mediante la asignación de cada nodo de nuevo:

$$(\mathbf{L}\mathbf{f})(v_i) = \sum_{v_j\sim v_i} w_{ij}\big(f(v_i)-f(v_j)\big)$$

Answer 2

Voy a tratar de dar una más accesible (complementarias) de respuesta.

Espectral de la agrupación consta de dos pasos. Primero determinar barrio los bordes entre la función de los vectores (diciéndole que si dos de esos los vectores son similares o no), dando como resultado un gráfico.

Luego de tomar este gráfico y que "embed", o "reorganizar" en un El espacio euclidiano de d dimensiones. Cada dimensión de esta incrustación está tratando de dar una solución a un problema de optimización. De manera informal, este problema de optimización es minimizar el número de los vecinos de nodos del grafo que aparecen en los lados opuestos de 0 (sujeto para un espacio de llenado de restricción). Así, cada nodo tiende a terminar hasta la próxima a sus vecinos (según lo determinado por la estructura de gráfico), lo cual puede ser un más amigable espacio para K-means para trabajar en.

Si usted llevar las matemáticas a través de, resulta que los vectores propios de la Laplace L dar una solución a un "relajado" versión de este problema de optimización - que es.