Algoritmo de agrupamiento HCS

El algoritmo de agrupamiento de subgrafos altamente conectados (HCS, por sus siglas en inglés) (también conocido como algoritmo HCS y otros nombres como clústeres/componentes/núcleos altamente conectados ) es un algoritmo basado en la conectividad de grafos para el análisis de clústeres . Funciona representando los datos de similitud en un grafo de similitud y luego encontrando todos los subgrafos altamente conectados. No hace ninguna suposición previa sobre el número de clústeres. Este algoritmo fue publicado por Erez Hartuv y Ron Shamir en 2000. ^{[ 1 ]}

El algoritmo HCS proporciona una solución de agrupamiento, que es intrínsecamente significativa en el dominio de la aplicación, ya que cada grupo de soluciones debe tener un diámetro de 2, mientras que la unión de dos grupos de soluciones tendrá un diámetro de 3.

El objetivo del análisis de clústeres es agrupar elementos en subconjuntos disjuntos, o clústeres, según su similitud. De esta forma, los elementos de un mismo clúster presentan una alta similitud entre sí (homogeneidad), mientras que los de clústeres diferentes presentan baja similitud (separación). El grafo de similitud es uno de los modelos para representar la similitud entre elementos y, a su vez, facilitar la generación de clústeres. Para construir un grafo de similitud a partir de datos de similitud, se representan los elementos como vértices y se generan aristas entre ellos cuando el valor de similitud supera un umbral determinado.

En un grafo de similitud, cuantas más aristas existan para un número dado de vértices, más similares serán esos vértices entre sí. En otras palabras, si intentamos desconectar un grafo de similitud eliminando aristas, cuantas más aristas debamos eliminar antes de que el grafo se desconecte, más similares serán los vértices que lo componen. El corte mínimo es el conjunto mínimo de aristas sin el cual el grafo se desconectará.

El algoritmo de agrupamiento HCS encuentra todos los subgrafos con n vértices tales que el corte mínimo de dichos subgrafos contiene más de n/2 aristas, y los identifica como clústeres. Dicho subgrafo se denomina Subgrafo Altamente Conectado (HCS). Los vértices individuales no se consideran clústeres y se agrupan en un conjunto de elementos únicos S.

Dado un grafo de similitud G(V,E), el algoritmo de agrupamiento HCS comprobará si ya está altamente conectado; si es así, devuelve G; de lo contrario, utiliza el corte mínimo de G para particionar G en dos subgrafos H y H', y ejecuta recursivamente el algoritmo de agrupamiento HCS en H y H'.

La siguiente animación muestra cómo el algoritmo de agrupamiento HCS divide un gráfico de similitud en tres grupos.

La función HCS(G(V, E)) es si G está altamente conectado entonces devuelve ( G ) de lo contrario ( H1 , H2 , C ) ← MINIMUMCUT( G ) HCS( H1 ) HCS( H2 ) fin si fin función

El paso de encontrar el corte mínimo en el grafo G es una subrutina que puede implementarse utilizando diferentes algoritmos para este problema. A continuación se muestra un ejemplo de algoritmo para encontrar el corte mínimo mediante aleatorización.

El tiempo de ejecución del algoritmo de agrupamiento HCS está limitado por N × f(n, m). f(n, m) es la complejidad temporal de calcular un corte mínimo en un grafo con n vértices y m aristas, y N es el número de clústeres encontrados. En muchas aplicaciones, N  <<  n.

Para algoritmos rápidos para encontrar un corte mínimo en un grafo no ponderado:

Los clústeres generados por el algoritmo de agrupamiento HCS poseen varias propiedades que pueden demostrar la homogeneidad y la separación de la solución.

Teorema 1 El diámetro de todo grafo altamente conectado es como máximo dos.

Demostración: Sea n=|G|. Si G tiene un vértice x con grado <= n/2, entonces G tiene un corte mínimo (que aísla a x) con aristas <= n/2, por lo que G no es altamente conexo. Por lo tanto, si G es altamente conexo, cada vértice tiene grado >= n/2. Existe un famoso teorema en teoría de grafos que dice que si cada vértice tiene grado >= n/2, entonces el diámetro de G (el camino más largo entre dos nodos cualesquiera) <= 2.

Teorema 2 (a) El número de aristas en un grafo altamente conectado es cuadrático. (b) El número de aristas eliminadas por cada iteración del algoritmo HCS es como máximo lineal.

Demostración: (a) Del Teorema 1 sabemos que cada vértice tiene grado >= n/2. Por lo tanto, el número de aristas en un grafo 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 aristas.

Los teoremas 1 y 2a proporcionan una fuerte indicación de la homogeneidad de un clúster final. Un mejor rendimiento se aproxima al caso en que todos los vértices de un clúster están conectados, lo cual es demasiado estricto y también NP-difícil .

El teorema 2b indica separación ya que cualesquiera dos grupos finales C1 y C2 no se habrían separado a menos que hubiera como máximo O(C1+C2) aristas entre ellos (en contraste con las aristas cuadráticas dentro de los grupos).

Adopción de Singletons : Los elementos que quedan como singletons tras el proceso de agrupamiento inicial pueden ser "adoptados" por los clústeres en función de su similitud con ellos. Si el número máximo de vecinos de un clúster específico es suficientemente grande, dicho elemento puede añadirse a ese clúster.

Eliminación de vértices de bajo grado : Cuando el grafo de entrada contiene vértices con grados bajos, no conviene ejecutar el algoritmo, ya que resulta computacionalmente costoso y poco informativo. Como alternativa, una mejora del algoritmo consiste en eliminar primero todos los vértices con un grado inferior a un umbral determinado.

• Análisis de la expresión génica ^{[ 2 ]} La hibridación de oligonucleótidos sintéticos a cDNAs dispuestos en matrices produce una huella digital para cada clon de cDNA. Al ejecutar el algoritmo HCS sobre estas huellas digitales, se pueden identificar clones que corresponden al mismo gen .
• Descubrimiento de la estructura de la red PPI ^{[ 3 ]} Utilizando la agrupación HCS para detectar subredes densas en PPI que pueden tener significado biológico y representar procesos biológicos.
• "Estudio de algoritmos de agrupamiento." Redes neuronales, Transacciones IEEE ^{[ 4 ]}
• El algoritmo de agrupamiento CLICK ^{[ 5 ]} es una adaptación del algoritmo HCS en gráficos de similitud ponderados, donde el peso se asigna con un sabor a probabilidad.
• https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage Particionamiento de redes biológicas en clústeres altamente conectados con cobertura máxima de bordes] ^{[ 6 ]}
• Implementación en R
• Implementación en Python