The Design And Analysis Of Cohesive Subgraph Mining Algorithms Based On K-plex Structure

Cohesive subgraph mining is widely studied as a fundamental problem in graph anal-ysis,which is mainly used to retrieve the densely connected vertices in networks.Gen-erally speaking a clique,that is,a subset of vertices that are adjacent to each other,is the most classic cohesive subgraph model.However,in practice,large and densely connected cohesive subgraphs can rarely appear as cliques due to data noise.Hence,the k-plex is proposed as a relaxed form of clique.A k-plex is a vertex set in which every vertex is not adjacent to at most k vertices of this set.Compared with clique,k-plex relaxes the criterion of degree of vertices in clique,so its application fields are wider.A fundamental problem of k-plex is the maximal k-plex enumeration problem,that is,to list all maximal k-plexes of prescribed size in a given graph.For an n-vertex graph,ex-isting Bron-Kerbosch-based algorithms enumerate the maximal k-plexes in running time O（2ⁿ）in the worst-case.In this thesis,a multi-branch algorithm based on graph decom-position is proposed for the maximal k-plex enumeration problem.The algorithm decom-poses the input graph into multiple subgraphs based on the principle of graph decompo-sition,and calls a multi-branch algorithm to search on each subgraph.In a subgraph with n vertices,the worst-case running time of this multi-branch algorithm is O（n~2γⁿ）,whereγ<2.The experimental results show that the algorithm proposed in this thesis signifi-cantly outperforms the existing maximal k-plex enumeration algorithm in running speed.The maximum k-plex problem is a special case of the maximal k-plex enumeration problem,which asks for the largest k-plex from the given graph.In this problem,the ex-isting algorithms lack consideration of large graphs,so this thesis proposes an exact algo-rithm Ma Plex for large real-world graphs.Based on the existing vertex and the novel edge reduction rules,this thesis design a powerful preprocessing method which efficiently re-moves redundant vertices and edges for Ma Plex.Also,the graph color heuristic is widely used for overestimating the maximum clique of a graph.For the first time,this thesis gen-eralize this technique for bounding the size of maximum k-plex in Ma Plex.Experimental results show that Ma Plex outperforms all other algorithms on large real-world graphs.