Abstract
The Diversified Top-$k$ Weight Clique (DTKWC) problem is a critical challenge in graph theory with applications ranging from social network analysis to bioinformatics. This paper introduces HEA-D, a hybrid evolutionary algorithm that combines a specialized clique-based crossover operator with simulated annealing-based local search. HEA-D demonstrates exceptional performance, finding the best-known solutions for all 550 tested instances and establishing new lower bounds for 334 large-scale real-world graphs. Notably, HEA-D often operates one to three orders of magnitude faster than existing state-of-the-art solvers.
Introduction
In graph theory, a clique is a subset of vertices where every vertex is connected to every other vertex. While the Maximum Weight Clique Problem (MWCP) focuses on finding a single optimal clique, many practical applications—such as motif discovery or community detection—require finding multiple high-quality solutions that are sufficiently distinct.
This requirement defines the Diversified Top-$k$ Weight Clique (DTKWC) problem. The objective is to identify $k$ maximal cliques that collectively maximize the total weight of the vertices they cover. Because this problem is NP-hard, exact solvers like CPLEX often struggle as graph size increases. HEA-D addresses these limitations through a robust heuristic framework designed for both solution quality and computational efficiency.
Methodology: The HEA-D Framework
HEA-D is built upon two primary algorithmic pillars designed to balance global exploration with local refinement:
1. Clique-based Crossover and "Private Weight"
Traditional evolutionary algorithms often use generic crossover operators that may disrupt the structural integrity of a solution. HEA-D employs a "clique-aware" crossover. When generating offspring from two parent solutions, the algorithm evaluates cliques based on their private weight—the weight of vertices covered uniquely by a specific clique and no others in the set.
This focus on unique coverage ensures that the population evolves toward sets of cliques that are both high-weight and diverse, preventing the algorithm from converging on redundant solutions.
2. Simulated Annealing-based Local Optimization (SALO)
To refine offspring, HEA-D utilizes SALO to explore a restricted neighborhood. Instead of performing vertex-level swaps, SALO attempts to replace entire cliques within the current solution with higher-weight maximal cliques from the graph. The simulated annealing component allows the algorithm to occasionally accept inferior moves, providing a mechanism to escape local optima.
Experimental Evaluation
The algorithm was rigorously tested against 550 instances derived from two major benchmarks:
- Advertisement Putting Benchmark: Small-scale instances with known optimal solutions.
- Weighted Real-World Large Graph Benchmark: 102 large-scale graphs where $k$ was varied from 1 to 50.
Key Results and Performance
HEA-D outperformed existing state-of-the-art methods, including TOPKWCLQ and the exact solver CPLEX, across several dimensions:
- Solution Quality: HEA-D identified the best-known solutions for every single instance. It established 334 new lower bounds for large-scale instances where previous records were surpassed.
- Computational Efficiency: The algorithm demonstrated significant speed advantages. On many instances, HEA-D was 10 to 1,000 times faster than its closest competitors.
- Scalability: While CPLEX could only prove optimality for 19 out of 510 real-world instances within the time limit, HEA-D consistently provided superior coverage in a fraction of the time, highlighting its suitability for massive real-world datasets.
Conclusion
HEA-D represents a significant advancement in solving the DTKWC problem. By prioritizing "private weight" during crossover and utilizing high-level clique swaps in local search, the algorithm achieves a superior balance of diversity and weight coverage. Future research may adapt the HEA-D framework to other diversified subgraph problems, such as finding top-$k$ $k$-plexes or $k$-cores in complex networks.
Summary updated