GRASP para Maximização da Modularidade por Densidade com Sinais
Resumo
Este trabalho lida com uma versão de problema de agrupamento em grafos baseada na maximização da modularidade, chamada de problema da Maximização da Modularidade por Densidade. Na variação tratada, são consideradas arestas positivas e negativas para agrupar vértices. Para este problema, é proposto o uso da metaheurística Greedy Randomized Adaptive Search Procedure. O método proposto atinge os melhores valores objetivo conhecidos no estado da arte.Referências
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.
Brandes, U. (2008). On Modularity Clustering. IEEE Transactions on Knowledge and Data Engineering, 20(2):172–188.
Clauset, A., Newman, M. E. J., and Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70(6):066111.
de Santiago, R. and Lamb, L. C. (2020). Exact signed modularity density maximization solutions and their real meaning. In 2020 IEEE Congress on Evolutionary Computation (CEC), pages 1–7.
Feo, T. A. and Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133.
Fortunato, S. and Barthélemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences of the United States of America, 104(1):36–41.
Guimerà, R., Mossa, S., Turtschi, A., and Amaral, L. A. N. (2005). The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles. Proceedings of the National Academy of Sciences, 102(22):7794–7799.
Kropivnik, S. and Mrvar, A. (1996). An analysis of the slovene parliamentary parties network. Developments in Statistics and Methodology, Metodološki zvezki, 12:209–216.
Leskovec, J., Huttenlocher, D., and Kleinberg, J. (2010). Signed networks in social media. In Proceedings of the 28th international conference on Human factors in computing systems - CHI ’10, page 1361, New York, New York, USA. ACM Press.
Li, Y., Liu, J., and Liu, C. (2014). A comparative analysis of evolutionary and memetic algorithms for community detection from signed social networks. Soft Computing, 18(2):329–348.
Li, Z., Zhang, S., Wang, R.-S., Zhang, X.-S., and Chen, L. (2008). Quantitative function for community detection. Physical Review E, 77(3):036109.
Meunier, D., Fonlupt, P., Saive, A.-L., Plailly, J., Ravel, N., and Royet, J.-P. (2014). Modular structure of functional networks in olfactory memory. NeuroImage, pages 264–75.
Nepusz, T., Yu, H., and Paccanaro, A. (2012). Detecting overlapping protein complexes in protein-protein interaction networks. Nature Methods, 9(5):471–472.
Newman, M. and Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2):026113.
Read, K. E. (1964). Cultures of the central highlands, new guinea. Southwestern Journal of Anthropology, 10.
Schmeja, S. (2011). Identifying star clusters in a field: a comparison of different algorithms. Astronomische Nachrichten, 332(2):172–184.
Brandes, U. (2008). On Modularity Clustering. IEEE Transactions on Knowledge and Data Engineering, 20(2):172–188.
Clauset, A., Newman, M. E. J., and Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70(6):066111.
de Santiago, R. and Lamb, L. C. (2020). Exact signed modularity density maximization solutions and their real meaning. In 2020 IEEE Congress on Evolutionary Computation (CEC), pages 1–7.
Feo, T. A. and Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6:109–133.
Fortunato, S. and Barthélemy, M. (2007). Resolution limit in community detection. Proceedings of the National Academy of Sciences of the United States of America, 104(1):36–41.
Guimerà, R., Mossa, S., Turtschi, A., and Amaral, L. A. N. (2005). The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles. Proceedings of the National Academy of Sciences, 102(22):7794–7799.
Kropivnik, S. and Mrvar, A. (1996). An analysis of the slovene parliamentary parties network. Developments in Statistics and Methodology, Metodološki zvezki, 12:209–216.
Leskovec, J., Huttenlocher, D., and Kleinberg, J. (2010). Signed networks in social media. In Proceedings of the 28th international conference on Human factors in computing systems - CHI ’10, page 1361, New York, New York, USA. ACM Press.
Li, Y., Liu, J., and Liu, C. (2014). A comparative analysis of evolutionary and memetic algorithms for community detection from signed social networks. Soft Computing, 18(2):329–348.
Li, Z., Zhang, S., Wang, R.-S., Zhang, X.-S., and Chen, L. (2008). Quantitative function for community detection. Physical Review E, 77(3):036109.
Meunier, D., Fonlupt, P., Saive, A.-L., Plailly, J., Ravel, N., and Royet, J.-P. (2014). Modular structure of functional networks in olfactory memory. NeuroImage, pages 264–75.
Nepusz, T., Yu, H., and Paccanaro, A. (2012). Detecting overlapping protein complexes in protein-protein interaction networks. Nature Methods, 9(5):471–472.
Newman, M. and Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2):026113.
Read, K. E. (1964). Cultures of the central highlands, new guinea. Southwestern Journal of Anthropology, 10.
Schmeja, S. (2011). Identifying star clusters in a field: a comparison of different algorithms. Astronomische Nachrichten, 332(2):172–184.
Publicado
20/07/2025
Como Citar
NASCIMENTO, Letícia do; SANTIAGO, Rafael de; FRANCO, Álvaro Junio Pereira; CASTELLUCCI, Pedro Belin.
GRASP para Maximização da Modularidade por Densidade com Sinais. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 6-10.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.7165.
