Correlation Clustering with Overlaps
The Cluster Editing problem asks for transforming a given graph into a disjoint union of cliques by applying a minimal number of edge-editing operations. The allowed operations include addition of non-existing edges and deletion of existing ones. We study a multi-parameterized version of the problem...
Saved in:
| Main Author: | |
|---|---|
| Format: | masterThesis |
| Published: |
2020
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10725/13449 https://doi.org/10.26756/th.2022.332 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_ | 1864513490712002560 |
|---|---|
| author | Fakhereldine, Amin |
| author_facet | Fakhereldine, Amin |
| author_role | author |
| dc.creator.none.fl_str_mv | Fakhereldine, Amin |
| dc.date.none.fl_str_mv | 2020 2020-05-27 2022-04-05T11:34:13Z 2022-04-05T11:34:13Z |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/13449 https://doi.org/10.26756/th.2022.332 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 -- Computer programs Cluster analysis -- Mathematical models Lebanese American University -- Dissertations Dissertations, Academic Algorithms Computer science -- Mathematics |
| dc.title.none.fl_str_mv | Correlation Clustering with Overlaps A Multi-parameterized Approach |
| dc.type.none.fl_str_mv | Thesis info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/masterThesis |
| description | The Cluster Editing problem asks for transforming a given graph into a disjoint union of cliques by applying a minimal number of edge-editing operations. The allowed operations include addition of non-existing edges and deletion of existing ones. We study a multi-parameterized version of the problem that limits the global number of allowed edge editing operations in the graph and the local amounts of the edge edits performed per vertex. Moreover, we allow the new vertex splitting operation, which allows the resulting clusters to overlap. In other words, data elements (or vertices) will be allowed to be members in more than one cluster instead of limiting them to only one single cluster, as in classical clustering methods. We present a heuristic algorithm and a semi-exact algorithm for the Multi-Parameterized Cluster Editing with Vertex Splitting problem. In our experimental analysis, we study the efficiency of our algorithms as well as the effectiveness of allowing vertex splitting. In particular, we show that allowing vertex splitting yields higher clustering accuracy and higher intra-cluster similarity. |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | LAURepo_0ff34b84c61dc4d47cc00e83adcab566 |
| 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/13449 |
| publishDate | 2020 |
| publisher.none.fl_str_mv | Lebanese American University |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | Correlation Clustering with OverlapsA Multi-parameterized ApproachFakhereldine, AminCluster analysis -- Computer programsCluster analysis -- Mathematical modelsLebanese American University -- DissertationsDissertations, AcademicAlgorithmsComputer science -- MathematicsThe Cluster Editing problem asks for transforming a given graph into a disjoint union of cliques by applying a minimal number of edge-editing operations. The allowed operations include addition of non-existing edges and deletion of existing ones. We study a multi-parameterized version of the problem that limits the global number of allowed edge editing operations in the graph and the local amounts of the edge edits performed per vertex. Moreover, we allow the new vertex splitting operation, which allows the resulting clusters to overlap. In other words, data elements (or vertices) will be allowed to be members in more than one cluster instead of limiting them to only one single cluster, as in classical clustering methods. We present a heuristic algorithm and a semi-exact algorithm for the Multi-Parameterized Cluster Editing with Vertex Splitting problem. In our experimental analysis, we study the efficiency of our algorithms as well as the effectiveness of allowing vertex splitting. In particular, we show that allowing vertex splitting yields higher clustering accuracy and higher intra-cluster similarity.1 online resource (x, 42 leaves); col. ill.Bibliography: leaf 38-42.Lebanese American University2022-04-05T11:34:13Z2022-04-05T11:34:13Z20202020-05-27Thesisinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/masterThesishttp://hdl.handle.net/10725/13449https://doi.org/10.26756/th.2022.332http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.phpeninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/134492022-07-14T06:05:18Z |
| spellingShingle | Correlation Clustering with Overlaps Fakhereldine, Amin Cluster analysis -- Computer programs Cluster analysis -- Mathematical models Lebanese American University -- Dissertations Dissertations, Academic Algorithms Computer science -- Mathematics |
| status_str | publishedVersion |
| title | Correlation Clustering with Overlaps |
| title_full | Correlation Clustering with Overlaps |
| title_fullStr | Correlation Clustering with Overlaps |
| title_full_unstemmed | Correlation Clustering with Overlaps |
| title_short | Correlation Clustering with Overlaps |
| title_sort | Correlation Clustering with Overlaps |
| topic | Cluster analysis -- Computer programs Cluster analysis -- Mathematical models Lebanese American University -- Dissertations Dissertations, Academic Algorithms Computer science -- Mathematics |
| url | http://hdl.handle.net/10725/13449 https://doi.org/10.26756/th.2022.332 http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php |