Improved upper bounds in clique partitioning problem

  • Alexander B. Belyi SMART Centre, 1 Create Way, Singapore 138602, Singapore
  • Stanislav L. Sobolevsky SMART Centre, 1 Create Way, Singapore 138602, Singapore; ITMO University, 49 Kronverksky Avenue, Saint Petersburg 197101, Russia; New York University, 370 Jay Street, New York 11201, USA
  • Alexander N. Kurbatski Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus https://orcid.org/0000-0002-2419-006X
  • Carlo Ratti Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge 02139, USA

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.

Author Biographies

Alexander B. Belyi, SMART Centre, 1 Create Way, Singapore 138602, Singapore

software engineer

Stanislav L. Sobolevsky, SMART Centre, 1 Create Way, Singapore 138602, Singapore; ITMO University, 49 Kronverksky Avenue, Saint Petersburg 197101, Russia; New York University, 370 Jay Street, New York 11201, USA

doctor of science (physics and mathematics); professor at the Institute Design and Urban Science, ITMO University, and associate professor of practice at the Center for Urban Science and Progress, New York University, and researcher, Massachusetts Institute of Technology

Alexander N. Kurbatski, Belarusian State University, 4 Niezaliežnasci Avenue, Minsk 220030, Belarus

doctor of science (engineering), full professor; head of the department of software engineering, faculty of applied mathematics and computer science

Carlo Ratti, Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge 02139, USA

PhD; professor of the practice at the department of urban studies and planning, director of MIT Senseable City Lab

References

  1. 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.
  2. Fortunato S. Community detection in graphs. Physics reports. 2010;486(3–5):75–174. DOI: 10.1016/j.physrep.2009.11.002.
  3. 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.
  4. 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.
  5. 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.
  6. Newman ME, Girvan M. Finding and evaluating community structure in networks. Physical Review E. 2004;69(2):026113. DOI: 10.1103/PhysRevE.69.026113.
  7. 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.
  8. 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.
  9. Wakabayashi Y. Aggregation of binary relations: algorithmic and polyhedral investigations. Augsburg: University of Augsburg; 1986. 191 p.
  10. 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.
  11. Dorndorf U, Pesch E. Fast clustering algorithms. ORSA Journal on Computing. 1994;6(2):141–153. DOI: 10.1287/ijoc.6.2.141.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. 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.
  20. 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.
Published
2019-11-27
Keywords: clique partitioning, branch and bound method, exact solution, upper bounds
Supporting Agencies This research is supported by the National Research Foundation (prime minister’s office, Singapore), under its CREATE programme, Singapore-MIT Alliance for Research and Technology (SMART) Future Urban Mobility (FM) IRG.
How to Cite
Belyi, A. B., Sobolevsky, S. L., Kurbatski, A. N., & Ratti, C. (2019). Improved upper bounds in clique partitioning problem. Journal of the Belarusian State University. Mathematics and Informatics, 3, 93-104. https://doi.org/10.33581/2520-6508-2019-3-93-104
Section
Theoretical Foundations of Computer Science