El algoritmo de agrupación HCS (Highly Connected Subgraphs) [1] (también conocido como el algoritmo HCS y otros nombres como Clústeres / Componentes / Núcleos altamente conectados ) es un algoritmo basado en la conectividad de gráficos para el análisis de agrupaciones . Funciona representando los datos de similitud en un gráfico de similitud y luego encontrando todos los subgrafos altamente conectados. No hace suposiciones previas sobre el número de conglomerados. Este algoritmo fue publicado por Erez Hartuv y Ron Shamir en 2000.
Clase | Análisis de conglomerados (en un gráfico de similitud) |
---|---|
Estructura de datos | Grafico |
Rendimiento en el peor de los casos | O (2N xf (n, m)) |
El algoritmo HCS proporciona una solución de agrupamiento, que es inherentemente significativa en el dominio de la aplicación, ya que cada grupo de soluciones debe tener un diámetro 2, mientras que una unión de dos grupos de soluciones tendrá un diámetro 3.
Modelado y preprocesamiento de similitudes
El objetivo del análisis de conglomerados es agrupar elementos en subconjuntos disjuntos, o conglomerados, según la similitud entre los elementos, de modo que los elementos del mismo conglomerado sean muy similares entre sí (homogeneidad), mientras que los elementos de diferentes conglomerados tienen poca similitud entre sí. (separación). El gráfico de similitud es uno de los modelos que representa la similitud entre elementos y, a su vez, facilita la generación de clusters. Para construir un gráfico de similitud a partir de datos de similitud, represente elementos como vértices y obtenga bordes entre vértices cuando el valor de similitud entre ellos esté por encima de algún umbral.
Algoritmo
En el gráfico de similitud, cuantas más aristas existan para un número determinado de vértices, más similar será ese conjunto de vértices entre sí. En otras palabras, si intentamos desconectar un gráfico de similitud quitando bordes, cuantos más bordes necesitemos eliminar antes de que el gráfico se desconecte, más similares serán los vértices en este gráfico. El corte mínimo es un conjunto mínimo de bordes sin los cuales el gráfico se desconectará.
El algoritmo de agrupación de HCS encuentra todos los subgrafos con n vértices de modo que el corte mínimo de esos subgrafos contenga más de n / 2 aristas y los identifica como agrupaciones. Dicho subgrafo se denomina Subgrafo altamente conectado (HCS). Los vértices individuales no se consideran clústeres y se agrupan en un conjunto de singletons S.
Dado un gráfico de similitud G (V, E), el algoritmo de agrupación de HCS verificará si ya está altamente conectado, si es así, devuelve G; de lo contrario, usa el corte mínimo de G para dividir G en dos subgráficos H y H ', y ejecutar de forma recursiva Algoritmo de agrupamiento de HCS en H y H '.
Ejemplo
La siguiente animación muestra cómo el algoritmo de agrupación de HCS divide un gráfico de similitud en tres agrupaciones.
Pseudocódigo
la función HCS (G (V, E)) es si G está altamente conectado, entonces regresa ( G ) else ( H1 , H2 , C ) ← MINIMUMCUT ( G ) HCS ( H1 ) HCS ( H2 ) finaliza si finaliza la función
El paso de encontrar el corte mínimo en el gráfico G es una subrutina que se puede implementar usando diferentes algoritmos para este problema. Consulte a continuación un algoritmo de ejemplo para encontrar el corte mínimo mediante la aleatorización.
Complejidad
El tiempo de ejecución del algoritmo de agrupación de HCS está limitado por N × f (n, m). f (n, m) es la complejidad temporal de calcular un corte mínimo en un gráfico con n vértices y m aristas, y N es el número de conglomerados encontrados. En muchas aplicaciones N << n.
Para algoritmos rápidos para encontrar un corte mínimo en un gráfico no ponderado:
Pruebas de propiedad
Los grupos producidos por el algoritmo de agrupamiento de HCS poseen varias propiedades, que pueden demostrar la homogeneidad y separación de la solución.
Teorema 1 El diámetro de cada gráfico altamente conectado es como máximo dos.
Prueba: Sea n = | G |. Si G tiene un vértice x con grado <= n / 2, entonces G tiene un corte mínimo (que aísla x) con aristas <= n / 2, por lo que G no está muy conectado. Entonces, si G está altamente conectado, cada vértice tiene un grado> = n / 2. Hay un teorema famoso en la teoría de grafos que dice que si cada vértice tiene un grado> = n / 2, entonces el diámetro de G (el camino más largo entre dos nodos) <= 2.
Teorema 2 (a) El número de aristas en una gráfica altamente conectada es cuadrática. (b) El número de bordes eliminados por cada iteración del algoritmo HCS es lineal como máximo.
Demostración: (a) A partir del teorema 1 sabemos que todo vértice tiene grado> = n / 2. Por lo tanto, el número de aristas en un gráfico altamente conectado debe ser al menos (n × n / 2) / 2, donde sumamos los grados de cada vértice y dividimos por 2.
(b) Por definición, cada iteración elimina un corte mínimo con <= n / 2 bordes.
Los teoremas 1 y 2a proporcionan una fuerte indicación de la homogeneidad de un grupo final. Hacerlo mejor se aproxima al caso en el que todos los vértices de un clúster están conectados, lo cual es demasiado estricto y también NP-hard .
El teorema 2b indica separación ya que dos grupos finales C1 y C2 no se habrían separado a menos que hubiera como máximo O (C1 + C2) bordes entre ellos (contraste con los bordes cuadráticos dentro de los grupos).
Variaciones
Adopción de singletons : los elementos que quedan como singletons por el proceso de agrupamiento inicial pueden ser "adoptados" por clusters en función de la similitud con el clúster. Si el número máximo de vecinos de un clúster específico es lo suficientemente grande, se puede agregar a ese clúster.
Eliminación de vértices de bajo grado : cuando el gráfico de entrada tiene vértices con grados bajos, no vale la pena ejecutar el algoritmo ya que es computacionalmente costoso y no informativo. Alternativamente, un refinamiento del algoritmo puede eliminar primero todos los vértices con un grado menor que cierto umbral.
Ejemplos de uso de HCS
- Análisis de expresión génica [2] La hibridación de oligonucleótidos sintéticos con ADNc en matriz produce una huella dactilar para cada clon de ADNc. Ejecutar el algoritmo HCS en estas huellas dactilares puede identificar clones correspondientes al mismo gen.
- Descubrimiento de la estructura de la red PPI [3] Uso de la agrupación de HCS para detectar subredes densas en PPI que pueden tener un significado biológico y representar procesos biológicos.
- "Estudio de algoritmos de agrupamiento". Redes neuronales, transacciones IEEE [4]
- El algoritmo de agrupación CLICK [5] es una adaptación del algoritmo HCS en gráficos de similitud ponderados, donde el peso se asigna con un sabor de probabilidad.
- https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage Partición de redes biológicas en clústeres altamente conectados con máxima cobertura de borde] [6]
Referencias
- ↑ Hartuv, E .; Shamir, R. (2000), "Un algoritmo de agrupamiento basado en la conectividad de gráficos", Information Processing Letters , 76 (4–6): 175–181, doi : 10.1016 / S0020-0190 (00) 00142-3
- ↑ E Hartuv, AO Schmitt, J Lange, S Meier-Ewert, H Lehrach, R Shamir. "Un algoritmo para agrupar huellas dactilares de ADNc". Genómica 66, no. 3 (2000): 249-256.
- ^ Jurisica, Igor y Dennis Wigle. Descubrimiento de conocimientos en proteómica. Vol. 8. Prensa CRC, 2006.
- ^ Xu, Rui y Donald Wunsch. "Estudio de algoritmos de agrupamiento". Redes neuronales, transacciones IEEE en 16, no. 3 (2005): 645-678.
- ^ Sharan, R .; Shamir, R. (2000), "CLIC: Un algoritmo de agrupamiento con aplicaciones al análisis de expresión genética", Actas ISMB '00 , 8 : 307–316C
- ^ Huffner, F .; Komusiewicz, C .; Liebtrau, A; Niedermeier, R (2014), "Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage", Transacciones IEEE / ACM sobre biología computacional y bioinformática , 11 (3): 455–467, CiteSeerX 10.1.1.377.1900 , doi : 10.1109 /TCBB.2013.177 , PMID 26356014