| The problem of finding cohesive groups is an important combinatorial optimization problem,including the maximum clique problem,maximum weight clique problem and the maximum -plex problem,which has been extensively studied in the field of social analysis,computer vision and coding theory.Among them,the maximum clique problem is one of the classical cohesive subgraph problems,which is equivalent to the maximum independent set problem or the minimum vertex cover problem.These three problems are all classical NP-hard problems,that is,when P ≠ NP,there is no polynomial time algorithm for them.However,in practical applications,finding only one optimal solution or enumerating all feasible solutions is often not available or possible which results the research of finding the top-k best solutions.However,in some situations,the cohesive subgraphs are not complete subgraphs,and the solutions found by this way are highly overlapping.To address these problems,in recent years,the diversified top-k cohesive subgraph models,such as diversified top-k weight clique,diversified temporal subgraph,diversified graph pattern matching,and diversified top-k biclique,are proposed.The diversified top-k cohesive subgraph problem is to find top-k cohesive subgraphs in a given graph to maximize its coverage,where the NP-hardness of the diversified top-kclique problem and diversified top-k weight clique problem has been proved.The main methods for solving the diversified top-k cohesive subgraph problem include complete algorithm and non-complete algorithm.When a complete algorithm is used to solve the problem,it can obtain the optimal solution,but its solving capability is very limited.In practical applications,diversified top-k optimization problems are usually large-scale problems,which are not feasible to be solved by complete algorithms in most cases.So,the advantage of approximation methods,which can obtain excellent feasible solutions in a limited time,has been highlighted.The non-complete algorithm mainly includes approximation algorithms and heuristic algorithms.As we know,the approximation algorithm can guarantee the approximation ratio of the solutions,but the quality of the solutions is often not good enough.When solving the problems with a heuristic algorithm,although it does not guarantee that the solutions obtained are optimal,it can obtain good enough solutions within a reasonable time.Therefore,in solving large-scale diversified top-k cohesive subgraph problems,the heuristic algorithms are always the priority choice of the researchers when there is no demand for the optimal solution.In recent years,thanks to the wide applications in gene expression,community search,anomaly detection and other problems,diversified top-k clique and related problems have attracted much attention from researchers.However,the existing algorithms have limited solving capability and insufficient quality of results for the large-scale instances.Therefore,in this thesis,we investigate non-complete algorithms for diversified top-k clique problem,diversified top-k weight clique problem,and diversified top-k s-plex problem.The diversified top-k weigh clique problem and the diversified top-k s-plex problem can be considered as the relaxed problems of the diversified top-k clique problem.Then we introduce the diversified top-k s-plex problem as a new model in the network based on the previous work.The main research contents and contributions of this paper are outlined as follows:(1)For the diversified top-k clique problem,the constraint formulas and the proof of the NP-hardness are given first.After that,we proposed an enhanced configuration checking strategy and a clique scoring strategy for diversified top-k clique problem.Among them,the enhanced configuration checking strategy is used to prevent the local search algorithm from falling into the local optimum and to avoid the circle search during the search procedure.The clique scoring strategy is used to evaluate the contribution of each clique in the incumbent solution during the updating phase of the solution.Then,an efficient local search algorithm based on these two strategies is proposed,called TOPKLS,which can effectively and efficiently achieve a better solution by finding and removing the cliques with the smallest value of the score.On large-scale real-world instances,the performance of TOPKLS algorithm is significantly better than the state-of-the-art algorithm.On the DIMACS and BHOSLIB benchmarks,the existing algorithm cannot give feasible solutions,while TOPKLS yields excellent solutions.(2)For the diversified top-k weight clique problem,we give the constraint formulas and prove its NP-hardness.Then,a hybrid evolutionary algorithm,HEA-D,is proposed to solve it.HEA-D uses a clique-based crossover strategy to crossover two parent individuals selected from the population to generate a new offspring individual.This crossover operation is a good way to inherit the good genes from the parents to generate a new better individual.Meanwhile,the algorithm uses a simulated annealing updating procedure to further improve the quality of the individuals generated by the initialization and crossover procedures.In order to efficiently replace the maximal weight clique in an individual during the updating procedure,a weighted clique-based scoring strategy is proposed to evaluate the quality of each maximal weight clique in an individual.The algorithm is compared with TOPKWCLQ,a weighted variant of the TOPKLS algorithm,and the CPLEX solver based on our constraint model on two benchmarks which include 110 instances,and the experimental results show the effectiveness and efficiency of the HEA-D algorithm.(3)For the diversified top-k s-plex problem,which is a relaxed problem of the diversified top-k clique problem.For this problem,the constraint formulas and the proof of its NP-hardness are given.We also propose two approximation algorithms,Enum Max and Enum Fast,as the baseline algorithms.The Enum Max algorithm stores all the maximal-plexes in the memory,and uses a greedy algorithm for the maximum -set coverage problem to obtain a(1–1/)-approximation solution that can be guaranteed.In contrast,the Enum Fast algorithm integrates the enumeration of the maximal -plexes and the solving method of the diversified top-k s-plex problem.So,it does not need to store all the -plexes,and the algorithm obtains a solution of 0.25-approximation ratio.Furthermore,an iterative local search algorithm based on Tabu search,called TOPKSPLEX,is proposed to solve the diversified top-k s-plex problem efficiently.The performance of TOPKSPLEX,Enum Max,Enum Fast,and the CPLEX solver based on the constraint formulation is compared on 139real-world large instances,and the results show that TOPKSPLEX outperforms the comparators. |
