A Hybrid Evolutionary Algorithm for the Diversified Top-k Weight Clique Search Problem (Student Abstract)

Jun Wu, Minghao YinAAAI 2022 · DOI

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:

  1. Population Initialization: A diverse set of initial solutions is generated.
  2. Clique-based Crossover: A novel operator that recombines two parent solutions to produce offspring that inherit high-quality clique structures.
  3. 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.
  4. 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.

Performance comparison of HEA-D against CPLEX and TOPKWCLQ on 102 real-world graphs across different values of k.

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

BibTeX
@inproceedings{wu2022hybrid,
  author = {Jun Wu and Minghao Yin},
  title = {{A Hybrid Evolutionary Algorithm for the Diversified Top-k Weight Clique Search Problem (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i11.21678},
}
Figure