HP-MOCD: Viabilizando a Detecção de Comunidades Multiobjetivo em Redes de Larga Escala

• Guilherme O. Santos UFOP
• Lucas S. Vieira UFOP
• Carlos H. G. Ferreira UFOP
• Gladston J. P. Moreira UFOP

DOI: https://doi.org/10.5753/brasnam.2026.22901

Resumo

A detecção de comunidades em redes complexas é um problema fundamental, e abordagens cl´assicas de objetivo único, como Louvain e Leiden, embora eficientes, apresentam limitações importantes, incluindo o problema de resolução e a degenerescência da função de modularidade, que podem levar a partições subótimas ou inconsistentes. Nesse contexto, algoritmos evolucionários multiobjetivos (MOEAs) surgem como alternativa promissora, mas, tipicamente, restringem-se a redes com menos de 10.000 nós devido ao elevado custo computacional. Este artigo apresenta e discute o HP-MOCD, um algoritmo multiobjetivo de alto desempenho recentemente proposto na literatura para detecção de comunidades, construído sobre o NSGA-II. O HP-MOCD combina operadores genéticos cientes da topologia, paralelização completa e otimizações em nível de bits, alcançando complexidade O(G·N_p|V|) para grafos esparsos. Resultados experimentais em benchmarks LFR e 14 redes reais mostram que o HP-MOCD é capaz de processar grafos com mais de um milhão de nós, superando MOEAs concorrentes em até 553× em tempo de execução e mantendo qualidade competitiva ou superior nas partições.

Referências

Azevedo, B. F., Rocha, A. M. A. C., Fernandes, F. P., Pacheco, M. F., and Pereira, A. I. (2024). Comparison between single and multi-objective clustering algorithms: Mathe case study. In Optimization, Learning Algorithms and Applications.

Blondel, V. D., Guillaume, J.-L., Lambiotte, R., and Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P10008.

Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., and Hwang, D.-U. (2006). Complex networks: Structure and dynamics. Physics Reports, 424(4):175–308.

Dabaghi-Zarandi, F., Afkhami, M. M., and Ashoori, M. H. (2025). Community detection method based on random walk and multi objective evolutionary algorithm in complex networks. Journal of Network and Computer Applications.

Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). A fast and elitist multi-objective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation, 6(2):182–197.

Fortunato, S. and Barthélemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104.

Moreira, G. and Paquete, L. (2019). Guiding under uniformity measure in the decision space. In 2019 IEEE Latin American Conference on Computational Intelligence (LACCI), pages 1–6.

Newman, M. E. (2006). Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23):8577–8582.

Newman, M. E. and Girvan, M. (2004). Finding and evaluating community structure in networks. Physical review E, 69(2):026113.

Pizzuti, C. (2009). A multi-objective genetic algorithm for community detection in networks. In 21st IEEE International Conference on Tools with Artificial Intelligence, pages 379–386.

Shaik, T., Ravi, V., and Deb, K. (2021). Evolutionary multi-objective optimization algorithm for community detection in complex social networks. SN Computer Science, 2(1):1.

Shi, C., Zhong, C., Yan, Z., Cai, Y., and Wu, B. (2010). A multi-objective approach for community detection in complex network. In IEEE Congress on Evolutionary Computation, pages 1–8.

Traag, V. A., Waltman, L., and van Eck, N. J. (2019). From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports, 9(1):5233.