Correlation Clustering via Graph Modification

Project Description: We study the effectiveness of the use of multiple parameters when applied to Correlation Clustering (AKA. Cluster Editing). Current work on this topic includes clustering with overlaps, where we allow a data element to belong to more than one cluster, if necessary. Moreover, we do not necessarily transform a graph into a disjoint union of cliques. Instead we perform edge deletion into a disjoint union of s-clubs: graphs of diameter at most s. Promising theoretical and experimental results have been obtained and they are due to appear in the near future. Our multi-parameterized cluster editing algorithm is used in many interdisciplinary projects (on real data) to obtain effective clustering. We are already witnessing results that are better than those obtained using known classical clustering algorithms.

PI: Faisal N. Abu-Khzam

Funding: This project has been partially supported by the Lebanese American University under grant SRDC-t2013-45. It is currently funded by the Presidential Intramural Research Fund (PIRF) at LAU (as of Fall 2023).

Publications:

F. N. Abu-Khzam, E. Arrighi, M. Bentert, P. G. Drange, J. Egan, S. Gaspers, A. Shaw, P. Shaw, B. D. Sullivan and P. Wolf. Cluster Editing with Vertex Splitting, Discrete Applied Mathematics, 2025. Accepted for publication.

F. N. Abu-Khzam, L. Isenmann and S. Thoumi. Correlation Clustering with Overlap: a Heuristic Graph Editing Approach. CoRR abs/2412.02704 (2024).

F. N. Abu-Khzam, N. Makarem and M. Shehab. An improved fixed-parameter algorithm for 2-club cluster edge deletion, Theoretical Computer Science 958:113864 (2023).

Previous publications (from related older projects):

J. R. Barr, P. Shaw, F. N. Abu-Khzam and J. Chen. Combinatorial Text Classification: the effect of multi-parameterized correlation clustering, in Proceedings of the 1st International Conference on Graph Computing (GC), IEEE, 2019: 29-36.

F. N. Abu-Khzam, J. Egan, S. Gaspers, A. Shaw and P. Shaw. Cluster Editing with Vertex Splitting, in Proceedings of the 5th International Symposium on Combinatorial Optimization (ISCO), Lecture Notes in Computer Science, volume 10856, Marrakesh, Morroco, April 2018, pages 1-13.

F. N. Abu-Khzam. On the Complexity of Multi-Parameterized Cluster Editing, Journal of Discrete Algorithms, volume 45, pages 26-34, 2017.