Research On Algorithms For The Maximum ?-plex Problem And Maximal ?-plex Enumeration

Clique is one of the important concepts for detecting cohesive subgraphs in graph theory,and it is widely used in artificial intelligence,data mining and other fields.Clique requires the vertices are all pairwise adjacent,but the restriction is too strict in practical applications.Therefore,as a relaxed form of clique,k-Plex allows existing missing edges between its vertices,which plays a more important role in detecting cohesive subgraphs.In recent years,research on related k-Plex algorithms has received extensive attention.Finding the k=Plex with the most number of vertices in a given graph,named 'the maximum k-Plex problem,is a research hot-spot in this field.At the same time,in order to better analyze the internal structure of the graph,the maximal k-Plex enumeration algorithm is also received much attention.In recent years,algorithms based on the above k-Plex problems have been proposed one after another,and they have played an important role in social network analysis,bioinformatics,etc.First,this thesis studies the heuristic strategies:of the branch-and-bound algorithm for the maximum k-Plex problem.And two efficient vertex order heuristic strategies are proposed to speed up the search process,one is selecting the branch vertices according to the vertex historical information of vertices,which are collected in the process of subgraph reductions;the other is combining the vertex historical information and vertex degree to select branch vertices.At the same time,this thesis also proposes a heuristic strategy for vertex reduction according to the degree of the vertex in order to avoid invalid reduction and time-consuming.On the other hand,for the maximal k-Plex enumeration problem,this thesis 'combines a number of reduction rules to design a branch-and-bound algorithm for enumerating all maximal connected k-Plex,and proposes two pruning rules to avoid repeated search branches that do not contain any maximal k-Plex.Meanwhile,parameterized settings of the reduction process in backtracking of the algorithm are set up,and are optimized the parameters with the irace which is a parameter optimization tool.A series of comparative experiments show that the enumeration algorithm proposed in this thesis is superior to the recently proposed k-Plex enumeration algorithms in computational efficiency.