A Restart Local Search for Solving Diversified Top-k Weight Clique Search Problem

Diversified top-k weight clique (DTKWC) search problem is an important generalization of the diversified top-k clique (DTKC) search problem with practical applications. The diversified top-k weight clique search problem aims to search ...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Jun Wu, Minghao Yin
Formato:	article
Lenguaje:	EN
Publicado:	MDPI AG 2021
Materias:	CPLEX DTKWC local search MILP scoring strategy Mathematics QA1-939
Acceso en línea:	https://doaj.org/article/65a2700f3e004a41b157ebf270590db4
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:65a2700f3e004a41b157ebf270590db4
record_format	dspace
spelling	oai:doaj.org-article:65a2700f3e004a41b157ebf270590db42021-11-11T18:14:34ZA Restart Local Search for Solving Diversified Top-<i>k</i> Weight Clique Search Problem10.3390/math92126742227-7390https://doaj.org/article/65a2700f3e004a41b157ebf270590db42021-10-01T00:00:00Zhttps://www.mdpi.com/2227-7390/9/21/2674https://doaj.org/toc/2227-7390Diversified top-<i>k</i> weight clique (DTKWC) search problem is an important generalization of the diversified top-<i>k</i> clique (DTKC) search problem with practical applications. The diversified top-<i>k</i> weight clique search problem aims to search <i>k</i> maximal cliques that can cover the maximum weight in a vertex weighted graph. In this work, we propose a novel local search algorithm called TOPKWCLQ for the DTKWC search problem which mainly includes two strategies. First, a restart strategy is adopted, which repeated the construction and updating processes of the maximal weight clique set. Second, a scoring heuristic is designed by giving different priorities for maximal weight cliques in candidate set. Meanwhile, a constraint model of the DTKWC search problem is constructed such that the research concerns can be evaluated. Experimental results show that the proposed algorithm TOPKWCLQ outperforms than the comparison algorithm on large-scale real-world graphs.Jun WuMinghao YinMDPI AGarticleCPLEXDTKWClocal searchMILPscoring strategyMathematicsQA1-939ENMathematics, Vol 9, Iss 2674, p 2674 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	CPLEX DTKWC local search MILP scoring strategy Mathematics QA1-939
spellingShingle	CPLEX DTKWC local search MILP scoring strategy Mathematics QA1-939 Jun Wu Minghao Yin A Restart Local Search for Solving Diversified Top-<i>k</i> Weight Clique Search Problem
description	Diversified top-<i>k</i> weight clique (DTKWC) search problem is an important generalization of the diversified top-<i>k</i> clique (DTKC) search problem with practical applications. The diversified top-<i>k</i> weight clique search problem aims to search <i>k</i> maximal cliques that can cover the maximum weight in a vertex weighted graph. In this work, we propose a novel local search algorithm called TOPKWCLQ for the DTKWC search problem which mainly includes two strategies. First, a restart strategy is adopted, which repeated the construction and updating processes of the maximal weight clique set. Second, a scoring heuristic is designed by giving different priorities for maximal weight cliques in candidate set. Meanwhile, a constraint model of the DTKWC search problem is constructed such that the research concerns can be evaluated. Experimental results show that the proposed algorithm TOPKWCLQ outperforms than the comparison algorithm on large-scale real-world graphs.
format	article
author	Jun Wu Minghao Yin
author_facet	Jun Wu Minghao Yin
author_sort	Jun Wu
title	A Restart Local Search for Solving Diversified Top-<i>k</i> Weight Clique Search Problem
title_short	A Restart Local Search for Solving Diversified Top-<i>k</i> Weight Clique Search Problem
title_full	A Restart Local Search for Solving Diversified Top-<i>k</i> Weight Clique Search Problem
title_fullStr	A Restart Local Search for Solving Diversified Top-<i>k</i> Weight Clique Search Problem
title_full_unstemmed	A Restart Local Search for Solving Diversified Top-<i>k</i> Weight Clique Search Problem
title_sort	restart local search for solving diversified top-<i>k</i> weight clique search problem
publisher	MDPI AG
publishDate	2021
url	https://doaj.org/article/65a2700f3e004a41b157ebf270590db4
work_keys_str_mv	AT junwu arestartlocalsearchforsolvingdiversifiedtopikiweightcliquesearchproblem AT minghaoyin arestartlocalsearchforsolvingdiversifiedtopikiweightcliquesearchproblem AT junwu restartlocalsearchforsolvingdiversifiedtopikiweightcliquesearchproblem AT minghaoyin restartlocalsearchforsolvingdiversifiedtopikiweightcliquesearchproblem
_version_	1718431889051615232

A Restart Local Search for Solving Diversified Top-<i>k</i> Weight Clique Search Problem

Ejemplares similares