Saltar al contenido
Volver a los resultados

Detección de Comunidades — Agrupamiento de Grafos en Redes

Propuesto por
Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
Año
2002–2019 (algorithm family)
Tipo
Graph-partitioning / clustering algorithm family

Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés

Tamaño de letra

¿Qué hace?

La detección de comunidades es una familia de algoritmos de partición de grafos que descubren subgrupos densamente conectados —comunidades— dentro de una red.

Formalizado por primera vez mediante la medida de modularidad por Girvan y Newman (2002), el campo avanzó rápidamente con el método de Louvain (Blondel et al., 2008), el refinamiento de Leiden (Traag et al., 2019) y el enfoque de Infomap basado en la teoría de la información. Todas las variantes responden a la misma pregunta: ¿qué nodos se agrupan más estrechamente entre sí que con el resto de la red?

La intuición detrás del método

Imagine una gran red social donde algunas personas hablan principalmente con su círculo inmediato, y solo ocasionalmente se comunican fuera de él. La detección de comunidades encuentra esos círculos automáticamente, sin que usted tenga que etiquetarlos de antemano. El algoritmo reorganiza los nodos en grupos de modo que las conexiones internas sean densas y las conexiones entre grupos sean escasas, maximizando una puntuación de calidad llamada modularidad (o, en Infomap, minimizando la longitud de descripción de un paseo aleatorio a través de la red). El resultado es una partición: cada nodo pertenece exactamente a una comunidad, y usted puede visualizar la red como un conjunto de clústeres cohesivos.

Historia

El estudio de la estructura comunitaria en redes fue establecido sobre una base cuantitativa por Girvan y Newman (2002), quienes introdujeron el concepto de intermediación de aristas como herramienta para la división jerárquica de redes. Newman y Girvan (2004) luego formalizaron la medida de modularidad Q, que se convirtió en el criterio de calidad estándar. Blondel et al. (2008) publicaron el método de Louvain —una optimización codiciosa de dos fases que hizo práctica la detección de comunidades de alta calidad en redes con millones de nodos. Traag, Waltman y van Eck (2019) identificaron un defecto estructural en Louvain —que puede producir comunidades internamente desconectadas— y desarrollaron el algoritmo de Leiden para corregirlo, garantizando particiones bien conectadas. Paralelamente, Rosvall y Bergstrom (2008) desarrollaron Infomap, que replantea la detección de comunidades como un problema de compresión: encontrar la partición que minimice la longitud de descripción de un paseo aleatorio en la red.

Cuándo usarlo

La detección de comunidades es apropiada cuando se tiene una red (mínimo ~20 nodos) y se desea descubrir una estructura de grupo latente sin preespecificar los grupos. Se adapta a objetivos exploratorios, descriptivos y de clasificación en datos de peso de arista binarios o continuos, incluidos datos de red transversales y longitudinales. No requiere atributos de nodo ni distribuciones normales. El método es particularmente adecuado cuando se desconoce el número de comunidades. Si la red es demasiado pequeña (menos de 20 nodos), se prefieren las estadísticas descriptivas de red. Los resultados son sensibles a las definiciones de peso de arista y a la densidad de la red, por lo que esas elecciones merecen una cuidadosa consideración.

Limitaciones y consideraciones

  • La maximización de la modularidad es susceptible a óptimos locales; los resultados pueden variar entre ejecuciones y deben informarse como el mejor de múltiples ejecuciones.
  • El límite de resolución significa que comunidades muy pequeñas en redes grandes pueden fusionarse, enmascarando una estructura de grano fino.
  • Los resultados son sensibles a cómo se definen los pesos de las aristas; diferentes esquemas de ponderación pueden producir particiones significativamente diferentes.
  • Girvan-Newman tiene una complejidad O(m²n) y no es práctico en redes grandes; Louvain o Leiden deben preferirse para la escala.

Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.

Fortalezas

  • No requiere que se especifique de antemano el número de comunidades; el tamaño de la partición lo determinan los datos.
  • Escala a redes grandes: Louvain y Leiden se ejecutan en tiempo casi lineal, lo que los hace prácticos para redes con millones de nodos.
  • Leiden garantiza comunidades bien conectadas e internamente cohesivas, corrigiendo el defecto de comunidades desconectadas de Louvain.
  • Aplicable tanto a redes no ponderadas como ponderadas sin suposiciones distribucionales sobre los datos.

Aplicaciones

  • Identificación de clústeres de investigación en redes de citas y coautoría para mapear campos científicos.
  • Detección de módulos funcionales en redes de interacción proteína-proteína en biología.
  • Encontrar comunidades de usuarios en redes sociales y de comunicación para análisis de comportamiento.
  • Segmentación de redes de clientes en negocios y marketing para revelar grupos de clientes cohesivos.
  • Descubrimiento de bloques estructurales en redes de infraestructura, transporte o cadena de suministro.

Cómo funciona

Cómo funciona

1

