Research On Community Detection Algorithm Based On Graph Decomposition

Due to the rapid development of information technology,we are witnessing the proliferation of Big Data based applications over recent years.Studying how to deal-ing with such data resources in a proper and effective way is full of opportunities and challenges.The graph structure is often adopted in describing the complicated rela-tionship between entities in large scale data with its good expressiveness.Since there exist some community structures which reveal important graph property in the large scale graph data,huge research efforts have been devoted to studying the community detection problem.On the other hand,the cohesive subgraph refers to densely inner connected local subgraphs.there are various cohesive subgraph models,different in the constrain of the density.With the characteristic of high cohesion and low coupling,the cohesive subgraph perfectly fits in community detection tasks.Thus,the cohesive subgraph based solutions are quite popular in the community detection domain.In this thesis,our work is focused on the research on the community detection algo-rithm based on cohesive subgraph decomposition.For the state--of--the--art community detection solutions,it's hard to strike a balance between the quality of the returned result and the efficiency of the algorithm.What's more,due to the constrain of the community persistence,the performance of the state--of--the-art temporal persistent community detection solutions are not that satisfying.In this thesis,we propose a new k-TriPeak model based on a higher-order connectivity structure,and devise a new top-down de-composition paradigm for the k-TriPeak decomposition problem.We propose the static and dynamic upper bounding techniques to further improve the efficiency of the devised algorithm.For the persistent community detection tasks on temporal graphs,we also propose a new(k,l,?)-TriPeak model based on k-TriPeak,and devise a search based iterative algorithm.We propose a graph reduction optimizing technique and several effective pruning strategies to further improve the efficiency of the devised algorithm.Finally,We conduct extensive experiments on several large real-world graph datasets and the experimental results demonstrate the effectiveness and efficiency of our pro-posed models and algorithms.