Research On Density-based Community Detection In Complex Network

Community structure analysis is one of important areas in complex network.The basis of community structure analysis is community detection.The premise of community structure analysis is that community structure should be obtained at first,and the community detection is a tool of mining community in complex network.Communities in networks often have an arbitrary size and shape,so it is a challenging task to find communities in networks.Density-based clustering has the advantage that clustering results are not influenced by arbitrary size and shape.So,it can bring better results for community detection.As the research for this kind of community detection moves forward,experts have gradually found some problems of density-based community detection,such as imperfect optimization of parameters in algorithms,incomplete node similarity models,and poor evaluation functions of community detection.All these problems have brought negative impact on the performance of community detection.Therefore,researching these problems in density-based community detection has great significance for improving algorithm performance and guaranteeing the accuracy of community detection analysis.Focusing on density-based community detection for complex networks,this thesis studies existing problems from community detection framed by density-based clustering and community detection framed by density model.The study includes the following aspects.?1?This thesis analyzes major problems in community detection framed by density-based clustering and community detection framed by density model.Problems in community detection framed by density-based clustering lie in that parameter optimization methods and parameter determination methods are not perfect and the partition result is sensitive to parameters.Problems in community detection framed by density model lie in that the range of application of the node similarity mode is limited,the network density model cannot describe community structure appropriately,and there are some defects in distinguishability of evaluating function.?2?To resolve the problem that parameter optimization methods and parameter determination methods are not perfect in density-based clustering,this thesis researches parameter optimization methods and parameter determination methods in a typical algorithm.Concerning three parameters in the algorithm,this thesis provides three parameter determination methods.1)for smoothing parameter?,this thesis provides a method of optimization which is based on minimized density entropy and discusses the influence of noise points to getting the most optimized?.Moreover,directing at data sets with and without noise points,this thesis presents concrete procedures of how to use numerical method to get the most optimized?.2)In terms of noise threshold?,this thesis,according to density attractors,substitutes it with variable merging threshold?_ijj and f_C of arbitrary-shape clusters.3)Regarding step size?,this thesis presents an adaptive parameter determination method,replacing fixed step size with adaptive step size.All the research makes parameter optimization methods and parameter determination methods for density-based clustering more complete,and provides theoretical foundation for solving parameter setting in community detection based on density-based clustering.?3?To resolve the problem that the result of community detection based on density-based clustering is sensitive to parameters,this thesis researches methods of projecting networks into low-dimensional data set and the application of density clustering in community detection.The thesis also presents a community detection algorithm based on density-based clustering and another faster community detection which aims at the networks with small average node degree and big node degree variance.The first method is to construct Laplacian matrix of network and through Laplacian Eigenmap,the network is projected into low-dimensional space.The corresponding eigenvector of projected node is regarded as the coordinate of the node in this space,and then the network can be changed into low-dimensional data set.Density clustering presented in this thesis is then applied to complete community detection.The second method is to change the issue of obtaining kernel density estimation into the issue of obtaining node degree for the networks with small average node degree and big node degree variance while getting Gaussian window?and cutoff distance d through minimized density entropy.The idea of hill-climbing of the density clustering presented in this thesis is then applied to complete community detection.Experiments show that the above research results have more advantages in clustering performance.?4?To resolve the problem that the range of application of the node similarity mode is limited,the network density model cannot describe community structure appropriately,and there are some defects in distinguishability of evaluating function,this thesis researches similarity models,density models,evaluation functions and community detection algorithm.This thesis also presents a new node similarity model and a new community similarity model through the use of t-step transition matrix.Besides,this thesis puts forward a relative density model based on node similarity and evaluation function S based on this model.A community detection algorithm based on relative density is then presented.After network preprocessing by node similarity,this algorithm can get an initial partition;based on community similarity,these original clusters are hierarchically clustered;according to evaluation function S,the most optimized community detection algorithm can be filtered out.Finally,experiments show that the above research can bring excellent quality on the basis of density-based community detection.Based on the above theoretical analysis and simulation verification,the main research work and achievements of this thesis are summarized.Meanwhile,the further research works are also forecasted.