Research On Constructing And Maintaining Cohensive Model Hierarchy

Graph is a structure to store relationships between entities,and can model various scenarios in reality.Dense subgraph detection is a basic problem in graph reserach.To deal with different scenarios,the industry has carried out extensive research on many dense subgraph models,such as clique,k-core,k-truss,k-plex,k-ecc,etc.We can mine dense subgraphs with different k param in a graph.The dense subgraph mined by k-core and k-truss model has obvious hierarchical structures.The graph is decomposed and indexed into a hierarchical tree to assist in studying the specific structure of the network graph.At the same time,in real life,graphs are often in high-speed dynamic changes.On the other hand,with the continuous expansion of social networks,the number of users increases,the scale of graphs becomes larger,and the requirements for effectively updating these hierarchies in a short time are also increasing.For complex networks,a small change can have a huge impact on the hierarchy.Facing the dynamic change of large graphs,how to maintain the two hierarchical structures efficiently and effectively is a huge challenge faced by the research.This thesis mainly studies the maintenance processing of the k-core hierarchy.Based on the definition of the k-core hierarchy,we propose a k-truss component based on k-truss,its construction algorithm and an algorithm for maintaining the index structure when inserting an edge.Aiming at these above problems and algorithmms,the main contributions of this thesis are listed as follows:(1).Maintaining k-core hierarchy when updating one edge.k-core model has be- come the most widely studied model as the algorithm for decomposing a graph by k-core has linear time complexity.Most of the existing research on k-core in dynamic graphs only focuses on the coreness of each vertex.This thesis first analyzes the region where the k-core hierarchy changes in the case of inserting/deleting one edge,and proposes a series of theorems to prove that all parts except this region do not change.Meanwhile,based on the coreness maintenance algorithm and the properties of the hierarchical structure,we put forward the idea and the algorithm of the maintenance process,and additional theorems to prove the correctness of these processes.Finally the maintenance algorithms and construction algorithm are tested on ten data sets.The comparison is carried out,and the effectiveness and efficiency of the algorithm are proved.(2).Maintaining k-core hierarchy when multiple edges changed.In the one-edge maintenance of k-core hierarchy,we found that the running time of the solution requires up to several seconds in a larger dataset.Therefore,this thesis is devoted to the research on the maintenance work under the condition of multiple edges changes at the same time.By summarizing the laws of changes,a general paradigm is proposed for the changes in the tree from a higher perspective,so that the maintenance tasks on multiple edges are consolidated.We first propose an algorithm to deal with this problem,and propose a series of optimization methods.In addition,in order to further improve the efficiency of the algorithm,we extend the problem to multi-core for parallelization optimization.By analyzing the problem from a more global perspective,we can decouple the problem,and try to balance the number of tasks for each core by analyzing the scales of different subtrees in the tree.Finally,we have demonstrated the high efficiency and effectiveness of the algorithms with experiments on 10 real datasets.(3).Hierarchy construction based on the k-truss and maintenance when inserting a single edge.Since the subgraph obtained by the k-truss model is more cohesive than the k-core,there are many existing works to discover communities on a given social network graph based on k-truss.Since the k-truss model is proposed based on the cohesion of edges,the existing work to find communities bases on edges mostly.But this scheme requires more computation time than k-cores.Aiming at this difficulty,this thesis uses the k-truss model to design the definition of k-truss hierarchy based on vertex's and edge's trussness.According to the definition of k-truss hierarchical structure,this thesis analyzes the difference between k-truss hierarchical structure and k-core hierarchy,and proposes a construction algorithm through the relationship between vertices and nodes by disjoint union set.In addition,this thesis also analyzes the maintenance of the k-truss hierarchy in the case of inserting an edge,and proposes a corresponding algorithm to solve the problem.Finally,this thesis conducts experiments on the algorithm on 8 datasets,and the results prove the efficiency and effectiveness of the k-truss hierarchy.