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

Logo poskytovatele

Varování

Publikace nespadá pod Ekonomicko-správní fakultu, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.
Autoři

BELY Aliaksandr SOBOLEVSKY Stanislav ALEXANDER Kurbatski RATTI Carlo

Rok publikování 2023
Druh Článek v odborném periodiku
Časopis / Zdroj Mathematical Methods of Operations Research
Fakulta / Pracoviště MU

Přírodovědecká fakulta

Citace
www https://link.springer.com/article/10.1007/s00186-023-00835-y
Doi http://dx.doi.org/10.1007/s00186-023-00835-y
Klíčová slova Clustering; Graphs; Clique partitioning problem; Community detection; Modularity; Upper bounds; Exact solution; Branch and bound; Linear programming
Přiložené soubory
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.