Research On Community Discovery Algorithm Based On Spectral Clustering

Many real complex systems can be abstracted into complex networks.Community structure is one of the most important features in real networks.It reveals node properties and network structure.It can be applied to information searching,behavior predicting,functional analyzing,etc.It has very important practical significance and researching value.The community detection algorithm is an algorithm that divides complex networks into many communities according to some rules.It can get the community structure of complex networks.It is a popular research direction of complex networks,and has attracted attention from many domestic and international researchers.In recent years,many community detection algorithms have been proposed,and the spectral clustering community detection algorithm is one of the typical algorithms.However,the spectral clustering algorithm cannot correctly calculate the similarity of some nodes,resulting in the similar matrix containing much wrong community information.To solve the above problems,this paper proves that the connection probability between nodes includes community information by the degree-corrected stochastic block model,and uses the connection probability to get the similarity between nodes.Furthermore,the probability matrix and mean probability matrix is introduced,and an improved spectral clustering community detection algorithm based on mean probability matrix is proposed.The main researching contents include:1.Prove that the connection probability between nodes contains community information:The degree-corrected stochastic block model proves that the connection probability between nodes contains a large amount of community structure information.And the mapping relationship between the connection probability and the similarity between nodes is established.2.Propose the probability matrix and the mean probability matrix:According to the Markov process,the transition probability between nodes is calculated,and the probability matrix of complex network is constructed by multi-order weighted transition probability.In order to reduce the bias caused by the parameters of the probability matrix,the mean probability matrix is proposed based on probability matrices of different time scale.3.Propose an improved spectral clustering community detection algorithm based on the mean probability matrix:An improved spectral clustering community detection algorithm is proposed.The similarity matrix of complex network is constructed based on the mean probability matrix,and the communities is obtained by optimizing normalized cut function.Finally,this paper uses lots of synthetic complex networks and real-world complex networks for experimenting.The quality of different community detection algorithms is evaluated by calculating modularity,adjusted rand index and normalized mutual information.Experiments show that the proposed algorithm has excellent performance for community detection and can accurately divide complex networks.