Abstract
Partitioning a set of graph vertices into two or more subsets constitutes an important class of problems in combinatorial optimization. Two well-known members of this class are the minimum ratio cut and the minimum normalized cut problems. Our focus is on developing metaheuristic-based approaches for ratio cut and normalized cut graph partitioning. We present three techniques in this category: multistart simulated annealing (MSA), iterated tabu search (ITS), and the memetic algorithm (MA). The latter two use a local search procedure. To speed up this procedure, we apply a technique that reduces the effort required for neighborhood examination. We carried out computational experiments on both random graphs and benchmark graphs from the literature. The numerical results indicate that the MA is a clear winner among the tested methods. Using rigorous statistical tests, we show that MA is unequivocally superior to MSA and ITS in terms of both the best and average solution values. Additionally, we compare the performances of MA and the variable neighborhood search (VNS) heuristic from the literature, which is the state-of-the-art algorithm for the normalized cut model. The experimental results demonstrate the superiority of MA over VNS, especially for structured graphs.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aksoylar C, Qian J, Saligrama V (2017) Clustering and community detection with imbalanced clusters. IEEE Trans Signal Inf Process Netw 3(1):61–76
Bader DA, Kappes A, Meyerhenke H, Sanders P, Schulz C, Wagner D (2017) Benchmarking for graph clustering and partitioning. In: Alhajj R, Rokne J (eds) Encyclopedia of social network analysis and mining. Springer, New York. https://doi.org/10.1007/978-1-4939-7131-2_23
Banerjee S, Kayal D (2016) Detection of hard exudates using mean shift and normalized cut method. Biocybern Biomed Eng 36(4):679–685
Bektur G (2020) A multi-start iterated tabu search algorithm for the multi-resource agent bottleneck generalized assignment problem. Int J Optim Control Theor Appl 10(1):37–46
Brimberg J, Mladenović N, Urošević D (2015) Solving the maximally diverse grouping problem by skewed general variable neighborhood search. Inf Sci 295:650–675
Cafieri S, Hansen P, Mladenović N (2014) Edge-ratio network clustering by variable neighborhood search. Eur Phys J B 87:116
Cao B, Glover F, Rego C (2015) A tabu search algorithm for cohesive clustering problems. J Heuristics 21(4):457–477
Černý V (1985) Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J Optim Theory Appl 45(1):41–51
Chalupa D (2017) A memetic algorithm for the minimum conductance graph partitioning problem. arXiv preprint arXiv:1704.02854
Chalupa D, Hawick KA, Walker JA (2018) Hybrid bridge-based memetic algorithms for finding bottlenecks in complex networks. Big Data Res 14:68–80
Chan PK, Schlag MDF, Zien JY (1994) Spectral k-way ratio-cut partitioning and clustering. IEEE Trans Comput Aided Des Integr Circuits Syst 13(9):1088–1096
Chen X, Hong W, Nie F, He D, Yang M, Huang JZ (2018) Spectral clustering of large-scale data by directly solving normalized cut. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining (KDD 2018). ACM, London, pp 1206–1215
Chen X, Hong W, Nie F, Huang JZ, Shen L (2020) Enhanced balanced min cut. Int J Comput Vis 128:1982–1995
Chen X, Huang JZ, Nie F, Chen R, Wu Q (2017) A self-balanced min-cut algorithm for image clustering. In: IEEE international conference on computer vision (ICCV 2017). IEEE, Venice, Italy, pp 2080–2088. https://doi.org/10.1109/ICCV.2017.227
de Sousa VJR, Anjos MF, Le Digabel S (2019) Improving the linear relaxation of maximum k-cut with semidefinite-based constraints. EURO J Comput Optim 7(2):123–151
Dhillon IS, Guan Y, Kulis B (2007) Weighted graph cuts without eigenvectors: a multilevel approach. IEEE Trans Pattern Anal Mach Intell 29(11):1944–1957
Fan N, Pardalos PM (2012) Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs. J Comb Optim 23(2):224–251
Faris H, Aljarah I, Mirjalili S (2018) Improved monarch butterfly optimization for unconstrained global search and neural network training. Appl Intell 48(2):445–464
Feng Y, Deb S, Wang GG, Alavi AH (2021) Monarch butterfly optimization: a comprehensive review. Expert Syst Appl 168:114418
Franzin A, Stützle T (2019) Revisiting simulated annealing: a component-based analysis. Comput Oper Res 104:191–206
Fu K, Gong C, Gu IYH, Yang J (2015) Normalized cut-based saliency detection by adaptive multi-level region merging. IEEE Trans Image Process 24(12):5671–5683
Gallego M, Laguna M, Martí R, Duarte A (2013) Tabu search with strategic oscillation for the maximally diverse grouping problem. J Oper Res Soc 64(5):724–734
Gallier J (2016) Spectral theory of unsigned and signed graphs. Applications to graph clustering: a survey. arXiv preprint arXiv:1601.04692
Glover F, Laguna M (1997) Tabu search. Kluwer Publisher
Hagen L, Kahng AB (1992) New spectral methods for ratio cut partitioning and clustering. IEEE Trans Comput Aided Des 11(9):1074–1085
Han J, Xiong K, Nie F (2017) Orthogonal and nonnegative graph reconstruction for large scale clustering. In: Proceedings of the twenty-sixth international joint conference on artificial intelligence (IJCAI 2017). Melbourne, pp 1809–1815
Hansen P, Ruiz M, Aloise D (2012) A VNS heuristic for escaping local extrema entrapment in normalized cut clustering. Pattern Recognit 45(12):4337–4345
He Y, Gong H, Xiong B, Xu X, Li A, Jiang T, Sun Q, Wang S, Luo Q, Chen S (2015) iCut: an integrative cut algorithm enables accurate segmentation of touching cells. Sci Rep 5:12089. https://doi.org/10.1038/srep12089
Heidari AA, Mirjalili S, Faris H, Aljarah I, Mafarja M, Chen H (2019) Harris hawks optimization: algorithm and applications. Future Gener Comput Syst 97:849–872
Hochbaum DS (2013) A polynomial time algorithm for Rayleigh ratio on discrete variables: replacing spectral techniques for expander ratio, normalized cut, and Cheeger constant. Oper Res 61(1):184–198
James TL, Brown EC, Keeling KB (2007) A hybrid grouping genetic algorithm for the cell formation problem. Comput Oper Res 34(7):2059–2079
Ji P, Zhang S, Zhou Z (2020) A decomposition-based ant colony optimization algorithm for the multi-objective community detection. J Ambient Intell Humaniz Comput 11(1):173–188
Jia H, Ding S, Du M, Xue Y (2016) Approximate normalized cuts without eigen-decomposition. Inf Sci 374:135–150
Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680
Krzystek P, Serebryanyk A, Schnörr C, Červenka J, Heurich M (2020) Large-scale mapping of tree species and dead trees in Šumava national park and Bavarian forest national park using lidar and multispectral imagery. Remote Sens 12:661. https://doi.org/10.3390/rs12040661
Lai X, Hao J-K (2016) Iterated maxima search for the maximally diverse grouping problem. Eur J Oper Res 254(3):780–800
Lai X, Hao J-K, Fu ZH, Yue D (2021) Neighborhood decomposition based variable neighborhood search and tabu search for maximally diverse grouping. Eur J Oper Res 289(3):1067–1086
Li S, Chen H, Wang M, Heidari AA, Mirjalili S (2020) Slime mould algorithm: a new method for stochastic optimization. Future Gener Comput Syst 111:300–323
Liu C, Liu Q (2018) Community detection based on differential evolution using modularity density. Information 9:218. https://doi.org/10.3390/info9090218
Liu X, Shen C, Guan X, Zhou Y (2019) Digger: detect similar groups in heterogeneous social networks. ACM Trans Knowl Discov Data 13(1):2. https://doi.org/10.1145/3267106
Lorente-Leyva LL, Herrera-Granda ID, Rosero-Montalvo PD, Ponce-Guevara KL, Castro-Ospina AE, Becerra MA, Peluffo-Ordóñez DH, Rodríguez-Sotelo JL (2018) Developments on solutions of the normalized-cut-clustering problem without eigenvectors. In: Huang T, Lv J, Sun C, Tuzikov AV (eds) Advances in neural networks-ISNN 2018, vol 10878. Lect Notes Comput Sci. Springer, pp 318–328
Lu H, Fu Z, Shu X (2014) Non-negative and sparse spectral clustering. Pattern Recognit 47(1):418–426
Lu Z, Hao J-K, Wu Q (2020) A hybrid evolutionary algorithm for finding low conductance of large graphs. Future Gener Comput Syst 106:105–120
Lu Z, Hao J-K, Zhou Y (2019) Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem. Comput Oper Resh 111:43–57
Ma L, Cheng S, Shi Y (2021) Enhancing learning efficiency of brain storm optimization via orthogonal learning design. IEEE Trans Syst Man Cybern Syst 51(11):6723–6742
Ma L, Huang M, Yang S, Wang R, Wang X (2021) An adaptive localized decision variable analysis approach to large-scale multiobjective and many-objective optimization. IEEE Trans Cybern. https://doi.org/10.1109/TCYB.2020.3041212
Merkurjev E, Bertozzi A, Yan X, Lerman K (2017) Modified Cheeger and ratio cut methods using the Ginzburg–Landau functional for classification of high-dimensional data. Inverse Probl. https://doi.org/10.1088/1361-6420/33/7/074003
Mu C, Zhang J, Liu Y, Qu R, Huang T (2019) Multi-objective ant colony optimization algorithm based on decomposition for community detection in complex networks. Soft Comput 23(23):12683–12709
Nascimento MCV, de Carvalho ACPLF (2011) Spectral methods for graph clustering—a survey. Eur J Oper Res 211(2):221–231
Nogueira B, Tavares E, Maciel P (2021) Iterated local search with tabu search for the weighted vertex coloring problem. Comput Oper Res 125:105087. https://doi.org/10.1016/j.cor.2020.105087
Palubeckis G, Karčiauskas E, Riškus A (2011) Comparative performance of three metaheuristic approaches for the maximally diverse grouping problem. Inf Technol Control 40(4):277–285
Palubeckis G, Ostreika A, Rubliauskas D (2015) Maximally diverse grouping: an iterated tabu search approach. J Oper Res Soc 66(4):579–592
Qiao Z, Zhang J, Qu X, Xiong J (2020) Dynamic self-organizing leader-follower control in a swarm mobile robots system under limited communication. IEEE Access 8:53850–53856
Ramos-Figueroa O, Quiroz-Castellanos M, Mezura-Montes E, Schütze O (2020) Metaheuristics to solve grouping problems: a review and a case study. Swarm Evol Comput 53:100643
Rodriguez FJ, Lozano M, García-Martínez C, González-Barrera JD (2013) An artificial bee colony algorithm for the maximally diverse grouping problem. Inf Sci 230:183–196
Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. In: Proceedings of the twenty-ninth AAAI conference on artificial intelligence. AAAI Press, Austin, pp 4292–4293
Rutenbar RA (1989) Simulated annealing algorithms: an overview. IEEE Circuits Devices Mag 5(1):19–26
Shi J, Malik J (2000) Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell 22(8):888–905
Shi X, Wu Y, Rao CR (2017) Consistent and powerful graph-based change-point test for high-dimensional data. Proc Natl Acad Sci U S A 114(15):3873–3878
Singh K, Sundar S (2019) A new hybrid genetic algorithm for the maximally diverse grouping problem. Int J Mach Learn Cybern 10(10):2921–2940
Tolić D, Antulov-Fantulin N, Kopriva I (2018) A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering. Pattern Recognit 82:40–55
van Laarhoven PJM (1988) Theoretical and computational aspects of simulated annealing. Erasmus Universiteit Rotterdam, Rotterdam
Van Lierde H, Chow TWS, Chen G (2020) Scalable spectral clustering for overlapping community detection in large-scale networks. IEEE Trans Knowl Data Eng 32(4):754–767
von Luxburg U (2007) A tutorial on spectral clustering. Stat Comput 17(4):395–416
Wang GG (2018) Moth search algorithm: a bio-inspired metaheuristic algorithm for global optimization problems. Memet Comput 10(2):151–164
Wang GG, Deb S, Coelho LS (2015) Elephant herding optimization. In: Proceedings of the 2015 3rd international symposium on computational and business intelligence (ISCBI). IEEE, Bali, pp 1–5. https://doi.org/10.1109/ISCBI.2015.8
Wang GG, Deb S, Coelho LS (2018) Earthworm optimisation algorithm: a bio-inspired metaheuristic algorithm for global optimisation problems. Int J Bio-Inspired Comput 12(1):1–22
Wang L, Lu J (2019) A memetic algorithm with competition for the capacitated green vehicle routing problem. IEEE/CAA J Autom Sin 6(2):516–526
Wei Y-C, Cheng C-K (1991) Ratio cut partitioning for hierarchical designs. IEEE Trans Comput Aided Des Integr Circuits Syst 10(7):911–921
Yu SX, Shi J (2003) Multiclass spectral clustering. In: Proceedings of the ninth IEEE international conference on computer vision (ICCV’03), vol 1. IEEE, Nice, pp 313–319. https://doi.org/10.1109/ICCV.2003.1238361
Zevnik J, Kramar Fijavž M, Kozelj D (2019) Generalized normalized cut and spanning trees for water distribution network partitioning. J Water Resour Plan Manag 145(10):04019041. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001100
Zhang R, Nie F, Li X (2017) Self-weighted spectral clustering with parameter-free constraint. Neurocomputing 241:164–170
Zheng S, Xu Z, Yang H, Song J, Pan Z (2019) Comparisons of different methods for balanced data classification under the discrete non-local total variational framework. Math Found Comput 2(1):11–28
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Palubeckis, G. Metaheuristic approaches for ratio cut and normalized cut graph partitioning. Memetic Comp. 14, 253–285 (2022). https://doi.org/10.1007/s12293-022-00365-w
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12293-022-00365-w