Evolutionary multitasking algorithm based on a dynamic solution encoding strategy for the minimum s-club cover problem

The problem of finding a cohesive subgraph, notably the s-club model, which is a subgraph with diameter at most s, is a widely applied topic in social network analysis and group of objects modeling. In particular, the minimum s-club cover problem (min s-club cover) is a recently introduced variant in the literature which asks to cover the vertices of a graph with a minimum number of s-clubs. The existence of common connections among these highly connected components encourages the application of multitasking optimization to leverage the shared meaningful knowledge in the discovery of multiple s-clubs at the same time. Therefore, this study proposes a multitasking evolutionary algorithm to solve the minimum s-club cover problem. Our proposal is designed with an effective solution representation method and evolutionary operators for the variation in the number of clubs. Each solution is represented by two components, where the gene number of a component can be different for each individual and can change during performing evolutionary operations. We also propose a solution generation method based on a random greedy algorithm that helps to ensure individual quality and population diversity in the initial population. The proposed algorithm is evaluated on two datasets in the DIMACS library. This study then analyzed the influence of different factors of the input data on the proposed algorithm results. Based on statistical analysis of the performance results, it is clear that our proposal’s solution is superior to an existing algorithm on two-thirds of the experimental data set.