La entrada es un grafo cuyos nodos representan entidades (personas, páginas web, proteínas, citas) y cuyos aristas representan relaciones entre ellas. Las aristas pueden ser dirigidas o no dirigidas, y pueden llevar pesos. La estructura de adyacencia —qué nodos están conectados y con qué fuerza— es la única entrada que necesitan los algoritmos. No se requieren etiquetas de nodos, clases o atributos externos, aunque pueden usarse para validar los resultados posteriormente.

2

Cada algoritmo comienza con una asignación inicial de nodos a comunidades. En Louvain y Leiden, cada nodo comienza como su propia comunidad singleton. Girvan-Newman comienza con la red completa y elimina iterativamente la arista con la mayor centralidad de intermediación, revelando progresivamente la estructura comunitaria. Infomap parte de una descripción de paseo aleatorio de la red y la codifica utilizando un mapa de dos niveles para minimizar la longitud del código.

3

La fase central busca una partición que maximice la modularidad Q (Louvain, Leiden) o minimice la longitud del código de la ecuación del mapa (Infomap). Louvain mueve codiciosamente nodos individuales entre comunidades para mejorar Q, luego agrega comunidades en supernodos y repite —un proceso de dos fases que escala bien pero puede producir comunidades desconectadas. Leiden refina Louvain garantizando que cada comunidad esté internamente conectada, utilizando un paso de movimiento local y refinamiento antes de la agregación. Girvan-Newman elimina aristas iterativamente y registra el dendrograma de divisiones; se selecciona la partición que maximiza Q en cualquier corte del dendrograma. El número de comunidades surge del propio algoritmo; no necesita especificarse de antemano.

4

La calidad de la partición final se resume mediante la puntuación de modularidad Q, que oscila entre -0.5 y 1. Los valores superiores a ~0.3-0.5 generalmente se consideran indicativos de una estructura comunitaria significativa. Debido a que la optimización de la modularidad puede quedar atrapada en óptimos locales, ejecutar el algoritmo varias veces y tomar el mejor resultado es una práctica estándar. La partición también se inspecciona visualmente y se valida de forma cruzada con cualquier atributo de nodo o etiquetas de verdad fundamental disponibles para confirmar que es sustantivamente significativa.

Errores comunes

  • Ejecutar el algoritmo una vez y tratar el único resultado como verdad fundamental —siempre ejecute varias veces e informe la mejor modularidad o use métodos de conjunto.
  • Ignorar el límite de resolución: en redes grandes y dispersas, comunidades pequeñas pero reales pueden ser absorbidas por otras más grandes sin previo aviso.
  • Aplicar algoritmos basados en modularidad a redes con menos de 20 nodos —la estructura comunitaria no puede identificarse de manera fiable a esa escala.
  • Confundir una puntuación de modularidad alta con una estructura comunitaria confirmada en el mundo real; la modularidad es una medida de calidad de la partición, no una prueba inferencial de si las comunidades son estadísticamente significativas.

Preguntas frecuentes

¿Qué algoritmo debo elegir: Louvain, Leiden, Girvan-Newman o Infomap?

Louvain es una línea base rápida y ampliamente utilizada para redes grandes. Leiden es la opción preferida cuando la corrección es importante, ya que garantiza comunidades internamente conectadas y generalmente logra una modularidad más alta. Girvan-Newman produce un dendrograma útil para la exploración jerárquica, pero es demasiado lento para redes grandes. Infomap es adecuado para redes dirigidas o basadas en flujo donde la trayectoria de un caminante aleatorio es significativa.

¿Necesito especificar el número de comunidades de antemano?

No. Louvain, Leiden e Infomap determinan el número de comunidades automáticamente a partir de la estructura de la red. Girvan-Newman produce un dendrograma completo del cual se puede leer cualquier número de comunidades; generalmente se selecciona la partición que maximiza Q.

¿Cómo sé si las comunidades encontradas son significativas?

La puntuación de modularidad Q proporciona una medida de calidad interna de los datos; valores superiores a aproximadamente 0.3-0.5 sugieren una estructura comunitaria no trivial. Más allá de eso, las comunidades deben validarse con el conocimiento del dominio, los atributos de los nodos o las etiquetas externas. Una Q alta por sí sola no prueba la significancia sociológica o biológica.

¿Qué sucede si los resultados difieren entre ejecuciones?

La optimización de la modularidad es una heurística y diferentes ejecuciones pueden producir particiones ligeramente diferentes, especialmente en Louvain. Ejecute el algoritmo varias veces (al menos 10-100 ejecuciones en redes grandes) e informe la partición con la Q más alta. Leiden es más estable que Louvain porque su paso de refinamiento es más exhaustivo, pero las ejecuciones repetidas siguen siendo una buena práctica.

Métodos relacionados

Fuentes

  1. Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.

    Abrir referencia DOI
    Copiado.
  2. Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.

    Abrir referencia de la publicación
    Copiado.