El algoritmo Girvan-Newman (llamado así por Michelle Girvan y Mark Newman ) es un método jerárquico utilizado para detectar comunidades en sistemas complejos . [1]
Intermediación de borde y estructura comunitaria
El algoritmo Girvan-Newman detecta comunidades eliminando progresivamente los bordes de la red original. Los componentes conectados de la red restante son las comunidades. En lugar de intentar construir una medida que nos diga qué bordes son los más importantes para las comunidades, el algoritmo Girvan-Newman se centra en los bordes que probablemente estén "entre" comunidades.
La intermediación de vértices es un indicador de nodos muy centrales en las redes. Para cualquier nodo, la intermediación de vértices se define como el número de caminos más cortos entre pares de nodos que lo atraviesan. Es relevante para los modelos en los que la red modula la transferencia de bienes entre los puntos de inicio y finalización conocidos, bajo el supuesto de que dicha transferencia busca la ruta más corta disponible.
El algoritmo Girvan-Newman extiende esta definición al caso de las aristas, definiendo la "intermediación de aristas" de una arista como el número de caminos más cortos entre pares de nodos que corren a lo largo de ella. Si hay más de una ruta más corta entre un par de nodos, a cada ruta se le asigna la misma ponderación de modo que la ponderación total de todas las rutas sea igual a la unidad. Si una red contiene comunidades o grupos que están débilmente conectados por unos pocos bordes entre grupos, entonces todos los caminos más cortos entre las diferentes comunidades deben ir a lo largo de uno de estos pocos bordes. Por lo tanto, los bordes que conectan a las comunidades tendrán un alto grado de intermediación (al menos uno de ellos). Al eliminar estos bordes, los grupos se separan entre sí y, por lo tanto, se revela la estructura comunitaria subyacente de la red.
Los pasos del algoritmo para la detección de comunidades se resumen a continuación.
- La intermediación de todos los bordes existentes en la red se calcula primero.
- Se eliminan los bordes con el mayor grado de intermediación.
- Se vuelve a calcular la intermediación de todos los bordes afectados por la eliminación.
- Los pasos 2 y 3 se repiten hasta que no queden bordes.
El hecho de que los únicos intermediarios que se recalculan sean solo los afectados por la eliminación, puede reducir el tiempo de ejecución de la simulación del proceso en las computadoras. Sin embargo, la centralidad de intermediación debe recalcularse con cada paso o se producirán errores graves. La razón es que la red se adapta a las nuevas condiciones establecidas después de la eliminación del borde. Por ejemplo, si dos comunidades están conectadas por más de un borde, entonces no hay garantía de que todos estos bordes tengan un alto nivel de intermediación. Según el método, sabemos que al menos uno de ellos tendrá, pero nada más se sabe. Al volver a calcular entremedios después de la eliminación de cada borde, se asegura que al menos uno de los bordes restantes entre dos comunidades siempre tendrá un valor alto.
El resultado final del algoritmo Girvan-Newman es un dendrograma . A medida que se ejecuta el algoritmo Girvan-Newman, el dendrograma se produce de arriba hacia abajo (es decir, la red se divide en diferentes comunidades con la eliminación sucesiva de enlaces). Las hojas del dendrograma son nodos individuales.
Ver también
Referencias
- ^ Girvan M. y Newman MEJ, Estructura comunitaria en redes sociales y biológicas , Proc. Natl. Acad. Sci. EE. UU. 99 , 7821–7826 (2002)