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

Jun Wu and Minghao Yin
Additional contact information
Jun Wu: Information Science and Technology, Northeast Normal University, Changchun 130117, China
Minghao Yin: Information Science and Technology, Northeast Normal University, Changchun 130117, China

Mathematics, 2021, vol. 9, issue 21, 1-17

Abstract: 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 k 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.

Keywords: CPLEX; DTKWC; local search; MILP; scoring strategy (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/21/2674/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/21/2674/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:21:p:2674-:d:662009

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().