Local search for diversified Top-k clique search problem

被引：16
|
作者：
Wu, Jun [1 ]
Li, Chu-Min [2 ]
Jiang, Lu [1 ]
Zhou, Junping [1 ]
Yin, Minghao [1 ]
机构：
[1] Northeast Normal Univ, Informat Sci & Technol, Changchun, Peoples R China
[2] Univ Picardie Jules Verne, MIS, Amiens, France
来源：
COMPUTERS & OPERATIONS RESEARCH | 2020年 / 116卷 / 116期
基金：
中国国家自然科学基金;
关键词：
Top-k clique search; Local search; Configuration checking; Clique scoring strategy; CONFIGURATION CHECKING;
D O I：
10.1016/j.cor.2019.104867
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
The objective of the diversified top-k clique (DTKC) search problem is to find k maximal cliques that cover the maximum number of vertices in a given graph. This problem is equivalent to the well-known maximum clique problem (MaxClique) when k = 1. This paper proves the NP-hardness of the DTKC search problem and presents a local search algorithm, named TOPKLS, based on two novel strategies for the DTKC search problem. The first strategy is called enhanced configuration checking (ECC), which is a new variant of a recent effective strategy called configuration checking (CC), for reducing cycling in the local search and improving the diversity of the DTKC search problem. The second strategy is a heuristic to estimate the quality of each maximal clique. Experiments demonstrate that TOPKLS outperforms the existing algorithms on large sparse graphs from real-world applications. (C) 2019 Elsevier Ltd. All rights reserved.
引用
收藏
页数：9
相关论文
共 50 条
  • [41] Diversified Late Acceptance Search
    Namazi, Majid
    Sanderson, Conrad
    Newton, M. A. Hakim
    Polash, Md Masbaul Alam
    Sattar, Abdul
    AI 2018: ADVANCES IN ARTIFICIAL INTELLIGENCE, 2018, 11320 : 299 - 311
  • [42] An approximation algorithm for the spherical k-means problem with outliers by local search
    Wang, Yishui
    Wu, Chenchen
    Zhang, Dongmei
    Zou, Juan
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2022, 44 (04) : 2410 - 2422
  • [43] A Local Search Algorithm for the Radius-Constrained k-Median Problem
    Chi, Gaojie
    Guo, Longkun
    Jia, Chaoqi
    THEORY OF COMPUTING SYSTEMS, 2025, 69 (01)
  • [44] An efficient local search algorithm for the maximum k-vertex cover problem
    Li, Ruizhi
    Wang, Fangzhou
    Liu, Siqi
    Xu, Ruiqi
    Yin, Minghao
    Hu, Shuli
    DATA TECHNOLOGIES AND APPLICATIONS, 2025,
  • [45] An approximation algorithm for the spherical k-means problem with outliers by local search
    Yishui Wang
    Chenchen Wu
    Dongmei Zhang
    Juan Zou
    Journal of Combinatorial Optimization, 2022, 44 : 2410 - 2422
  • [46] A Local Search based on Variant Variable Depth Search for the Quadratic Assignment Problem
    Okano, Takeshi
    Katayama, Kengo
    Kanahara, Kazuho
    Nishihara, Noritaka
    2018 IEEE 7TH GLOBAL CONFERENCE ON CONSUMER ELECTRONICS (GCCE 2018), 2018, : 60 - 63
  • [47] A dual-mode local search algorithm for solving the minimum dominating set problem
    Zhu, Enqiang
    Zhang, Yu
    Wang, Shengzhi
    Strash, Darren
    Liu, Chanjuan
    KNOWLEDGE-BASED SYSTEMS, 2024, 298
  • [48] Iterated Local search for the Linear Ordering Problem
    Castilla Valdez, Guadalupe
    Bastiani Medina, Shulamith S.
    INTERNATIONAL JOURNAL OF COMBINATORIAL OPTIMIZATION PROBLEMS AND INFORMATICS, 2012, 3 (01): : 12 - 20
  • [49] On local search for the generalized graph coloring problem
    Vredeveld, T
    Lenstra, JK
    OPERATIONS RESEARCH LETTERS, 2003, 31 (01) : 28 - 34
  • [50] On the quality of local search for the quadratic assignment problem
    Angel, E
    Zissimopoulos, V
    DISCRETE APPLIED MATHEMATICS, 1998, 82 (1-3) : 15 - 25
12345