La agrupación jerárquica es un método para encontrar estructuras comunitarias en una red . La técnica organiza la red en una jerarquía de grupos según una función de peso especificada. Los datos pueden representarse en una estructura de árbol conocida como dendrograma . La agrupación jerárquica puede ser aglomerativa o divisiva, dependiendo de si se procede a través del algoritmo agregando enlaces a la red o eliminando enlaces de la red, respectivamente. Una técnica divisiva es el algoritmo de Girvan-Newman .
En el algoritmo de agrupamiento jerárquico, primero se asigna un peso a cada par de vértices de la red. El peso, que puede variar según la implementación (consulte la sección a continuación), tiene como objetivo indicar qué tan estrechamente relacionados están los vértices. Luego, comenzando con todos los nodos de la red desconectados, comience a emparejar nodos de mayor a menor peso entre los pares (en el caso divisivo, comience desde la red original y elimine los enlaces de menor a mayor peso). A medida que se agregan enlaces, comienzan a formarse subconjuntos conectados. Estos representan las estructuras de la comunidad de la red.
Los componentes de cada paso iterativo son siempre un subconjunto de otras estructuras. Por lo tanto, los subconjuntos se pueden representar mediante un diagrama de árbol o dendrograma . Las secciones horizontales del árbol en un nivel determinado indican las comunidades que existen por encima y por debajo de un valor del peso.
Existen muchos pesos posibles para usar en algoritmos de agrupamiento jerárquico. El peso específico utilizado está determinado por los datos, así como por consideraciones de velocidad computacional. Además, las comunidades que se encuentran en la red dependen en gran medida de la elección de la función de ponderación. Por lo tanto, cuando se comparan con datos del mundo real con una estructura de comunidad conocida, las diversas técnicas de ponderación han tenido distintos grados de éxito.
Dos ponderaciones que se han utilizado anteriormente con éxito variable son la cantidad de caminos independientes de los nodos entre cada par de vértices y la cantidad total de caminos entre vértices ponderados por la longitud del camino. Sin embargo, una desventaja de estas ponderaciones es que ambos esquemas de ponderación tienden a separar los vértices periféricos individuales de sus comunidades legítimas debido a la pequeña cantidad de caminos que van a estos vértices. Por esta razón, su uso en técnicas de agrupamiento jerárquico está lejos de ser óptimo. [1]
La centralidad de los bordes intermedios se ha utilizado con éxito como ponderación en el algoritmo de Girvan-Newman . [1] Esta técnica es similar a un algoritmo de agrupamiento jerárquico divisivo, excepto que las ponderaciones se recalculan en cada paso.
El cambio en la modularidad de la red con la adición de un nodo también se ha utilizado con éxito como ponderación. [2] Este método proporciona una alternativa computacionalmente menos costosa que el algoritmo de Girvan-Newman y al mismo tiempo produce resultados similares.
