Exact computational solution of modularity density maximization by effective column generation. (English) Zbl 1391.90617

Summary: Modularity density maximization (MDM) is associated with clustering problems in networks. MDM is an alternative to the resolution limit issue of the modularity maximization problem. Several reports in the literature have described mathematical programming models for MDM which solve instances of at most 40 nodes. In this context, this paper presents six new column generation methods that find exact solutions for the MDM problem. These methods use exact and auxiliary heuristic problems and an initial variable generator. Our methods show clear improvements over current results. Comparisons between our proposed methods and state-of-the-art algorithms are also carried out. Our results show that (i) two of our methods surpass the exact state-of-the-art algorithms in terms of time, and (ii) our methods provide optimal values for larger instances than current approaches can tackle.


90C35 Programming involving graphs or networks
05C82 Small world graphs, complex networks (graph-theoretic aspects)
90B10 Deterministic network models in operations research
Full Text: DOI


[1] Agarwal, G.; Kempe, D., Modularity-maximizing graph communities via mathematical programming, Eur. Phys. J. B, 66, 3, 409-418, (2008) · Zbl 1188.90262
[2] Aloise, D.; Cafieri, S.; Caporossi, G.; Hansen, P.; Perron, S.; Liberti, L., Column generation algorithms for exact modularity maximization in networks, Phys. Rev. E, 82, 4, 046112, (2010)
[3] Aloise, D.; Caporossi, G.; Hansen, P.; Liberti, L.; Perron, S.; Ruiz, M., Modularity maximization in networks by variable neighborhood search, (Bader, D. A.; Meyerhenke, H.; Sanders, P.; Wagner, D., Contemporary Mathematics, 588, (2013)) · Zbl 1276.90055
[4] Batagelj, V., Mrvar, A., 2006. Pajek datasets. http://vlado.fmf.uni-lj.si/pub/networks/data/> (accessed 01.05.15) · Zbl 1054.68564
[5] Blondel, V. D.; Guillaume, J.-L.; Lambiotte, R.; Lefebvre, E., Fast unfolding of communities in large networks, J. Stat. Mech., 2008, 10, P10008, (2008)
[6] Brandes, U.; Delling, D.; Gaertler, M.; Gorke, R.; Hoefer, M.; Nikoloski, Z.; Wagner, D., On modularity clustering, IEEE Trans. Knowl. Data Eng., 20, 2, 172-188, (2008)
[7] Clauset, A.; Newman, M. E.J.; Moore, C., Finding community structure in very large networks, Phys. Rev. E, 70, 6, (2004)
[8] Costa, A., MILP formulations for the modularity density maximization problem, Eur. J. Oper. Res., 245, 1, 14-21, (2015) · Zbl 1346.05266
[9] Costa, A.; Kushnarev, S.; Liberti, L.; Sun, Z., Divisive heuristic for modularity density maximization, Comput. Oper. Res., 71, 100-109, (2016) · Zbl 1349.90850
[10] Dantzig, G. B.; Wolfe, P., Decomposition principle for linear programs, Oper. Res., 8, 1, 101-111, (1960) · Zbl 0093.32806
[11] Djidjev, H. N.; Onus, M., Scalable and accurate graph clustering and community structure detection, IEEE Trans. Parallel Distrib. Syst., 24, 5, 1022-1029, (2013)
[12] Ferrara, E.; De Meo, P.; Catanese, S.; Fiumara, G., Detecting criminal organizations in mobile phone networks, Expert Syst. Appl., 41, 13, 5733-5750, (2014)
[13] Fortunato, S.; Barthélemy, M., Resolution limit in community detection, Proc. Natl. Acad. Sci. U.S.A., 104, 1, 36-41, (2007)
[14] Fortunato, S.; Castellano, C., Community structure in graphs, (Meyers, R. A., Computational Complexity: Theory, Techniques, and Applications, (2012), Springer New York New York, NY), 490-512
[15] Gong, M.; Cai, Q.; Li, Y.; Ma, J., An improved memetic algorithm for community detection in complex networks, 2012 IEEE Congress on Evolutionary Computation, 1-8, (2012), IEEE Brisbane, QLD
[16] Guimera, R.; Amaral, L., Functional cartography of complex metabolic networks, Nature, 433, February, 895-900, (2005)
[17] IBM, IBM ILOG CPLEX optimization studio V12.6.3 documentation, (2015), IBM
[18] Karimi-Majd, A.-M.; Fathian, M.; Amiri, B., A hybrid artificial immune network for detecting communities in complex networks, Computing, 97, 5, 483-507, (2014) · Zbl 1358.91085
[19] Kernighan, B. W.; Lin, S., An efficient heuristic procedure for partitioning graphs, Bell Syst. Tech. J., 49, 2, 291-307, (1970) · Zbl 0333.05001
[20] Krzakala, F.; Moore, C.; Mossel, E.; Neeman, J.; Sly, A.; Zdeborová, L.; Zhang, P., Spectral redemption in clustering sparse networks, Proc. Natl. Acad. Sci. U.S.A., 110, 52, (2013) · Zbl 1359.62252
[21] Li, Y.; Liu, J.; Liu, C., A comparative analysis of evolutionary and memetic algorithms for community detection from signed social networks, Soft Comput., 18, 2, 329-348, (2014)
[22] Li, Z.; Zhang, S.; Wang, R.-S.; Zhang, X.-S.; Chen, L., Quantitative function for community detection, Phys. Rev. E, 77, 3, 036109, (2008)
[23] Liu, J.; Zeng, J., Community detection based on modularity density and genetic algorithm, Proceedings - International Conference on Computational Aspects of Social Networks, CASoN’10, 29-32, (2010)
[24] Meunier, D.; Fonlupt, P.; Saive, A.-L.; Plailly, J.; Ravel, N.; Royet, J.-P., Modular structure of functional networks in olfactory memory, Neuroimage, 95, 264-275, (2014)
[25] Nascimento, M. C.; Pitsoulis, L., Community detection by modularity maximization using GRASP with path relinking, Comput. Oper. Res., 40, 12, 3121-3131, (2013) · Zbl 1348.91237
[26] Nash, S. G., Encyclopedia of operations research and management science, (2013), Springer US Boston, MA
[27] Nepusz, T.; Yu, H.; Paccanaro, A., Detecting overlapping protein complexes in protein-protein interaction networks, Nat. Methods, 9, 471-472, (2012)
[28] Newman, M., The structure and function of networks, Comput. Phys. Commun., 147, 1-2, 40-45, (2002) · Zbl 1001.68931
[29] Newman, M., 2013. Spectral community detection in sparse networks. arXiv preprint arXiv:1308.6494. https://arxiv.org/abs/1308.6494v1
[30] Newman, M.; Girvan, M., Finding and evaluating community structure in networks, Phys. Rev. E, 69, 2, 026113, (2004)
[31] Radicchi, F.; Castellano, C.; Cecconi, F.; Loreto, V.; Parisi, D., Defining and identifying communities in networks, Proc. Natl. Acad. Sci. U.S.A., 101, 9, 2658-2663, (2004)
[32] Rotta, R.; Noack, A., Multilevel local search algorithms for modularity clustering, J. Exp. Algorithmics, 16, 2, 2.1, (2011) · Zbl 1284.05309
[33] Schmeja, S., Identifying star clusters in a field: a comparison of different algorithms, Astronomische Nachrichten, 332, 2, 172-184, (2011)
[34] Xie, J.; Kelley, S.; Szymanski, B. K., Overlapping community detection in networks, ACM Comput. Surv., 45, 4, 1-35, (2013) · Zbl 1288.68191
[35] Xu, G.; Tsoka, S.; Papageorgiou, L. G., Finding community structures in complex networks using mixed integer optimisation, Eur. Phys. J. B, 60, 231-239, (2007) · Zbl 1189.90027
[36] Yang, S.; Luo, S., Quantitative measure for community detection in weighted networks, Mod. Phys. Lett. B, 23, 27, 3209-3224, (2009) · Zbl 1184.05117
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.