Research On Community Detection Algorithm Based On Structure Granulation

In real life,there are a variety of complex networks that are abstracted from complex systems.The research and analysis of these networks will enable us to have a better understanding of its structure and behavior.Community structure is an important structural feature in complex networks,and its existence has an important impact on the operation of the network.The community refers to the group formed by a group of closely connected individuals,which are closely linked within the community,and the sparse relationship between communities.Such as the circle of friends in QQ and WeChat,a topic forum on Post Bar,the cooperative groups in the network of scientists and a protein group that constitutes a functional module in a protein interactive network and so on.Mining the community structure in complex networks has become a hot research in complex network analysis.It is of great importance for understanding network structure,analyzing network behavior and predicting network security.Therefore,community detection research in complex networks has become a research topic with important theoretical significance and practical application value.Many effective algorithms have been proposed so far in community discovery research and development.However,with the rapid development of the Internet and mobile terminals and the geometric expansion of data size,many traditional algorithms have been difficult to effectively handle large-scale complex networks.In order to solve this problem,this dissertation introduces the idea of granulation into the community discovery algorithm,which aims to reduce the size of the network by compressing the nodes and edges of the network by means of granulating,thereby reducing the complexity of problem solving.After in-depth research on relevant theories and algorithms of community discovery and related theoretical knowledge of granular computing,we propose two effective structure granulation algorithms:Multilayer granulation community detection algorithm based on local modularity(MGr-LM)and Adaptive granulation community detection algorithm based on node similarity(AGr-NS).The feasibility and effectiveness of the algorithm are verified by applying them to eight real-world network datasets of different types and sizes and compared with several current popular algorithms.The main work of this dissertation is as follows:1)Multilayer granulation community detection algorithm based on local modularity(MGr-LM Algorithm):This dissertation first studies and designs the structure granulation operations of the compressed network,including the operation of node granulation based on local modularity and the operation of edge granulation.Then,the complex network is granulated into different granular networks from thin to coarse,and a multi-granularity super network with layer by layer granulation and layer by layer abstraction is formed,in which each layer of super network corresponds to a granularity of community partition(a super node represents a community).Finally,according to the object of problem,the optimal granular layer is selected as the final results.The results of a series of experiments on public data sets show that the method can quickly partition the network of different types and sizes and obtain higher quality community structure and has obvious advantages in obtaining more real and meaningful community structure.2)An adaptive granulation community detection algorithm based on node similarity(AGr-NS Algorithm):The algorithm MGr-LM needs to obtain all the granular layers in the granulation process and then choose the best result.In order to improve the process and enable the algorithm to automatically reveal and stop the optimal granular layer,an adaptive granulation algorithm named AGr-NS is proposed.The algorithm first calculates the similarity between adjacent nodes in the network.Then,the network is adaptively granulated by the improved structure granulation operation and automatically converged to a satisfactory community granular layer.Finally,the isolated nodes on the granular layer are processed and distributed to the smaller neighboring communities to obtain the final partition result.Among them,the granulation process is hcuristically optimized based on the similarity of nodes and the modularity of the network bases on node similarity,which ensures the accuracy of partition and eliminates the problem of resolution limits that is incidental to pure network modularity optimization algorithm.A series of experimental results show that the proposed algorithm AGr-NS is feasible and effective and can directly adaptively obtain the same results or similar results that compare to the optimal results obtained by the algorithm MGr-LM.