Algoritmo de Girvan Newman

El Algoritmo de Girvan Newman es uno de los métodos más utilizados de orden jerárquico para detectar comunidades dentro de sistemas complejos de datos. Posee características y funcionalidades que le permiten ser considerado uno de los métodos más eficientes dentro del mundo de la detección de comunidades.

A continuación, conoceremos un poco más sobre el orígen de este algoritmo, su funcionamiento y como podemos aprovecharlo al máximo para estudiar nuestros grafos.

Algoritmo de Girvan Newman

Este algoritmo es un método jerárquico desarrollado por  Michelle Girvan y Mark Newman, utilizado para detectar las comunidades en sistemas complejos. Este algoritmo se encarga de detectar comunidades eliminando progresivamente los enlaces de la red original. Los componentes conectados dentro de la red que resulta de este análisis, son las comunidades.

Este método busca en vez de construir una medida que nos indica cuales enlaces serían los más importantes para las comunidades, se centra en mostrar cuáles enlaces poseen mayor probabilidad entre comunidades. Descubramos un poco más sobre su funcionamiento.

algoritmo de Girvan Newman

Intermediación de enlaces y estructura de la comunidad

El proceso conocido como intermediación de enlaces es estudiado como una medida de centralidad. Esta nos permite conocer la influencia de los nodos dentro de un grafo. Para cualquier nodo perteneciente a un grafo, la intermediación de un vértice es el número de camino más cortos entre pares de nodos que se ejecutan a través de él. Con esta medida podemos conocer la influencia real que posee un nodo sobre el flujo de información entre otros nodos, especialmente en los casos donde el flujo de información debe realizarse a través del camino más corto disponible.

El algoritmo de Girvan Newman aplica una intermediación enlace cómo el número de caminos más cortos entre pares de nodos que se ejecutan a lo largo de ella. Si existe más de una ruta corta entre un par de nodos, cada ruta recibe una asignación de peso similar al peso total de todos los caminos que 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.

Pasos del algoritmo para la detección de la comunidad

  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 queden más enlaces

algoritmo de Girvan Newman

El hecho de que las únicas intermediaciones que son recalculadas, son las que se ven afectadas por la eliminación. Este proceso puede disminuir el tiempo de ejecución del proceso de simulación en un software de análisis. 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 la intermediación 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.

Esperamos que esta información sea de utilidad para conocer un poco más sobre los algoritmos que podemos utilizar para la detección de comunidades.

Visita más de Grapheverywhere para conocer todo lo que debes saber sobre detección de comunidades. 

Share This