GRASP for Modularity Maximization by Density with Signs
Abstract
We focus on a clustering problem in graphs based on maximizing modularity, known as Modularity Density Maximization. In the investigated variation, both positive and negative edges are considered to define node clusters. In this work, we propose a version of the metaheuristic Greedy Randomized Adaptive Search Procedure. The method was able to achieve the best-known objective values in the state-of-the-art.References
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.
Published
2025-07-20
How to Cite
NASCIMENTO, Letícia do; SANTIAGO, Rafael de; FRANCO, Álvaro Junio Pereira; CASTELLUCCI, Pedro Belin.
GRASP for Modularity Maximization by Density with Signs. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
