HP-MOCD: Um Algoritmo Evolucionário Multiobjetivo de Alto Desempenho para Detecção de Comunidades em Redes Complexas
DOI:
https://doi.org/10.5753/reic.2026.8488Keywords:
Detecção de Comunidades, Algoritmos Evolucionários Multiobjetivo, NSGA-II, Redes Complexas, Computação de Alto DesempenhoAbstract
A detecção de comunidades em redes complexas é fundamental para domínios sociais, biológicos e tecnológicos. Heurísticas tradicionais de objetivo único, como Louvain e Leiden, são eficientes, porém sofrem com viés de resolução e degenerescência estrutural. Algoritmos evolucionários multiobjetivos (MOEAs) contornam tais limitações otimizando critérios conflitantes em conjunto, mas seus altos custos restringem sua aplicação a redes pequenas. Este trabalho apresenta o HP-MOCD, um MOEA de alto desempenho baseado no NSGA-II, que combina operadores genéticos cientes da topologia, paralelização completa e otimizações em nível de bits, com complexidade O(G · Np |V |). Experimentos em redes sintéticas e reais demonstram superioridade em diversos cenários e forte escalabilidade: o algoritmo processa grafos com mais de um milhão de nós e supera MOEAs concorrentes em até 553× no tempo de execução. O algoritmo é disponibilizado como biblioteca Python de código aberto.
Downloads
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. DOI: 10.1088/1742-5468/2008/10/P10008.
Coello, C. A. C., Lamont, G. B., and Veldhuizen, D. A. V. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems. Last edition.
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 multiobjective genetic algorithm: Nsga-ii. IEEE Transactions on Evolutionary Computation, 6(2):182–197. DOI: 10.1109/4235.996017.
Ehrgott, M. (2005). Multicriteria Optimization, volume 491 of Lecture Notes in Economics and Mathematical Systems. Springer, Berlin, Heidelberg, 2nd edition.
Fortunato, S. and Barthélemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1). DOI: 10.1073/pnas.0605965104.
Fu, J. and Wang, Y. (2024). An improved continuous-encoding-based multiobjective evolutionary algorithm for community detection in complex networks. IEEE Transactions on Artificial Intelligence, 5(11):5815–5827.
Ghoshal, A. K., Das, N., Bhattacharjee, S., and Chakraborty, G. (2019). A fast parallel genetic algorithm based approach for community detection in large networks. In COMSNETS, pages 95–101.
Ghoshal, A. K., Das, N., and Das, S. (2021). Disjoint and overlapping community detection in small-world networks leveraging mean path length. IEEE Transactions on Computational Social Systems, 9(2):406–418.
Lancichinetti, A., Fortunato, S., and Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Phys. Rev. E, 78:046110. DOI: 10.1103/PhysRevE.78.046110.
Liu, B., Wang, D., and Gao, J. (2024). A multi-objective community detection algorithm with a learning-based strategy. International Journal of Computational Intelligence Systems, 17(1):311.
Moreira, G. and Paquete, L. (2019). Guiding under uniformity measure in the decision space. In 2019 IEEE Latin American Conference on Computational Intelligence (LA-CCI), pages 1–6. DOI: 10.1109/LA-CCI47412.2019.9037034.
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. DOI: 10.1109/ICTAI.2009.58.
Radicchi, F., Castellano, C., Cecconi, F., Loreto, V., and Parisi, D. (2004). Defining and identifying communities in networks. Proceedings of the National Academy of Sciences, 101(9):2658–2663. DOI: 10.1073/pnas.0400054101.
Raghavan, U. N., Albert, R., and Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 76(3):036106.
Santos, G. O., Vieira, L. S., Rossetti, G., Ferreira, C. H. G., and Moreira, G. J. P. (2025). A high-performance evolutionary multiobjective community detection algorithm. Social Network Analysis and Mining, 15(1):110. DOI: 10.1007/s13278-025-01519-7.
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. DOI: 10.1109/CEC.2010.5585987.
Traag, V. A., Waltman, L., and van Eck, N. J. (2019). From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports, 9(1):5233. DOI: 10.1038/s41598-019-41695-z.
Vinh, N. X., Epps, J., and Bailey, J. (2009). Information theoretic measures for clusterings comparison: is a correction for chance necessary? In Proceedings of the 26th annual international conference on machine learning, pages 1073–1080.
Vinh, N. X., Epps, J., and Bailey, J. (2010). Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. Journal of Machine Learning Research, 11:2837–2854.
Yang, J. and Leskovec, J. (2012). Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD workshop on mining data semantics, pages 1–8.
Yusupov, J., Palakonda, V., Mallipeddi, R., and Veluvolu, K. C. (2021). Multi-objective evolutionary algorithm based on ensemble of initializations for overlapping community detection. In International Conference on Electronics, Information, and Communication (ICEIC), pages 1–7.
Downloads
Published
Como Citar
Issue
Section
Licença
Copyright (c) 2026 Os autores
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
