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

doi:10.19665/j.issn1001-2400.2019.03.025

摘要/Abstract

摘要：

针对目前谱聚类算法的相似图包含较多错误社区信息的问题,引入了概率矩阵的概念,提出了一种改进的谱聚类社区发现算法。该算法首先利用马尔可夫过程计算节点间的转移概率,并基于转移概率构建复杂网络的概率矩阵;然后以均值概率矩阵重新构造相似图;最后通过优化归一化切割函数实现社区划分。采用人工网络和现实网络与其他典型算法进行对比实验,实验结果表明,该算法能够更加精准地划分社区,具有更加良好的聚类性能。

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

Abstract:

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.

Key words: probability matrix, spectral clustering, transition probability, Markov process, community detection, complex network

中图分类号:

TP393.02

张书博,任淑霞,吴涛. 结合概率矩阵的改进谱聚类社区发现算法[J]. 西安电子科技大学学报, 2019, 46(3): 167-172.

ZHANG Shubo,REN Shuxia,WU Tao. Improved spectral clustering community detection algorithm by combining the probability matrix[J]. Journal of Xidian University, 2019, 46(3): 167-172.

图/表 6

表1

图1

图2

图3

表2

图4

参考文献 18

[1]	GIRVAN M, NEWMAN M E J. Community Structure in Social and Biological Networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2002,99(12):7821-7826. doi: 10.1073/pnas.122653799
[2]	付立冬, 马小科, 聂靖靖 . 进化谱分算法检测动态网络社团结构[J]. 西安电子科技大学学报, 2018,45(2): 43-47+53.
	FU Lidong, MA Xiaoke, NIE Jingjing . Evolutionary Spectral Approach to Finding Communties in Dynamic Networks[J]. Journal of Xidian University, 2018,45(2): 43-47+53.
[3]	JIANJUN C, XINHONG Y, QI L , et al. Voting Simulation Based Agglomerative Hierarchical Method for Network Community Detection[J]. Scientific Reports, 2018,8(1):8064-8075. doi: 10.1038/s41598-018-26415-3
[4]	DE GUZZI BAGNATO G, RONQUI J R F, TRAVIESO G . Community Detection in Networks Using Self-avoiding Random Walks[J]. Physica A: Statistical Mechanics and Its Applications, 2018,505:1046-1055. doi: 10.1016/j.physa.2018.04.006
[5]	NG A Y, JORDAN M I, WEISS Y . On Spectral Clustering: Analysis and an Algorithm[CA/OL].[2018-11-20]. https://papers.nips.cc/paper/2092-on-spectral-clustering-analysis-and-an-algorithm.pdf
[6]	XUANMEI Q, WEIDI D, PENGFEI J , et al. A Multi-similarity Spectral Clustering Method for Community Detection in Dynamic Networks[J]. Scientific Reports, 2016,6:31454. doi: 10.1038/srep31454
[7]	NARANTSATSRALT U U, KANG S . Social Network Community Detection Using Agglomerative Spectral Clustering[J]. Complexity, 2017,2017:1-10.
[8]	GUI C, ZHANG R, HU R , et al. Overlapping Communities Detection Based on Spectral Analysis of Line Graphs[J]. Physica A: Statistical Mechanics and Its Applications, 2018,498:50-65. doi: 10.1016/j.physa.2018.01.025
[9]	LI X, CHENG X, SU S , et al. Community-based Seeds Selection Algorithm for Location Aware Influence Maximization[J]. Neurocomputing, 2018,275:1601-1613. doi: 10.1016/j.neucom.2017.10.007
[10]	ZHANG X C, YOU Q . An Improved Spectral Clustering Algorithm Based on Random Walk[J]. Frontiers of Computer Science in China, 2011,5(3):268-278. doi: 10.1007/s11704-011-0023-0
[11]	WANG B, ZHANG L, WU C , et al. Spectral Clustering Based on Similarity and Dissimilarity Criterion[J]. Pattern Analysis and Applications, 2017,20(2):495-506. doi: 10.1007/s10044-015-0515-x
[12]	SUN P G, SUN X . Complete Graph Model for Community Detection[J]. Physica A: Statistical Mechanics and Its Applications, 2017,471:88-97. doi: 10.1016/j.physa.2016.12.014
[13]	AMELIO A, PIZZUTI C . Correction for Closeness: Adjusting Normalized Mutual Information Measure for Clustering Comparison[J]. Computational Intelligence, 2017,33(3):579-601. doi: 10.1111/coin.v33.3
[14]	RABBANY R, ZAÏANE O R . Generalization of Clustering Agreements and Distances for Overlapping Clusters and Network Communities[J]. Data Mining and Knowledge Discovery, 2015,29(5):1458-1485. doi: 10.1007/s10618-015-0426-x
[15]	SAOUD B, MOUSSAOUI A . Community Detection in Networks Based on Minimum Spanning Tree and Modularity[J]. Physica A: Statistical Mechanics and Its Applications, 2016,460:230-234. doi: 10.1016/j.physa.2016.05.014
[16]	PONS P, LATAPY M . Computing Communities in Large Networks Using Random Walks [C]//Lecture Notes in Computer Science: 3733. Heidelberg: Springer Verlag, 2005: 284-293.
[17]	NEWMAN M E J . Fast Algorithm for Detecting Community Structure in Networks[J]. Physical Review E - Statistical, Nonlinear, Soft Matter Physics, 2004,69(62):066133. doi: 10.1103/PhysRevE.69.066133
[18]	PARES F, GARCIA-GASULLA D, VILALTA A , et al. Fluid Communities: A Competitive, Scalable and Diverse Community Detection Algorithm [C]//Proceedings of the 2017 6th Complex Networks & Their Applications. Heidelberg: Springer, 2017: 229-240.

参数	说明	取值
β	度分布的幂律指数	3
γ	社区大小的幂律指数	1.5
ave_deg	节点的平均度数	10
min_com	社区至少拥有的节点数	30
seed	随机数生成器的种子数	10

序号	网络名称	节点数	边数
1	US Air lines	332	2 126
2	Erdos991	454	1 421
3	Roget	1 010	3 656
4	Science	1 461	3 009
5	SCiNet	2 729	10 419
6	US Power Grid	4 941	6 594
7	Erdos992	6 094	9 949
8	PGP	10 680	24 316