A continuación muestro una síntesis del articulo Graph Clustering de Satu Elisa Schaeffer
Al inicio del artículo se definen conceptos básicos necesarios para el entendimiento del articulo como los son complejidad computacional, algoritmos de aproximación, teoría de grafos y cadenas de Markov.
Definición de tareas de clustering de grafos discutiendo diferentes definiciones de clusterings y clusters
La partición de grafos significa minimizar la cantidad de bordes que cruzan de un grupo de vértices a otro.
No hay una definición única de clúster en un grafo. Al crear un grafo cada clúster debe de estar conectado de manera intuitiva: esto significa que debe de haber por lo menos uno, preferentemente varios caminos conectando cada para de vértices en un clúster. Si un vértice 'x' no puede ser alcanzado por un vértice 'y' no deben de estar agrupados en un mismo clúster. Además cada camino debe de ser interno al clúster: además del conjunto de vértices C que es conectada en G, la sub grafo inducido por C se debe conectar en sí mismo, es decir, que no es suficiente para dos vértices v y u en C para ser
conectados por un camino que pasa por los vértices de V \ C, sino también necesitan estar conectados por un camino que sólo visite vértices incluidos en C.
Como consecuencia, cuando el clustering de un gráfico desconectado con componentes conocidos, la agrupación por lo general debe ser conectado a cada componente por separado, a menos que se imponga una restricción global.
Definición de mediciones de similaridad
Hay dos enfoques principales para la identificación de un clúster:
Calculando algunos valores de los vértices y clasificar los vértices en grupos sobre la base de los valores obtenidos, o calcular una medida de la aptitud en el conjunto de posibles clúster y luego elegir entre el conjunto de clúster candidatos que optimizan la medida utilizada
Algoritmos globales de clustering
En un clustering global cada vértice del grafo de entrada es asignado a un clúster en el método de salida, tal como en un clúster local, las asignaciones en el clúster realizadas desde un cierto subgrupo de vértices, comúnmente un solo vértice.
Métodos locales
El clustering local se refiere a guardar el grafo en formato que permite acceder a los sub grafos conectados o a listas de adyacencia de vértices cercanos, lo que permite calcular los clúster uno a la vez basado en vistas parciales de la topología del grafo. Esto permite realizar cálculos imposibles a colecciones muy grandes de datos.
Algunas aplicaciones de clustering de grafos son las siguientes:
<!--[if !supportLists]-->• <!--[endif]-->Identificar estructuras relevantes y analizar la conectividad para el modelamiento u optimización estructural.
<!--[if !supportLists]-->• <!--[endif]-->Optimización de software como los servicios de chat
<!--[if !supportLists]-->• <!--[endif]-->Diseño estructural de redes de sensores
<!--[if !supportLists]-->• <!--[endif]-->Agrupar información en bases de datos de manera óptima