.png){kind=icon}
.png){kind=icon}
Return
Computing maximum k-defective cliques in massive graphs
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2020.105131.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A k-defective clique (k is a non-negative integer) of an undirected graph G is a subset of its vertices, which induces a nearly complete graph with a maximum of k missing edges. The maximum k-defective clique problem (MDCP) is to determine the k-defective clique of the maximum size in the graph. As a relaxation of the popular maximum clique problem, the MDCP is a relevant model for a number of practical applications such as complex network analysis. However, it is computationally challenging to solve the problem. In this study, we investigate a set of general and dedicated graph reduction and pruning techniques to improve exact search algorithms based on the branch-and-bound framework. We present results of extensive computational experiments on 141 benchmark graphs from several popular sources, including both random graphs and massive real-world networks. Comparisons with two state-of-the-art methods in the literature demonstrate that our approach is on par with the reference methods and performs remarkably well on massive graphs. (C) 2020 Elsevier Ltd. All rights reserved.
Keywords:
Relaxed clique
Exact search
Branch-and-bound
Massive graphs
Graph reduction
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W
Organization
No organization information available