Research On Spectral Clustering Community Detection Algorithm Based On Bayesian Inference And Graph Kernel

Community structure is a vital fundamental characteristic of complex networks,for which scholars in various fields have successively proposed many community detection algorithms.How to effectively extract the information of points and edges in complex networks is the main goal of such algorithms.The spectral clustering method is one of the classic algorithms.Com-pared with other community detection algorithms,this method has the advantages of rigorous mathematical logic,suitable for high-dimensional data,the ability of clustering on data sets with an arbitrary probability distribution and converging to the global optimal solution.However,the spectral clustering method has certain limitations.First,the algorithm needs to manually spec-ify the number of communities.The existing community number detection algorithms cannot estimate the number of communities quickly and effectively when the community structure is not obvious.Secondly,the similarity matrix of most spectral clustering methods is constructed based on a specific similarity index,which may lead to the consequence that only part of the structure information of the node can be obtained.However,the construction of the similar-ity matrix and the selection of feature vectors have a huge impact on the accuracy of the final community detection results.In response to the above problems,the thesis studies community number detection algorithms and community detection algorithms,which mainly include the following two parts:(1)Aiming at the slow detection speed and low accuracy of traditional community number detection algorithms,the thesis proposes a fast community number detection algorithm based on Bayesian inference.This algorithm firstly prunes and reconstructs the original network to segment multiple small connected graphs,and then determines the Monte Carlo sampling pro-cess based on the degree-corrected random block model,thereby obtaining an estimate of the number of communities in the current network.Experimental results show that the detection speed and accuracy of this algorithm are superior to other existing community number detection algorithms.(2)In order to solve the problem that the similarity matrix constructed by the traditional spectral clustering algorithm cannot obtain the complete structure information of the node,the thesis proposes a spectral clustering community detection algorithm based on point mutual in-formation kernel.This algorithm first proposes and defines a new graph kernel based on point mutual information-PMI-Kernel,and constructs similarity matrices and standardized Laplacian matrices based on it,then calculates the corresponding eigenvectors to obtain the final feature matrix.Based on the estimated number of communities obtained before,the k-means algorithm is used to cluster the row vectors of the feature matrix and map the row vectors to the correspond-ing nodes to obtain the final community detection result.Experiments on real complex networks and artificial synthetic networks show that the algorithm has high accuracy and stability.