Markov Spectral Clustering Algorithm with DCBM for Community Detection

Abstract:

Spectral clustering algorithm is one of the classical community detection algorithms. Due to the current constructed similarity graphs carry less community structure information, the actual clustering effect has a big gap with the ideal clustering effect. Therefore, based on degree corrected stochastic block model and Markov chain, a novel spectral clustering approach for community detection, called MSCD, is proposed. Firstly, probability matrix composed of the connection probability between nodes is introduced based on DCBM, and the mapping relationship is established between probability matrix and similar matrix. Then, Markov chain is utilized to reconstruct the similar graph of spectral clustering. Finally, the reconstructed similar graph is used to partition the networks into clusters. Three typical algorithms of SC, MRWKNN and FluidC are performed on synthetic networks and real networks. Comparative experiments show that the MSCD algorithm has more efficient clustering performance and can reveal a clearer community.

Key words:DCBM; Markov chain; Probability matrix; Spectral clustering; Community detection; Complex network