Detección de comunidades: Algoritmo Girvan-Newman

Algoritmo de Girvan - Newman


El algoritmo de Girvan -Newman (el nombre de Michelle Girvan y Mark Newman ) es un método jerárquico utilizado para detectar las comunidades en sistemas complejos. [1]

Intermediación  de enlaces y estructura de la comunidad 

El algoritmo de Girvan -Newman detecta comunidades eliminando progresivamente los enlaces de la red original. Los componentes conectados de la red que queda son las comunidades. En lugar de tratar de construir una medida que nos indica que los enlaces son los más importantes para las comunidades, el algoritmo de Girvan -Newman se centra en los enlaces que son más probable " entre " comunidades.

La intermediación de vértices se ha estudiado en el pasado como una medida de la centralidad y la influencia de los nodos en las redes. Para cualquier nodo i, intermediación vértice se define como el número de caminos más cortos entre pares de nodos que se ejecutan a través de él. Es una medida de la influencia de un nodo sobre el flujo de información entre otros nodos, especialmente en los casos donde el flujo de información a través de una red sigue principalmente el camino más corto disponible. El algoritmo de Girvan - Newman extiende esta definición para el caso de enlaces, la definición de la " intermediación enlace " de un enlace como el número de caminos más cortos entre pares de nodos que se ejecutan a lo largo de ella. Si hay más de una ruta más corta entre un par de nodos, cada ruta se le asigna el mismo peso tal que el peso total de todos los caminos es igual a la unidad. Si una red contiene las comunidades o grupos que están sólo vagamente conectados por unos enlaces entre grupos, entonces todos los caminos más cortos entre las diferentes comunidades deben pasar por una de estas pocas aristas. Por lo tanto, los enlaces de conexión comunidades tendrán alta intermediación enlace (al menos uno de ellos). Mediante la eliminación de estos enlaces, los grupos están separados uno de otro y por lo que la estructura de la comunidad subyacente de la red se revela.

Los pasos del algoritmo para la detección de la comunidad se resumen a continuación

1. La intermediación de todos los enlaces existentes en la red se calcula primero.
2. Se elimina el enlace con la más alta intermediación.
3. La intermediación de todos los enlaces afectados por la eliminación se vuelve a calcular.
4. Pasos 2 y 3 se repiten hasta que no hay quedan enlaces.

El hecho de que los únicos betweennesses siendo recalculados son sólo los que se ven afectados por la eliminación, puede disminuir el tiempo de ejecución del proceso de simulación ' en las computadoras. Sin embargo, la centralidad de intermediación debe ser recalculado con cada paso, o se producen errores graves. La razón es que la red se adapta a las nuevas condiciones establecidas después de la eliminación enlace. Por ejemplo, si dos comunidades están conectados por más de un enlace, entonces no hay garantía de que todos estos enlaces tendrán alta intermediación. De acuerdo con el método, sabemos que al menos una de ellas tendrá, pero nada más que lo que se sabe. Por recalcular betweennesses después de la eliminación de cada enlace, se asegura que al menos uno de los enlaces restantes entre dos comunidades siempre tendrá un valor alto.

El resultado final del algoritmo de Girvan - Newman es un dendrograma. Cuando se ejecuta el algoritmo de Girvan - Newman, el dendrograma se produce a partir de la parte superior hacia abajo ( es decir, la red se divide en diferentes comunidades con la eliminación sucesiva de enlaces). Las hojas de la dendrograma son nodos individuales.

Referencia

1. Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99, 7821–7826 (2002)

Wikipedia