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). Prior to this work, algorithms for the Cluster Editing problem were assumed to be far from practical. Our multi-parameterized cluster editing algorithm is being used on real data to obtain effective clustering, such as text classification and analysis of ear infection data. We are already witnessing results that are better than those obtained using known classical clustering algorithms. 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.

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. On the Complexity of Multi-Parameterized Cluster Editing, Journal of Discrete Algorithms, volume 45, pages 26-34, 2017.

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.

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, N. Makarem and M. Shehab. An improved fixed-parameter algorithm for 2-club cluster edge deletion, Theoretical Computer Science 958:113864 (2023).