Improved upper bounds in clique partitioning problem
Abstract
In this work, a problem of partitioning a complete weighted graph into cliques in such a way that sum of edge weights between vertices belonging to the same clique is maximal is considered. This problem is known as a clique partitioning problem. It arises in many applications and is a varian of classical clustering problem. However, since the problem, as well as many other combinatorial optimization problems, is NP-hard, finding its exact solution often appears hard. In this work, a new method for constructing upper bounds of partition quality function values is proposed, and it is shown how to use these upper bounds in branch and bound technique for finding an exact solution. Proposed method is based on the usage of triangles constraining maximal possible quality of partition. Novelty of the method lies in possibility of using triangles overlapping by edges, which allows to find much tighter bounds than when using only non-overlapping subgraphs. Apart from constructing initial estimate, a method of its recalculation, when fixing edges on each step of branch and bound method, is described. Test results of proposed algorithm on generated sets of random graphs are provided. It is shown, that version that uses new bounds works several times faster than previously known methods.
References
- Grötschel M, Wakabayashi Y. A cutting plane algorithm for a clustering problem. Mathematical Programming. Series B. 1989; 45(1–3):59 – 96. DOI: 10.1007/BF01589097.
- Fortunato S. Community detection in graphs. Physics reports. 2010;486(3–5):75–174. DOI: 10.1016/j.physrep.2009.11.002.
- Belyi A, Bojic I, Sobolevsky S, Sitko I, Hawelka B, Rudikova L, et al. Global multi-layer network of human mobility. International Journal of Geographical Information Science. 2017;31(7):1381–1402. DOI: 10.1080/13658816.2017.1301455.
- Belyi A, Bojic I, Sobolevsky S, Rudikova L, Kurbatski A, Ratti C. Community structure of the world revealed by Flickr data. In: Tekhnologii informatizatsii i upravleniya. TIM-2016. Materialy III Mezhdunarodnoi nauchno-prakticheskoi konferentsii; 14 –15 aprelya 2016 g.; Grodno, Belarus’ [Technologies of Information and Management TIM-2016. Materials of the 3rd International science and training conference; 2016 April 14 –15; Grodno, Belarus]. Grodno: Yanka Kupala State University of Grodno; 2016. p. 1– 9.
- Sobolevsky S, Belyi A, Ratti C. Optimality of community structure in complex networks. arXiv:1712.05110 [Preprint]. 2017 [cited 2019 March 22]: [17 p.]. Available from: https://arxiv.org/abs/1712.05110.
- Newman ME, Girvan M. Finding and evaluating community structure in networks. Physical Review E. 2004;69(2):026113. DOI: 10.1103/PhysRevE.69.026113.
- Newman ME. Modularity and community structure in networks. Proceedings of the National Academy of Sciences of the United States of America. 2006;103(23):8577–8582. DOI: 10.1073/pnas.0601602103.
- Rosvall M, Bergstrom CT. Maps of random walks on complex networks reveal community structure. Sciences of the United States of America. 2008;105(4):1118 –1123. DOI: 10.1073/pnas.0706851105.
- Wakabayashi Y. Aggregation of binary relations: algorithmic and polyhedral investigations. Augsburg: University of Augsburg; 1986. 191 p.
- De Amorim SG, Barthélemy JP, Ribeiro CC. Clustering and clique partitioning: simulated annealing and tabu search approaches. Journal of Classification. 1992;9(1):17– 41. DOI: 10.1007/BF02618466.
- Dorndorf U, Pesch E. Fast clustering algorithms. ORSA Journal on Computing. 1994;6(2):141–153. DOI: 10.1287/ijoc.6.2.141.
- Charon I, Hudry O. Noising methods for a clique partitioning problem. Discrete Applied Mathematics. 2006;154(5):754 –769. DOI: 10.1016/j.dam.2005.05.029.
- Zhou Y, Hao JK, Goëffon A. A three-phased local search approach for the clique partitioning problem. Journal of Combinatorial Optimization. 2016;32(2):469 – 491. DOI: 10.1007/s10878-015-9964-9.
- Brimberg J, Janićijević S, Mladenović N, Urošević D. Solving the clique partitioning problem as a maximally diverse grouping problem. Optimization Letters. 2017;11(6):1123–1135. DOI: 10.1007/s11590-015-0869-4.
- Sobolevsky S, Campari R, Belyi A, Ratti C. General optimization technique for high-quality community detection in complex networks. Physical Review E. 2014;90(1):012811. DOI: 10.1103/PhysRevE.90.012811.
- Oosten M, Rutten JHGC, Spieksma FCR. The clique partitioning problem: facets and patching facets. Networks: An International Journal. 2001;38(4):209 –226. DOI: 10.1002/net.10004.
- Jaehn F, Pesch E. New bounds and constraint propagation techniques for the clique partitioning problem. Discrete Applied Mathematics. 2013;161(13–14):2025–2037. DOI: 10.1016/j.dam.2013.02.011.
- Dorndorf U, Jaehn F, Pesch E. Modelling robust flight-gate scheduling as a clique partitioning problem. Transportation Science. 2008;42(3):292–301. DOI: 10.1287/trsc.1070.0211.
- Wang H, Alidaee B, Glover F, Kochenberger G. Solving group technology problems via clique partitioning. International Journal of Flexible Manufacturing Systems. 2006;18(2):77–97. DOI: 10.1007/s10696-006-9011-3.
- Aloise D, Cafieri S, Caporossi G, Hansen P, Perron S, Liberti L. Column generation algorithms for exact modularity maximization in networks. Physical Review E. 2010;82(4):046112. DOI: 10.1103/PhysRevE.82.046112.
Copyright (c) 2019 Journal of the Belarusian State University. Mathematics and Informatics
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The authors who are published in this journal agree to the following:
- The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
- The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
- The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)