Graph clustering (Agrupamiento de los grafos)

A continuación se hace una recopilación de los aspectos más importantes del artículo de investigación Graph Clustering (Agrupación de los gráfos) por la Doctora Satu Elisa Scheaffer.

Abstracto

En este estudio se resumen las definiciones y métodos para la agrupación de los grafos, esto es, encontrar un conjunto de vértices relacionados en grafos. También en este artículo se revisan las diferentes definiciones y se describe que son los agrupamientos en un grafo y la medición de la cantidad de agrupaciones.
La idea es presentar los algoritmos globales para producir un agrupamiento para el completo conjunto de vértices de una entrada de un grafo, después se discuten las tareas de identificar un agrupamiento para un específico vértice para una computación local. Algunas ideas sobre las áreas de aplicación de agrupamiento de algoritmos de grafos están dadas.

También se discute la problemática de evaluar el agrupamiento y se hace una evaluación comparativa sobre el agrupamiento de algoritmos.
Además se habla en este artículo sobre la terminología para facilitar la discusión, como son la complejidad computacional, la aproximación de los algoritmos, la teoría de grafos, las cadenas de Markov.

Introducción

Los datos no uniformes carecen de estructura debido a la heterogeneidad de los datos. El proceso para identificar esta estructura en términos de agrupar los datos elementales es llamado clustering (agrupamiento), y es también llamado clasificación de los datos (data classification). El resultado de agrupar es llamado clusters. El agrupamiento es usualmente basado sobre similitudes de mediciones definidas para los elementos de los datos. El agrupamiento de los datos esta estrechamente relacionado en aprendizaje no relacionado en reconocimiento de patrones. Una tarea básica sobre el aprendizaje no supervisado para la clasificación del conjunto de los datos dentro de dos o más clases basadas sobre lo similar de las medidas en los datos.

Los grafos son estructuras formadas por un conjunto de vértices (también llamados nodos) y un conjunto de lados que son conexiones entre pares de vértices. El agrupamiento de los grafos es una tarea de agrupar los vértices de los grafos dentro en agrupaciones dadas, considerando la estructura de los lados dentro de cada agrupamiento.

Como el campo del agrupamiento de los datos a aumentado y se ha hecho bastante popular y el número de publicaciones propuestas para el agrupamiento de algoritmos así como, el reporte de aplicaciones es alto, daremos una explicación de las metodologías que son comúnmente aplicadas y mencionaremos algunas publicaciones que hacen referencia a cada rama de la investigación.

Agrupamiento de los datos

Formalmente, dado un conjunto de datos, el objetivo de agrupamiento es dividir los datos en un conjunto de agrupaciones tales que los elementos asignados a un grupo determinado son similares a la conexión en algún predefinido sentido. Sin embargo, no todos los grafos tienen estructura con agrupamiento natural. No obstante, la salida de un algoritmo de agrupamiento es el agrupamiento para cualquier grafo de entrada. Si la estructura de los grafos esta completamente uniforme, con los lados eventualmente distribuidos sobre un conjunto de vértices, el agrupamiento computarizado para cualquier algoritmo será un poco arbitrario. La calidad de las medidas ayuda a determinar si hay agrupamientos significantes presentes en el grafo y si hay un agrupamiento revelado.

Conclusión de las observaciones

En este estudio se han revisado algunos de las definiciones esenciales y las técnicas de agrupamiento de grafos. En general, esto parece que muchas de las buenas medidas de agrupamiento están entrelazadas: los métodos son en ese sentido un espectro de métodos que en consecuencia son relacionados a caminos aleatorios que modelan el comportamiento de redes electrónicas y también sirven para hacer intermediación a los cálculos, entre otras cosas. Esas conexiones teóricas entre muchos de los métodos dada la razón para creer que nosotros estamos en el camino correcto: el campo del agrupamiento de los grafos parece estar confundiendose fundamentalmente de definiciones similares, aunque algunos de los puntos de partida para los algoritmos son muy distantes.

Se resolvieron tanto los enfoques globales y locales y se discutió sobre el delicado problema de seleccionar un apropiado método para la tarea que nos ocupa, seleccionar buenos valores de parámetros, y evaluar la calidad del agrupamiento de los datos. Las herramientas ya están disponibles y son tan variadas como las aplicaciones del agrupamiento de los grafos, aunque queda mucho por hacerse.