Un enfoque de agrupamiento espectral para encontrar comunidades en grafos

Agrupar nodos en un grafo es una técnica general útil en la minería de datos de grandes conjuntos de datos de redes. En este contexto, Newman y Girvan 9 han propuesto recientemente una función objetiva para el agrupamiento de grafos llamada función Q, que permite la selección automática del número de clústeres. Empíricamente, se ha demostrado que valores más altos de la función Q correlacionan bien con buenos agrupamientos de grafos. En este documento mostramos cómo optimizar la función Q se puede reformular como un problema de relajación espectral y proponemos dos nuevos algoritmos de agrupamiento espectral que buscan maximizar Q. Los resultados experimentales indican que los nuevos algoritmos son eficientes y efectivos para encontrar tanto buenos agrupamientos como el número adecuado de clústeres en una variedad de conjuntos de datos de grafos del mundo real. Además, los algoritmos espectrales son mucho más rápidos para grafos dispersos grandes, escalando de manera aproximadamente lineal con el número de nodos n en el grafo, en comparación con O(n2) para los algoritmos de agrupamiento anteriores que utilizan la función Q.