Scalable Multilevel and Memetic Signed Graph Clustering
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929414477971456 |
|---|---|
| author | Hausberger, Felix Faraj, Marcelo Fonseca Schulz, Christian |
| author_facet | Hausberger, Felix Faraj, Marcelo Fonseca Schulz, Christian |
| contents | In this study, we address the complex issue of graph clustering in signed graphs, which are characterized by positive and negative weighted edges representing attraction and repulsion among nodes, respectively. The primary objective is to efficiently partition the graph into clusters, ensuring that nodes within a cluster are closely linked by positive edges while minimizing negative edge connections between them. To tackle this challenge, we first develop a scalable multilevel algorithm based on label propagation and FM local search. Then we develop a memetic algorithm that incorporates a multilevel strategy. This approach meticulously combines elements of evolutionary algorithms with local refinement techniques, aiming to explore the search space more effectively than repeated executions. Our experimental analysis reveals that this our new algorithms significantly outperforms existing state-of-the-art algorithms. For example, our memetic algorithm can reach solution quality of the previous state-of-the-art algorithm up to four orders of magnitude faster. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_13618 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Scalable Multilevel and Memetic Signed Graph Clustering Hausberger, Felix Faraj, Marcelo Fonseca Schulz, Christian Data Structures and Algorithms In this study, we address the complex issue of graph clustering in signed graphs, which are characterized by positive and negative weighted edges representing attraction and repulsion among nodes, respectively. The primary objective is to efficiently partition the graph into clusters, ensuring that nodes within a cluster are closely linked by positive edges while minimizing negative edge connections between them. To tackle this challenge, we first develop a scalable multilevel algorithm based on label propagation and FM local search. Then we develop a memetic algorithm that incorporates a multilevel strategy. This approach meticulously combines elements of evolutionary algorithms with local refinement techniques, aiming to explore the search space more effectively than repeated executions. Our experimental analysis reveals that this our new algorithms significantly outperforms existing state-of-the-art algorithms. For example, our memetic algorithm can reach solution quality of the previous state-of-the-art algorithm up to four orders of magnitude faster. |
| title | Scalable Multilevel and Memetic Signed Graph Clustering |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2208.13618 |