Correlation Clustering with Overlaps

LAUR Repository

Show simple item record

dc.contributor.author Fakhereldine, Amin
dc.date.accessioned 2022-04-05T11:34:13Z
dc.date.available 2022-04-05T11:34:13Z
dc.date.copyright 2020 en_US
dc.date.issued 2020-05-27
dc.identifier.uri http://hdl.handle.net/10725/13449
dc.description.abstract 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. en_US
dc.language.iso en en_US
dc.subject Cluster analysis -- Computer programs en_US
dc.subject Cluster analysis -- Mathematical models en_US
dc.subject Lebanese American University -- Dissertations en_US
dc.subject Dissertations, Academic en_US
dc.subject Algorithms en_US
dc.subject Computer science -- Mathematics en_US
dc.title Correlation Clustering with Overlaps en_US
dc.type Thesis en_US
dc.title.subtitle A Multi-parameterized Approach en_US
dc.term.submitted Spring en_US
dc.author.degree MS in Computer Science en_US
dc.author.school SAS en_US
dc.author.idnumber 201706566 en_US
dc.author.commembers Mansour, Nashat
dc.author.commembers Haraty, Ramzi
dc.author.department Computer Science And Mathematics en_US
dc.description.physdesc 1 online resource (x, 42 leaves); col. ill. en_US
dc.author.advisor Abu-Khzam, Faisal
dc.keywords Correlation Clustering en_US
dc.keywords Cluster Editing en_US
dc.keywords Fixed-parameter Tractability en_US
dc.keywords Clustering with Overlaps en_US
dc.keywords Vertex Splitting en_US
dc.description.bibliographiccitations Bibliography: leaf 38-42. en_US
dc.identifier.doi https://doi.org/10.26756/th.2022.332
dc.author.email amin.fakhereldine@lau.edu en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php en_US
dc.publisher.institution Lebanese American University en_US
dc.author.affiliation Lebanese American University en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account