Research On Solving Algorithms For The Maximum Relaxed Clique Problems

Cohesive subgraphs play a crucial role in various networks due to their distinct subgraph structures.The clique model,as a representative of the classic cohesive subgraphs,has been widely applied in various fields since its proposal.However,with the development of social life,the rigid constraints of the clique model have made it increasingly difficult to adapt to the needs of practical problems.Correspondingly,various relaxed clique models have gradually come into the sight of researchers.By relaxing one or several properties of the clique model,the obtained relaxed clique models often have better applicability than the clique model.Therefore,they have significant implications in domains such as criminal network analysis,epidemic control,network clustering,and biological systems.The research on the relaxed clique models includes many directions,among which the problem of finding the relaxed cliques with the largest size occupies almost all relevant researches on these models.As a typical combinatorial optimization problem,research on the maximum relaxed clique problem mainly focuses on designing various efficient solving algorithms for it.These algorithms can generally be divided into two categories:complete algorithms and incomplete algorithms.Following this research direction,this study mainly focused on four maximum relaxed clique problems of maximum k-plex,maximum y-quasiclique,maximum k-club and maximum k-defective clique problems,and proposed four efficient solving algorithms.The maximum relaxed clique problems studied covered a range of relaxation directions including vertex degree relaxation,graph density relaxation and distance length relaxation.The proposed algorithms also spanned various complete and incomplete algorithms including branch and bound algorithm,local search algorithm,and tabu search algorithm.This research could not only promote the solution of the maximum relaxed clique problems,but also helped researchers better understand the application of different relaxed clique models in social life.Specifically,the research content and contributions of this dissertation can be illustrated in the following four aspects:(1)Abranch and bound algorithm,BnB,was proposed for the maximum k-plex problem.In the BnB algorithm,four graph reduction properties were excavated based on the structural characteristics of k-plex,and corresponding reduction functions were designed.These reduction functions not only assisted in removing redundant vertices during preprocessing,but also helped reduce the number of branches during the search process.Furthermore,a Dynamic Vertex Selection Strategy was designed to guide the direction of the algorithm’s branches.The BnB algorithm not only identified the optimal solutions for 7 instances on the classic benchmark,but also obtained the optimal solutions of 480 instances on the massive real-world benchmark with a total of 556(139×4)instances.It found 111 more optimal solutions in comparison to the state-of-the-art maximum k-plex complete algorithm.(2)A local search algorithm,NuQClq,was proposed for the maximum y-quasi-clique problem.In the NuQClq algorithm,the use of accumulated vertex information was firstly proposed for the vertex selection,and the resulting Cumulative Saturation Heuristic could effectively distinguish candidate vertices with the same benefit value.Additionally,a Bounded Configuration Checking Strategy was designed to control the cycling problem during the search process.Results showed that the proposed NuQClq algorithm obtained 104,34 and 37 better solutions than the other three state-of-the-art maximum y-quasi-clique heuristic algorithms on a total of 289 classic instances.(3)A local search algorithm,NukCP,was proposed for the maximum k-club problem.In the NukCP algorithm,a Dynamic Reduction Strategy was designed to balance time efficiency and upper bound calculation precision.In addition,according to the structural characteristics of k-club,the method of using spanning tree to maintain the solution was proposed for the first time,and based on this,a Stratified Threshold Configuration Checking Strategy was designed to control the cycling problem.Compared to the other three state-of-the-art maximum k-club heuristic algorithms,the Nu k CP algorithm not only demonstrated outstanding solving performance on the classic benchmarks,but also obtained 193 best solutions out of 195(65×3)instances on the massive NDR benchmark.(4)A solution-based tabu search algorithm,CSTDC,was proposed for the maximum kdefective clique problem.In the CSTDC algorithm,a Hybrid Scoring Heuristic was designed to select candidate vertices by combining with the information contained in the vertices.Moreover,a new hash function calculation method and a new constraint were used to improve the traditional solution-based tabu search,leading to the development of the Constrained Solution-based Tabu Search.As the first heuristic algorithm for this problem,the CSTDC algorithm obtained 2947 best solutions out of 2952(492×6)instances on seven benchmarks compared to the state-of-the-art k-defective clique complete algorithm.Furthermore,it also obtained 262 better solutions than another heuristic algorithm which was extended based on a classic clique algorithm.