Abstract
The Diversified Top-$k$ Weight Clique (DTKWC) search problem is a complex combinatorial optimization task with significant applications in social network analysis, bioinformatics, and marketing. This paper introduces HEA-D, a hybrid evolutionary algorithm that integrates global evolutionary exploration with simulated annealing-based local refinement. Experimental results on 102 real-world network graphs demonstrate that HEA-D significantly outperforms state-of-the-art solvers like CPLEX and TOPKWCLQ, establishing new performance benchmarks for finding high-value, diverse clusters in complex networks.
Introduction
In graph theory, a clique represents a subset of vertices where every pair is connected by an edge. While the maximum clique problem is well-studied, many practical scenarios require identifying multiple cliques that are both high-value (weighted) and distinct (diversified). The Diversified Top-$k$ Weight Clique (DTKWC) problem addresses this by seeking at most $k$ maximal cliques that maximize the total weight of the covered vertices.
The DTKWC problem is NP-hard, presenting three primary challenges: accounting for vertex weights, ensuring diversity to minimize overlap, and managing computational complexity in large-scale graphs. Applications range from identifying influential communities in social networks to optimizing advertisement placement in media scheduling.
Methodology
To address the DTKWC problem, we propose a dual approach consisting of a formal mathematical model and a specialized heuristic algorithm.
Mixed-Integer Linear Programming (MILP)
We first developed a MILP formulation to provide a rigorous mathematical definition of the DTKWC problem. This framework serves as a baseline for optimality and defines the constraints for selecting $k$ maximal cliques to maximize unique vertex weight coverage.
The HEA-D Algorithm
Given the limitations of exact solvers on large graphs, we developed HEA-D, a memetic algorithm that combines evolutionary strategies with local search. The algorithm follows a structured workflow:
- Population Initialization: A diverse set of initial solutions is generated.
- Clique-based Crossover: A novel operator that recombines two parent solutions to produce offspring that inherit high-quality clique structures.
- Simulated Annealing (SA) Local Optimization: To escape local optima, SA is employed to refine solutions by exploring neighboring configurations, allowing for occasional "downhill" moves to reach better global regions.
- Population Update: The population is iteratively updated to retain the most promising solutions.
Experimental Evaluation
The performance of HEA-D was evaluated using two primary benchmarks:
- Advertisement Placement Graphs: 8 real-world datasets from TV program scheduling.
- Real-World Network Graphs: 102 large-scale graphs from the Network Data Repository, with synthetic weights assigned using a modulo-based formula ($w(v_i) = (i \pmod{200}) + 1$).
By varying the parameter $k$ from 10 to 50, a total of 550 test instances were generated.
Results and Discussion
HEA-D was compared against the exact solver CPLEX and TOPKWCLQ, a leading algorithm for the unweighted version of the problem.
As shown in the table above, HEA-D consistently outperformed or matched the competition across all tested values of $k$. Notably, as the complexity increased (higher $k$), the gap widened. At $k=50$, HEA-D found strictly better solutions in 74 out of 102 instances, while neither CPLEX nor TOPKWCLQ could find a superior solution in any instance within the time limit. Furthermore, HEA-D established new lower bounds for 334 out of the 550 total instances, demonstrating its efficacy in finding high-quality solutions where previous methods failed.
Conclusion
The HEA-D algorithm demonstrates the power of hybridizing global evolutionary search with local simulated annealing for solving the DTKWC problem. By shifting the focus to vertex weights and diversity, the model provides a more realistic framework for economic and biological applications. Future work will focus on testing HEA-D on graphs with naturally occurring weight distributions and improving the scalability of the crossover operator for billion-edge networks.
Summary updated