Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem

Alexander Belyi (), Stanislav Sobolevsky (), Alexander Kurbatski () and Carlo Ratti ()
Additional contact information
Alexander Belyi: Masaryk University
Stanislav Sobolevsky: Masaryk University
Alexander Kurbatski: Belarusian State University
Carlo Ratti: Massachusetts Institute of Technology

Mathematical Methods of Operations Research, 2023, vol. 98, issue 2, No 5, 269-297

Abstract: Abstract We consider a variant of the clustering problem for a complete weighted graph. The aim is to partition the nodes into clusters maximizing the sum of the edge weights within the clusters. This problem is known as the clique partitioning problem, being NP-hard in the general case of having edge weights of different signs. We propose a new method of estimating an upper bound of the objective function that we combine with the classical branch-and-bound technique to find the exact solution. We evaluate our approach on a broad range of random graphs and real-world networks. The proposed approach provided tighter upper bounds and achieved significant convergence speed improvements compared to known alternative methods.

Keywords: Clustering; Graphs; Clique partitioning problem; Community detection; Modularity; Upper bounds; Exact solution; Branch and bound; Linear programming; 05C85; 68T09; 68R10; 90C35; 90C90; 91C20 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00186-023-00835-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:98:y:2023:i:2:d:10.1007_s00186-023-00835-y

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-023-00835-y

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().