结合概率矩阵的改进谱聚类社区发现算法  

Improved spectral clustering community detection algorithm by combining the probability matrix

作　　者：张书博 任淑霞[1] 吴涛 ZHANG Shubo;REN Shuxia;WU Tao(School of Computer Science and Software Engineering,Tianjin Polytechnic Univ.,Tianjin 300387,China)

机构地区：[1]天津工业大学计算机科学与软件学院

出　　处：《西安电子科技大学学报》2019年第3期167-172,共6页Journal of Xidian University

基　　金：国家自然科学基金(61403278)

摘　　要：针对目前谱聚类算法的相似图包含较多错误社区信息的问题,引入了概率矩阵的概念,提出了一种改进的谱聚类社区发现算法。该算法首先利用马尔可夫过程计算节点间的转移概率,并基于转移概率构建复杂网络的概率矩阵;然后以均值概率矩阵重新构造相似图;最后通过优化归一化切割函数实现社区划分。采用人工网络和现实网络与其他典型算法进行对比实验,实验结果表明,该算法能够更加精准地划分社区,具有更加良好的聚类性能。Due to the fact that the similarity graphs of most spectral clustering algorithms carry lots of wrong community information, a probability matrix and a novel improved spectral clustering algorithm for community detection are proposed. First, the Markov process is used to calculate the transition probability between nodes, and the probability matrix of a complex network is constructed by the transition probability. Then the similarity graph is reconstructed with the mean probability matrix. Finally, the community detection is achieved by optimizing the normalized cuts function. The proposed algorithm is compared with other classical algorithms on artificial networks and real networks. The results show that our algorithm can cluster the community more accurately and has a better clustering performance.

关 键 词：概率矩阵 谱聚类 转移概率 马尔可夫过程 社区发现 复杂网络 

分 类 号：TP393.02[自动化与计算机技术—计算机应用技术]