An Efficient Evolutionary Algorithm for Diversified Top-k (Weight) Clique Search Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909171155206144 |
|---|---|
| author | Zheng, Jiongzhi Xue, Jinghui He, Kun Li, Chu-Min Liu, Yanli |
| author_facet | Zheng, Jiongzhi Xue, Jinghui He, Kun Li, Chu-Min Liu, Yanli |
| contents | In many real-world problems and applications, finding only a single element, even though the best, among all possible candidates, cannot fully meet the requirements. We may wish to have a collection where each individual is not only outstanding but also distinctive. Diversified Top-k (DTk) problems are a kind of combinatorial optimization problem for finding such a promising collection of multiple sub-structures, such as subgraphs like cliques and social communities. In this paper, we address two representative and practical DTk problems, DTk Clique search (DTkC) and DTk Weight Clique search (DTkWC), and propose an efficient algorithm called Diversified Top-k Evolutionary AlgorithM (DiverTEAM) for these two problems. DiverTEAM consists of a local search algorithm, which focuses on generating high-quality and diverse individuals and sub-structures, and a genetic algorithm that makes individuals work as a team and converge to (near-)optima efficiently. Extensive experiments show that DiverTEAM exhibits an excellent and robust performance across various benchmarks of DTkC and DTkWC. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_09997 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An Efficient Evolutionary Algorithm for Diversified Top-k (Weight) Clique Search Problems Zheng, Jiongzhi Xue, Jinghui He, Kun Li, Chu-Min Liu, Yanli Neural and Evolutionary Computing In many real-world problems and applications, finding only a single element, even though the best, among all possible candidates, cannot fully meet the requirements. We may wish to have a collection where each individual is not only outstanding but also distinctive. Diversified Top-k (DTk) problems are a kind of combinatorial optimization problem for finding such a promising collection of multiple sub-structures, such as subgraphs like cliques and social communities. In this paper, we address two representative and practical DTk problems, DTk Clique search (DTkC) and DTk Weight Clique search (DTkWC), and propose an efficient algorithm called Diversified Top-k Evolutionary AlgorithM (DiverTEAM) for these two problems. DiverTEAM consists of a local search algorithm, which focuses on generating high-quality and diverse individuals and sub-structures, and a genetic algorithm that makes individuals work as a team and converge to (near-)optima efficiently. Extensive experiments show that DiverTEAM exhibits an excellent and robust performance across various benchmarks of DTkC and DTkWC. |
| title | An Efficient Evolutionary Algorithm for Diversified Top-k (Weight) Clique Search Problems |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2404.09997 |