Ascent-descent variable neighborhood decomposition search for community detection by modularity maximization. (English) Zbl 1411.90272

Summary: In this paper we propose a new variant of the variable neighborhood decomposition search (VNDS) heuristic for solving global optimization problems. We call it Ascent-Descent VNDS since it performs “boundary effect”, or local search step, even if the improvement in solving the subproblem has not been obtained. We apply it in detecting communities in large networks by modularity maximization, the criterion which is, despite of some recent criticism, most widely used. Computational analysis is performed on 22 instances from the 10th DIMACS Implementation Challenge. On 13 instances where optimal solutions were not known, we got the improved best known solutions on 9 instances and on 4 instances the solution was equal to the best known. Thus, the proposed new heuristic outperforms the current state-of-the-art algorithms from the literature.


90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming


Full Text: DOI


[1] Aloise, D.; Cafieri, S.; Caporossi, G.; Hansen, P.; Perron, S.; Liberti, L., Column generation algorithms for exact modularity maximization in networks, Physical Review E, 82, 046-112, (2010)
[2] Aloise, D.; Caporossi, G.; Hansen, P.; Liberti, L.; Perron, S.; Ruiz, M., Modularity maximization in networks by variable neighborhood search, Graph Partitioning and Graph Clustering, 588, 113-127, (2013) · Zbl 1276.90055
[3] Alpert, CJ., Yao, SZ. (1995). Spectral partitioning: the more eigenvectors, the better. In Proceedings of the 32nd annual ACM/IEEE design automation conference ( pp. 195-200). ACM
[4] Bader, D. A., Meyerhenke, H., Sanders, P., & Wagner, D. (Eds.). (2013). Graph partitioning and graph clustering - 10th DIMACS implementation challenge, contemporary mathematics (Vol. 588). Boston: AMS. · Zbl 1262.05001
[5] Barber, MJ; Clark, JW, Detecting network communities by propagating labels under constraints, Physical Review E, 80, 026-129, (2009)
[6] Blondel, VD; Guillaume, JL; Lambiotte, R., Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment, 10, p10008, (2008)
[7] Boccaletti, S.; Ivanchenko, M.; Latora, V.; Pluchino, A.; Rapisarda, A., Detecting complex network modularity by dynamical clustering, Physical Review E, 75, 045-102, (2007)
[8] Brandes, U.; Delling, D.; Gaertler, M.; Gorke, R.; Hoefer, M.; Nikoloski, Z.; Wagner, D., On modularity clustering, IEEE Transactions on Knowledge and Data Engineering, 20, 172-188, (2008)
[9] Cafieri, S.; Hansen, P.; Liberti, L., Edge ratio and community structure in networks, Physical Review E, 81, 026-105, (2010)
[10] Cafieri, S.; Costa, A.; Hansen, P., Reformulation of a model for hierarchical divisive graph modularity maximization, Annals of Operations Research, 222, 213-226, (2014) · Zbl 1303.90111
[11] Cafieri, S.; Hansen, P.; Mladenović, N., Edge-ratio network clustering by variable neighborhood search, The, European Physical Journal B, 87, 1-7, (2014)
[12] Carrizosa, E., Mladenovic, N., Todosijevic, R. (2011). Sum-of-squares clustering on networks. Yugoslav Journal of Operations Research ISSN: 0354-0243 EISSN:2334-6043 21(2) · Zbl 1289.90242
[13] Carrizosa, E.; Mladenović, N.; Todosijević, R., Variable neighborhood search for minimum sum-of-squares clustering on networks, European Journal of Operational Research, 230, 356-363, (2013) · Zbl 1317.91061
[14] Dinh, TN; Thai, MT, Toward optimal community detection: From trees to general weighted networks, Internet Mathematics, 11, 181-200, (2015)
[15] Djidjev, HN. (2006). A scalable multilevel algorithm for graph clustering and community structure detection. In International workshop on algorithms and models for the web-graph (pp. 117-128) Springer · Zbl 1142.68453
[16] Duch, J.; Arenas, A., Community detection in complex networks using extremal optimization, Physical review E, 72, 027-104, (2005)
[17] Fortunato, S.; Barthelemy, M., Resolution limit in community detection, Proceedings of the National Academy of Sciences, 104, 36-41, (2007)
[18] Girvan, M.; Newman, ME, Community structure in social and biological networks, Proceedings of the National Academy of Sciences, 99, 7821-7826, (2002) · Zbl 1032.91716
[19] Goldschmidt, O., & Hochbaum, D. S. (1988). Polynomial algorithm for the k-cut problem. In 29th annual symposium on foundations of computer science (pp. 444-451). IEEE.
[20] Hanafi, S.; Lazić, J.; Mladenović, N.; Wilbaut, C.; Crevits, I., New variable neighbourhood search based 0-1 mip heuristics, Yugoslav Journal of Operations Research, 25, 343-360, (2015) · Zbl 1474.90301
[21] Hansen, P.; Mladenović, N.; Perez-Britos, D., Variable neighborhood decomposition search, Journal of Heuristics, 7, 335-350, (2001) · Zbl 1041.68623
[22] Hansen, P.; Mladenović, N.; Pérez, JAM, Variable neighbourhood search: Methods and applications, 4OR, 6, 319-360, (2008) · Zbl 1179.90332
[23] Hansen, P.; Ruiz, M.; Aloise, D., A vns heuristic for escaping local extrema entrapment in normalized cut clustering, Pattern Recognition, 45, 4337-4345, (2012)
[24] Hansen, P., Mladenović, N., Todosijević, R., & Hanafi, S. (2016). Variable neighborhood search: basics and variants. EURO Journal on Computational Optimization. doi:10.1007/s13675-016-0075-x.
[25] Kehagias, A.; Pitsoulis, L., Bad communities with high modularity, The European Physical Journal B, 86, 1-11, (2013)
[26] Kirkpatrick, S.; Gelatt, CD; Vecchi, MP; etal., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[27] Liu, X.; Murata, T., Advanced modularity-specialized label propagation algorithm for detecting communities in networks, Physica A: Statistical Mechanics and its Applications, 389, 1493-1500, (2010)
[28] Lou, H.; Li, S.; Zhao, Y., Detecting community structure using label propagation with weighted coherent neighborhood propinquity, Physica A: Statistical Mechanics and its Applications, 392, 3095-3105, (2013)
[29] Medus, A.; Acuna, G.; Dorso, C., Detection of community structures in networks via global optimization, Physica A: Statistical Mechanics and its Applications, 358, 593-604, (2005)
[30] Miyauchi, A.; Sukegawa, N., Redundant constraints in the standard formulation for the clique partitioning problem, Optimization Letters, 9, 199-207, (2015) · Zbl 1316.90057
[31] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers and Operations Research, 24, 1097-1100, (1997) · Zbl 0889.90119
[32] Nascimento, MC; Pitsoulis, L., Community detection by modularity maximization using grasp with path relinking, Computers and Operations Research, 40, 3121-3131, (2013) · Zbl 1348.91237
[33] Newman, ME, Modularity and community structure in networks, Proceedings of the National Academy of Sciences, 103, 8577-8582, (2006)
[34] Newman, ME, Modularity and community structure in networks, Proceedings of the National Academy of Sciences, 103, 8577-8582, (2006)
[35] Newman, ME; Girvan, M., Finding and evaluating community structure in networks, Physical review E, 69, 026-113, (2004)
[36] Niu, YQ; Hu, BQ; Zhang, W.; Wang, M., Detecting the community structure in complex networks based on quantum mechanics, Physica A: Statistical Mechanics and Its Applications, 387, 6215-6224, (2008)
[37] Ovelgönne, M.; Geyer-Schulz, A., An ensemble learning strategy for graph clustering, Graph Partitioning and Graph Clustering, 588, 187, (2012) · Zbl 1269.05104
[38] Raghavan, UN; Albert, R.; Kumara, S., Near linear time algorithm to detect community structures in large-scale networks, Physical Review E, 76, 036-106, (2007)
[39] Reichardt, J.; Bornholdt, S., Statistical mechanics of community detection, Physical Review E, 74, 016-110, (2006)
[40] Shi, J.; Malik, J., Normalized cuts and image segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, 22, 888-905, (2000)
[41] Sobolevsky, S.; Campari, R.; Belyi, A.; Ratti, C., General optimization technique for high-quality community detection in complex networks, Physical Review E, 90, 012-811, (2014)
[42] Su, J., Havens, TC. (2014). Fuzzy community detection in social networks using a genetic algortihm. In 2014 IEEE international conference on fuzzy systems (FUZZ-IEEE) (pp. 2039-2046). IEEE
[43] Sun, PG, Community detection by fuzzy clustering, Physica A: Statistical Mechanics and its Applications, 419, 408-416, (2015)
[44] Watts, DJ; Strogatz, SH, Collective dynamics of small-world networks, Nature, 393, 440-442, (1998) · Zbl 1368.05139
[45] Wu, P.; Pan, L., Multi-objective community detection based on memetic algorithm, PloS one, 10, e0126845, (2015)
[46] Zhang, H.; Chen, X.; Li, J.; Zhou, B., Fuzzy community detection via modularity guided membership-degree propagation, Pattern Recognition Letters, 70, 66-72, (2016)
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.