Correlation Clustering via s-Club Cluster Edge Deletion
Cluster Editing, a known model for correlation clustering, has garnered significant consideration in the parameterized complexity area and has been utilized in a range of practical contexts. In certain situations, the requirement for clusters to be cliques was deemed excessively stringent, leading t...
Saved in:
| Main Author: | |
|---|---|
| Format: | masterThesis |
| Published: |
2023
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10725/15136 https://doi.org/10.26756/th.2023.621 http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513470046666752 |
|---|---|
| author | Makarem, Norma |
| author_facet | Makarem, Norma |
| author_role | author |
| dc.creator.none.fl_str_mv | Makarem, Norma |
| dc.date.none.fl_str_mv | 2023-10-24T09:18:21Z 2023-10-24T09:18:21Z 2023 2023-05-19 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/15136 https://doi.org/10.26756/th.2023.621 http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Lebanese American University |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Cluster analysis -- Data processing Cluster analysis -- Mathematical models Computational complexity Computer algorithms Lebanese American University -- Dissertations Lebanese American University -- Dissertations |
| dc.title.none.fl_str_mv | Correlation Clustering via s-Club Cluster Edge Deletion Theory and Experiments |
| dc.type.none.fl_str_mv | Thesis info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/masterThesis |
| description | Cluster Editing, a known model for correlation clustering, has garnered significant consideration in the parameterized complexity area and has been utilized in a range of practical contexts. In certain situations, the requirement for clusters to be cliques was deemed excessively stringent, leading to the proposal of alternative relaxed clique models for dense subgraphs, such as s-club. In this work, we implement three approaches to tackle the 2-club clustering via edge deletion: a heuristic approach based on the influence of the edge to resolve maximum conflicts, a parameterized algorithm in which by deleting a maximum of k edges, the graph can be transformed into a 2-club cluster based on a branching algorithm, and the approach in Integer Linear Programming to find the optimized solution in an integer formulation. We run these algorithms and cross-compare the three experiment results to the fastest Cluster Editing algorithm which runs in O(1.62k) time. Our 2-club Cluster Edge Deletion approach showed better performance than Cluster Editing in terms of running time, and significantly less cost of modifications while preserving the information of the underlying structure. Finally, we consider the 3-clubs Cluster Edge Deletion which did not have much focus in the literature. The problem can be solved in time O(4k). We present a first fixed-parameter algorithm that breaks this 4k barrier by solving the problem in O(3.65k) time. In addition, we implement this 3CCED algorithm in the heuristic approach and compare the experiments to Cluster Editing and 2CCED. The results show that the 3-club Cluster Edge Deletion presents the highest performance in terms of running time and cost of modifications to reach the desired results. This shows that deletion into a graph whose components are of bounded diameter can be a better model for correlation clustering. |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | LAURepo_33f5a24a89d5ca77cf6fe9fb9354370a |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/15136 |
| publishDate | 2023 |
| publisher.none.fl_str_mv | Lebanese American University |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Correlation Clustering via s-Club Cluster Edge DeletionTheory and ExperimentsMakarem, NormaCluster analysis -- Data processingCluster analysis -- Mathematical modelsComputational complexityComputer algorithmsLebanese American University -- DissertationsLebanese American University -- DissertationsCluster Editing, a known model for correlation clustering, has garnered significant consideration in the parameterized complexity area and has been utilized in a range of practical contexts. In certain situations, the requirement for clusters to be cliques was deemed excessively stringent, leading to the proposal of alternative relaxed clique models for dense subgraphs, such as s-club. In this work, we implement three approaches to tackle the 2-club clustering via edge deletion: a heuristic approach based on the influence of the edge to resolve maximum conflicts, a parameterized algorithm in which by deleting a maximum of k edges, the graph can be transformed into a 2-club cluster based on a branching algorithm, and the approach in Integer Linear Programming to find the optimized solution in an integer formulation. We run these algorithms and cross-compare the three experiment results to the fastest Cluster Editing algorithm which runs in O(1.62k) time. Our 2-club Cluster Edge Deletion approach showed better performance than Cluster Editing in terms of running time, and significantly less cost of modifications while preserving the information of the underlying structure. Finally, we consider the 3-clubs Cluster Edge Deletion which did not have much focus in the literature. The problem can be solved in time O(4k). We present a first fixed-parameter algorithm that breaks this 4k barrier by solving the problem in O(3.65k) time. In addition, we implement this 3CCED algorithm in the heuristic approach and compare the experiments to Cluster Editing and 2CCED. The results show that the 3-club Cluster Edge Deletion presents the highest performance in terms of running time and cost of modifications to reach the desired results. This shows that deletion into a graph whose components are of bounded diameter can be a better model for correlation clustering.1 online resource (xi, 46 leaves)Bibliography: leaves 41-46.Lebanese American University2023-10-24T09:18:21Z2023-10-24T09:18:21Z20232023-05-19Thesisinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/masterThesishttp://hdl.handle.net/10725/15136https://doi.org/10.26756/th.2023.621http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.phpeninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/151362023-11-08T09:40:37Z |
| spellingShingle | Correlation Clustering via s-Club Cluster Edge Deletion Makarem, Norma Cluster analysis -- Data processing Cluster analysis -- Mathematical models Computational complexity Computer algorithms Lebanese American University -- Dissertations Lebanese American University -- Dissertations |
| status_str | publishedVersion |
| title | Correlation Clustering via s-Club Cluster Edge Deletion |
| title_full | Correlation Clustering via s-Club Cluster Edge Deletion |
| title_fullStr | Correlation Clustering via s-Club Cluster Edge Deletion |
| title_full_unstemmed | Correlation Clustering via s-Club Cluster Edge Deletion |
| title_short | Correlation Clustering via s-Club Cluster Edge Deletion |
| title_sort | Correlation Clustering via s-Club Cluster Edge Deletion |
| topic | Cluster analysis -- Data processing Cluster analysis -- Mathematical models Computational complexity Computer algorithms Lebanese American University -- Dissertations Lebanese American University -- Dissertations |
| url | http://hdl.handle.net/10725/15136 https://doi.org/10.26756/th.2023.621 http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php |