Reseña Articulo Dra. Elisa Schaeffer

En este ocasión voy a escribir sobre el articulo Graph clustering de la Dra. Satu Elisa Schaffer, el cual fue publicado en el 2007.

El articulo trata sobre definiciones y métodos de  agrupación de grafos, las definiciones de que una agrupamiento en un grafo y la medidas de calidad de este. Nosotros mostramos un algoritmo mundial para producir un agrupamiento  de vértices en un grafo, después de lo cual se discute la tarea de identificar un agrupamiento de vértices de una semilla  específica por computación local.

Cualquier información no uniforme contiene una estructura subyacente de heterogeneidad en la información. El proceso se identificar esta estructura en términos de agrupamiento de elemento  de datos es llamada clustering, también llamada información clasificada. El grupo resultante es llamado clusters. El grupo es normalmente definido por una medición definida por los datos.

Los grafos son estructuras formadas por una serie de vértices (también llamados nodos) y la conexión entre ellos son los lados o bordes. El agrupamiento de grafos es la tarea de agrupar los vértices de un grafo considerando la estructura de los bordes del grafo de manera que debería de haber muchos bordes dentro del agrupamiento y relativamente pocos entre el agrupamiento

Teoría de Grafos

Un grafo G es un par de conjuntos G = (V, E). V es el conjunto de vértices y  el numero de vértices n=|V| es el orden de la grafica. El conjunto E contiene los bordes del  grafo.  En un grafo no dirigido, cada arista es un par no ordenado {v, w}. En un grafo dirigido (también llama dígrafo en la literatura mucho), los bordes son pares ordenados. Los vértices v y w son llamados los extremos de los bordes. La borde cuenta | E | = m es el tamaño del gráfico. En un grafo ponderado, una función de peso! : E! R se define que asigna un peso en cada borde. Un grafo es plano si se puede dibujar en un plano sin que ninguno de los bordes de cruce.

Es común que en aplicaciones, los grafos no son simples, ligeros y sin dirección. Si más de un bordes está permitido entres dos vértices, en lugar de una adyacencia binaria la matriz se acostumbra a utilizar una matriz que determina para cada par de vértices cuántas aristas que comparten. Gráficos con tales multiplicidades borde se llaman multígrafos.

Aplicaciones de graph clustering.

·         Transformación de Datos

·         Redes de información y uso de la información

·         Sistemas de Base de Datos

·         Redes Biológica y sociológica

·         Otras Aplicaciones

Problemas y futuro

Los 3 principales problemas de graph clustering son:

·         Selección de parámetros: ¿Cómo determina el usuario los valores de los parámetros para dar una entrada para un algoritmo de clusterig?

·          Escalabilidad: ¿cómo el consumo de tiempo de ejecución y la memoria del algoritmo se comportan para los gráficos de entrada masiva?

·         Evaluación: cómo decidir cuál de varios agrupamientos es el mejor.

Los fundamentos teóricos de graph clustering nos están totalmente explorados; pero se no se espera que exista una sola respuesta para las preguntas de graph clustering.