Detección de Comunidades

La detección de comunidades es la tarea de identificar, dentro de una red o grafo, grupos de nodos densamente conectados entre sí y con conexiones más escasas hacia el resto. Esos grupos —llamados comunidades, clústeres o módulos— revelan la estructura interna de la red: los círculos de amistad en una red social, los módulos funcionales en una red de proteínas.

La modularidad

La medida más usada para evaluar una división en comunidades es la modularidad, introducida por Mark Newman y Michelle Girvan en 2004. Compara cuántas aristas caen dentro de las comunidades frente a las que cabría esperar en una red aleatoria con los mismos grados. Un valor alto indica una estructura de comunidades marcada; un valor cercano a cero, que la división no mejora al azar. Muchos algoritmos se limitan, de hecho, a maximizar la modularidad.

Los algoritmos

Hay varias familias. El método de Girvan-Newman (2002) va eliminando las aristas más «transitadas» —las de mayor intermediación— para ir separando comunidades. El método de Louvain (Blondel y colaboradores, 2008) optimiza la modularidad de forma voraz y es muy rápido, lo que lo hizo popular para redes enormes. El método de Leiden (Traag y colaboradores, 2019) lo mejora garantizando que las comunidades queden bien conectadas. Y la propagación de etiquetas deja que cada nodo adopte la etiqueta mayoritaria de sus vecinos hasta alcanzar un consenso, en tiempo casi lineal.

Los retos

La tarea tiene dificultades conocidas. La optimización de la modularidad sufre un límite de resolución —demostrado por Santo Fortunato y Marc Barthélemy en 2007—: por debajo de cierta escala, tiende a fundir comunidades pequeñas y bien definidas en otras mayores. Además, en muchas redes reales las comunidades se solapan —un nodo pertenece a varias— y elegir cuántas comunidades hay no siempre es obvio.

Su relación con la IA

Hoy la detección de comunidades se apoya cada vez más en el aprendizaje automático. Las redes neuronales de grafos (Graph Neural Networks) abordan la tarea aprendiendo primero representaciones vectoriales de los nodos y agrupándolas después, con líneas de trabajo específicas para el caso de comunidades solapadas. Es un campo de investigación activo, con aplicaciones en biología, redes sociales y sistemas de recomendación. Documentación: documentación científica de comunidades; artículo original de DMoN.