Usando el algoritmo de Leiden para encontrar grupos bien conectados en redes
Vincent Traag, Ludo Waltman, Nees Jan van EckCWTS
Introducción
Un desarrollo emocionante en el campo de los estudios cuantitativos de ciencias es el uso de enfoques de agrupación algorítmica para construir clasificaciones a nivel de artículo basadas en redes de citas. Hasta hace poco, la mayoría de las clasificaciones se basaban en categorizar revistas en lugar de artículos individuales. Esto es comprensible dados los desafíos sustanciales de clasificar millones de artículos. En CWTS, ahora trabajamos rutinariamente con clasificaciones a nivel de artículo. Hemos dedicado bastante tiempo a desarrollar algoritmos de agrupamiento para crear estas clasificaciones. Estos algoritmos tienen un impacto más allá de nuestro propio campo de investigación y son de interés para muchos científicos de redes.Te sorprenderá saber que uno de los algoritmos de agrupamiento más famosos, comúnmente conocido como el algoritmo de Lovaina, en realidad tiene un defecto importante: los grupos que encuentra pueden estar arbitrariamente mal conectados. Por ejemplo, el algoritmo de Lovaina puede agrupar artículos en un grupo, aunque algunos de los artículos no tienen enlaces de citas con los otros artículos en el grupo. Aquí informamos brevemente sobre un nuevo algoritmo que hemos desarrollado, que llamamos algoritmo de Leiden. Este algoritmo garantiza encontrar clústeres bien conectados. ¡Aún mejor, lo hace mucho más rápido que el algoritmo de Louvain!
Algoritmo de Louvain
El algoritmo de Louvain es un algoritmo simple y elegante que es más eficiente que muchos otros algoritmos de agrupación en red. Cuando se introdujo en 2008, se aplicó a una gran red de más de cien millones de nodos y mil millones de enlaces. Se clasificó entre los mejores algoritmos de agrupación en estudios comparativos en 2009 y 2016. El algoritmo de Lovaina busca agrupaciones de alta calidad moviendo nodos individuales, por ejemplo, artículos individuales en una red de citas, de una agrupación a otra de tal manera que La calidad de los grupos se mejora tanto como sea posible. Cuando los grupos no pueden mejorarse más moviendo nodos individuales, el algoritmo de Lovaina hace algo ingenioso: agrega la red, de modo que cada grupo en la red original se convierte en un nodo en la red agregada. En la red agregada, el algoritmo comienza a mover nodos individuales de un clúster a otro. Al repetir el movimiento y la agregación de nodos, el algoritmo de Lovaina puede encontrar grupos de alta calidad en poco tiempo. Desafortunadamente, sin embargo, este enfoque también conduce a una falla importante, que parece haber pasado desapercibida durante la última década.
A veces, un nodo funciona como intermediario o puente para el resto de su clúster. Sin ese nodo crucial, el clúster ya no estaría conectado. Dado que el algoritmo de Lovaina sigue moviendo nodos de un grupo a otro, en algún momento puede mover el nodo crucial a un grupo diferente, rompiendo así la conectividad del grupo original. Quizás sorprendentemente, el algoritmo de Lovaina no puede arreglar esta conectividad rota. La ruptura completa de la conectividad es lo peor que le puede pasar a un clúster. Es el ejemplo más extremo de un problema más general del algoritmo de Lovaina: el algoritmo puede producir grupos que están mal conectados y que deberían haberse dividido en varios grupos.
Algoritmo de Leiden
Solucionamos este problema del algoritmo de Lovaina en nuestro nuevo algoritmo de Leiden. De manera similar al algoritmo de movimiento local inteligente que se desarrolló previamente en CWTS, el algoritmo de Leiden puede dividir grupos en lugar de solo fusionarlos, como lo hace el algoritmo de Lovaina. Al dividir los clústeres de una manera específica, el algoritmo de Leiden garantiza que los clústeres estén bien conectados. Además, el algoritmo garantiza más que esto: si ejecutamos el algoritmo repetidamente, eventualmente obtenemos grupos que son subconjuntos óptimos. Esto significa que es imposible mejorar la calidad de los clústeres moviendo uno o más nodos de un clúster a otro. Esta es una propiedad fuerte del algoritmo de Leiden. Establece que los grupos que encuentra no están muy lejos de ser óptimos. Finalmente, en lugar de verificar continuamente para todos los nodos en una red si se pueden mover a un clúster diferente, como se hace en el algoritmo de Lovaina, el algoritmo de Leiden realiza esta verificación solo para los llamados nodos inestables. Como resultado, el algoritmo de Leiden no solo encuentra clústeres de mayor calidad que el algoritmo de Lovaina, sino que también lo hace en mucho menos tiempo.
En CWTS, utilizamos el algoritmo de Leiden para agrupar grandes redes de citas. El algoritmo de Lovaina necesita más de media hora para encontrar grupos en una red de aproximadamente 10 millones de artículos y 200 millones de enlaces de citas. El algoritmo de Leiden necesita solo un poco más de tres minutos para agrupar esta red. Además, cuando se ejecuta repetidamente, el algoritmo de Leiden encuentra fácilmente grupos de mayor calidad que el algoritmo de Lovaina.
¡Inténtalo tú mismo!
Esperamos que el algoritmo de Leiden resulte útil no solo para nosotros en CWTS, sino también para muchos otros investigadores tanto en estudios de ciencias cuantitativos como en ciencias de redes. Durante la última década, miles de investigadores han publicado artículos en los que utilizan el algoritmo de Lovaina. En el futuro, estos investigadores podrían emplear el algoritmo de Leiden.Junto con el documento que presenta el algoritmo de Leiden, también hemos lanzado el código fuente Java del algoritmo en GitHub. Hemos hecho un gran esfuerzo para garantizar que el algoritmo sea fácil de usar para todos. Para los más inclinados técnicamente, hemos creado documentación técnica y comentarios de código. ¡Tome el código fuente, ejecútelo en sus propios datos de red y díganos qué piensa de él!
Nota del administrador: Ahora también está disponible como complemente de Gephi.
No hay comentarios:
Publicar un comentario