Agrupación jerárquica de redes - Hierarchical clustering of networks

El agrupamiento jerárquico es un método para encontrar estructuras comunitarias en una red . La técnica organiza la red en una jerarquía de grupos de acuerdo con una función de peso específica. Luego, los datos se pueden representar en una estructura de árbol conocida como dendrograma . El agrupamiento jerárquico puede ser aglomerativo o divisivo dependiendo de si se procede a través del algoritmo agregando enlaces o eliminando enlaces de la red, respectivamente. Una técnica divisiva es el algoritmo Girvan-Newman .

Algoritmo

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 siguiente), 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 los nodos en orden de peso decreciente entre los pares (en el caso divisivo, comience desde la red original y elimine los enlaces en orden de peso decreciente). A medida que se agregan enlaces, comienzan a formarse subconjuntos conectados. Estos representan las estructuras comunitarias de la red. ${\ Displaystyle W_ {ij}}$ ${\ Displaystyle (i, j)}$

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 . Los cortes horizontales del árbol en un nivel dado indican las comunidades que existen por encima y por debajo de un valor del peso.

Pesos

Hay muchas ponderaciones posibles para su uso en algoritmos de agrupamiento jerárquico. El peso específico utilizado viene dictado 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, en comparación con los datos del mundo real con una estructura de comunidad conocida, las diversas técnicas de ponderación se han cumplido con diversos grados de éxito.

Dos ponderaciones que se han utilizado anteriormente con éxito variable son el número de rutas independientes de nodo entre cada par de vértices y la cantidad total de rutas entre vértices ponderadas por la longitud de la ruta. 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 al pequeño número 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.

La centralidad de la intermediación de los bordes se ha utilizado con éxito como ponderación en el algoritmo de Girvan-Newman . Esta técnica es similar a un algoritmo de agrupamiento jerárquico divisivo, excepto que los pesos se recalculan con 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. Este método proporciona una alternativa computacionalmente menos costosa al algoritmo de Girvan-Newman al tiempo que produce resultados similares.

Ver también

• Topología de la red
• Taxonomía numérica
• Estructura de árbol

Referencias