Ok, nos permite construir adyacencia matriz W para ese gráfico siguiendo el procedimiento simple: si tanto de vértices adyacentes i-ésimo y j-ésimo son del mismo color entonces el peso del borde entre ellas W_ {i, j} es un gran número (que sintonizarás en tus experimentos más adelante) y de lo contrario es un pequeño número que descubrirás de forma análoga.
Ahora, escribamos laplaciano de la matriz como L = D - W, donde D es una matriz diagonal con los elementos d_ {i, i} igual a la suma de la W i-ésima fila.
Ahora, uno puede demostrar fácilmente que el valor de fLf^T, donde f es un vector arbitrario, es pequeño si los vértices con grandes pesos de ajuste tienen valores f cercanos. Puede pensar en ello como en la forma de establecer un sistema de coordenadas para el gráfico con i-el vértice tiene una coordenada f_i en el espacio 1D.
Ahora, elijamos algunos de esos vectores f^k que nos dan representación del gráfico como un conjunto de puntos en algún espacio euclidiano en el que, por ejemplo, k-means funciona: ahora tiene i-th vertex del gráfico inicial que tiene coordenadas f^1_i, f^2_i, ... y también los vectores adyacentes del mismo color en el gráfico inicial se cerrarán en este nuevo espacio de coordenadas.
La pregunta sobre cómo elegir vectores f es simple: solo tome un par de vectores propios de la matriz L como f que corresponden a valores propios pequeños pero no nulos.
Este es un método conocido llamado clúster espectral.
Más información: Los elementos del aprendizaje estadístico: Los datos Minería, Inferencia y predicción. por Trevor Hastie, Robert Tibshirani y Jerome Friedman
que está disponible de forma gratuita desde la página autores http://www-stat.stanford.edu/~tibs/ElemStatLearn/
¿No es lo que se implementa en scikit-learn SpectralClustering? –
@Juh_ probablemente, no sabía nada de scikit-learn en el momento de escribir. – Moonwalker