El algoritmo de Girvan-Newman (llamado así por Michelle Girvan y Mark Newman ) es un método jerárquico utilizado para detectar comunidades en sistemas complejos . [1]
El algoritmo de 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 centrales para las comunidades, el algoritmo de Girvan-Newman se centra en los bordes que probablemente se encuentren "entre" las comunidades.
La intermediación de vértices es un indicador de nodos altamente centrales en redes. Para cualquier nodo , la intermediación de vértices se define como la fracción de caminos más cortos entre pares de nodos que pasan por él. Es relevante para los modelos en los que la red modula la transferencia de bienes entre puntos de inicio y fin conocidos, bajo el supuesto de que dicha transferencia busca la ruta más corta disponible.
El algoritmo de Girvan-Newman extiende esta definición al caso de los bordes, definiendo la "intermediación de bordes" de un borde como el número de caminos más cortos entre pares de nodos que corren a lo largo de él. Si hay más de un camino más corto entre un par de nodos, a cada camino se le asigna el mismo peso, de modo que el peso total de todos los caminos es igual a la unidad. Si una red contiene comunidades o grupos que están conectados de forma vaga por unos pocos bordes entre grupos, entonces todos los caminos más cortos entre diferentes comunidades deben pasar por uno de estos pocos bordes. Por lo tanto, los bordes que conectan comunidades tendrán una alta intermediación de bordes (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 la comunidad se resumen a continuación
El hecho de que las únicas intermediaciones que se recalculen sean las que se ven afectadas 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 producen errores graves. La razón es que la red se adapta a las nuevas condiciones establecidas después de la eliminación de la arista. Por ejemplo, si dos comunidades están conectadas por más de una arista, entonces no hay garantía de que todas estas aristas tengan una intermediación alta. De acuerdo con el método, sabemos que al menos una de ellas la tendrá, pero no se sabe nada más que eso. Al recalcular las intermediaciones después de la eliminación de cada arista, se garantiza que al menos una de las aristas restantes entre dos comunidades siempre tendrá un valor alto.
El resultado final del algoritmo de Girvan-Newman es un dendrograma . A medida que se ejecuta el algoritmo de 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.
