En este artículo la Dra. Elisa Scheaffer presenta un estudio realizado sobre el agrupamiento de grafos.
El proceso de identificar la heterogeneidad de los datos no uniformes se le llama agrupamiento clasificación de datos. Los grafos son estructuras formadas por un conjunto de vértices (o nodos) y aristas que conectan un par de nodos.
El agrupamiento de grafos es una tarea de agrupar vértices de la gráfica en grupos de tal manera que queden pocos vértices fuera de los grupos.
El estudio consta de 10 secciones, en donde se abordan desde las definiciones básicas y necesarias para comprender el agrupamiento de grafos, hasta los problemas que quedan inconclusos, las direcciones futuras y las conclusiones sobre este tema.
En la sección 2 de este estudio, se otorgan los términos y definiciones que facilitan el entendimiento del resto del estudio. En esta se proveen términos de complejidad computacional, algoritmos de aproximación, teoría de grafos y cadenas de Markov.
En la sección 3, se comienza con la tarea de definir lo que constituye una agrupación en un grafo y lo que una agrupación debería ser. También se discuten algunas clases especiales de gráficos. En esta sección también se menciona cual es el objetivo de la agrupación, una vez dado un conjunto de datos, este consiste en dividir el conjunto de datos en grupos de tal manera que los elementos asignados a un grupo determinado son similares o conectados en sentido predefinido.
En esta sección se abordan temas de modelos de generación para los grafos agrupados, propiedades deseables del grupo y las representaciones de los grupos para las diferentes clases de grafos, como lo son los grafos bipartitas y los grafos directos.
En la sección 4 se aborda el tema de las mediciones para identificar grupos, en donde primeramente se hace una visión de las medidas de similitud de vértices que pueden ser utilizadas de former manner para identificar el conjunto de un vértice específico o para agrupar todos los vértices en un conjunto de grupos, y luego presentar las posibles cluster fitness measures que sirven para métodos que producen la agrupación mediante la comparación de diferentes grupos y seleccionando uno que cumpla u optimice un criterio determinado.
En la sección 5 se ve el tema de los métodos globales para agrupamiento de grafos, en donde se ve la complejidad del agrupamiento global, cálculo iterativo o en línea de los agrupamientos globales, agrupamiento jerárquico, agrupamiento de división global y agrupamiento aglomerativo global.
En la sección 6 se ven los métodos locales para el agrupamiento en grafos, los cuales son utilizados para encontrar un buen grupo que contiene un vértice especificado o un conjunto de vértices mediante el examen de un número limitado de vértices a la vez, los cuales están en la "vecindad" del vértice especificado.
En la sección 7 se describe la dificultad de comparar, evaluar y realizar el benchmarking de los métodos de agrupamiento de grafos.
En la sección 8 se presentan las aplicaciones del agrupamiento de grafos, aplicaciones en agrupamiento de datos, en redes de información y uso de la información, en sistemas de bases de datos, en redes sociológicas y biológicas, entre otras.
En la Sección 9 se revisan los problemas abiertos y las direcciones futuras, y en la Sección 10 se llega a la conclusión del estudio.
