基于DCBM的马尔可夫谱聚类社区发现算法

Markov Spectral Clustering Algorithm with DCBM for Community Detection

摘要:

谱聚类划分算法是经典社区发现算法之一，由于目前构造的相似图承载的社区结构信息较少，导致聚类效果与理想效果具有较大差距，因此，提出了基于DCBM的马尔可夫谱聚类社区发现算法MSCD.首先，基于DCBM模型提出了以节点间连接概率为元素的概率矩阵，并建立了概率矩阵与相似矩阵之间的映射关系，其次，利用马尔可夫链重构了谱聚类的相似图，最后，使用重构的相似图对网络进行社区划分.在人工合成网络和真实网络上与SC、MRW-KNN、FluidC三种典型算法进行了对比实验，实验结果表明，MSCD算法具有更加高效的聚类性能，能够揭示更加清晰的社区结构.

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.