Geodesic
Improved upper bounds in clique partitioning problem
Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2019), pp. 93-104.

Voir la notice de l'article provenant de la source Math-Net.Ru

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
Keywords: clique partitioning; branch and bound method; exact solution; upper bounds. 
@article{BGUMI_2019_3_a7,
     author = {A. B. Belyi and S. L. Sobolevskii and A. N. Kourbatski and C. Ratti},
     title = {Improved upper bounds in clique partitioning problem},
     journal = {Journal of the Belarusian State University. Mathematics and Informatics},
     pages = {93--104},
     publisher = {mathdoc},
     volume = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a7/}
}
TY  - JOUR
AU  - A. B. Belyi
AU  - S. L. Sobolevskii
AU  - A. N. Kourbatski
AU  - C. Ratti
TI  - Improved upper bounds in clique partitioning problem
JO  - Journal of the Belarusian State University. Mathematics and Informatics
PY  - 2019
SP  - 93
EP  - 104
VL  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a7/
LA  - ru
ID  - BGUMI_2019_3_a7
ER  - 
%0 Journal Article
%A A. B. Belyi
%A S. L. Sobolevskii
%A A. N. Kourbatski
%A C. Ratti
%T Improved upper bounds in clique partitioning problem
%J Journal of the Belarusian State University. Mathematics and Informatics
%D 2019
%P 93-104
%V 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a7/
%G ru
%F BGUMI_2019_3_a7
A. B. Belyi; S. L. Sobolevskii; A. N. Kourbatski; C. Ratti. Improved upper bounds in clique partitioning problem. Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2019), pp. 93-104. http://geodesic.mathdoc.fr/item/BGUMI_2019_3_a7/

[1] M. Grotschel, Y. Wakabayashi, “A cutting plane algorithm for a clustering problem”, Mathematical Programming, 45(1–3) (1989), 59–96 | DOI | MR | Zbl

[2] S. Fortunato, “Community detection in graphs”, Physics reports, 486(3–5) (2010), 75–174 | DOI | MR

[3] A. Belyi, I. Bojic, S. Sobolevsky, I. Sitko, B. Hawelka, L. Rudikova, “Global multi-layer network of human mobility”, International Journal of Geographical Information Science, 31(7) (2017), 1381–1402 | DOI

[4] A. Belyi, I. Bojic, S. Sobolevsky, L. Rudikova, A. Kurbatski, C. Ratti, “Community structure of the world revealed by Flickr data”, Tekhnologii informatizatsii i upravleniya. TIM-2016. Materialy III Mezhdunarodnoi nauchno-prakticheskoi konferentsii (Belarus), 2016, 1–9, Grodno: GrGU | MR

[5] S. Sobolevsky, A. Belyi, C. Ratti, “Optimality of community structure in complex networks”, 2017, 17, arXiv: http://dx.doi.org/https://arxiv.org/abs/1712.05110

[6] M. E. Newman, M. Girvan, “Finding and evaluating community structure in networks”, Physical Review E, 69(2) (2004), 26–113 | DOI | MR

[7] M. E. Newman, “Modularity and community structure in networks”, Proceedings of the National Academy of Sciences of the United States of America, 103(23) (2006), 8577–8582 | DOI

[8] M. Rosvall, C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure”, Sciences of the United States of America, 105(4) (2008), 1118–1123 | DOI

[9] Y. Wakabayashi, “Aggregation of binary relations: algorithmic and polyhedral investigations”, Augsburg: University of Augsburg, 1986, 191 | Zbl

[10] Amorim. De, J. P. Barthelemy, C. C. Ribeiro, “Clustering and clique partitioning: simulated annealing and tabu search approaches”, Journal of Classification, 9(1) (1992), 17–41 | DOI | MR

[11] ?. U. Dorndorf, E. Pesch, “Fast clustering algorithms”, ORSA Journal on Computing, 6(2) (1994), 141–153 | DOI | Zbl

[12] I. Charon, O. Hudry, “Noising methods for a clique partitioning problem”, Discrete Applied Mathematics, 154(5) (2006), 754–769 | DOI | MR | Zbl

[13] Y. Zhou, J. K. Hao, A. Goeffon, “A three-phased local search approach for the clique partitioning problem”, Journal of Combinatorial Optimization, 32(2) (2016), 469–491 | DOI | MR | Zbl

[14] J. Brimberg, S. Janicijevic, N. Mladenovic, D. Urosevic, “Solving the clique partitioning problem as a maximally diverse grouping problem”, Optimization Letters, 11(6) (2017), 1123–1135 | DOI | MR | Zbl

[15] S. Sobolevsky, R. Campari, A. Belyi, C. Ratti, “General optimization technique for high-quality community detection in complex networks”, Physical Review E, 90(1) (2014), 012811 | DOI

[16] M. Oosten, JHGC. Rutten, FCR. Spieksma, “The clique partitioning problem: facets and patching facets”, Networks: An International Journal, 38(4) (2001), 209–226 | DOI | MR | Zbl

[17] F. Jaehn, E. Pesch, “New bounds and constraint propagation techniques for the clique partitioning problem”, Discrete Applied Mathematics, 161(13–14) (2013), 2025–2037 | DOI | MR | Zbl

[18] U. Dorndorf, F. Jaehn, E. Pesch, “Modelling robust flight-gate scheduling as a clique partitioning problem”, Transportation Science, 42(3) (2008), 292–301 | DOI

[19] H. Wang, B. Alidaee, F. Glover, G. Kochenberger, “Solving group technology problems via clique partitioning”, International Journal of Flexible Manufacturing Systems, 18(2) (2006), 77–97 | DOI | MR | Zbl

[20] D. Aloise, S. Cafieri, G. Caporossi, P. Hansen, S. Perron, L. Liberti, “Column generation algorithms for exact modularity maximization in networks”, Physical Review E, 82(4) (2010), 046112 | DOI