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

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

CLC Number:

TP393.02

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.

Figures/Tables 6

References 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

Improved spectral clustering community detection algorithm by combining the probability matrix

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 18

Related Articles 9

Metrics

Comments

Recommended 10

[1]	LUO Yi,TAN Xiansi,WANG Hong,QU Zhiguo. Method for predicting the attack intention of hypersonic vehicles [J]. Journal of Xidian University, 2019, 46(5): 113-119.
[2]	FU Lidong;MA Xiaoke;NIE Jingjing. Evolutionary spectral approach to finding communities in dynamic networks [J]. Journal of Xidian University, 2018, 45(2): 43-47+53.
[3]	LIU Lu;WANG Rongfang;JIAO Licheng;SHI Junfei. Combined similarity based spectral clustering ensemble for POLSAR classification [J]. J4, 2015, 42(3): 48-53+128.
[4]	CHEN Guoqiang;WANG Yuping. Revealing of the hierarchy community of the complex network by decomposition multi-objective optimization [J]. J4, 2013, 40(3): 205-211.
[5]	WANG Yu;GAO Lin. Discovering communities in dynamic networks: a bridgeness incremental clustering algorithm [J]. J4, 2013, 40(1): 30-35.
[6]	LIU Han-qiang;JIAO Li-cheng;ZHAO Feng. SAR image multilevel segmentation based on local similarity measure [J]. J4, 2010, 37(6): 1071-1076.
[7]	FU Li-dong;GAO Lin. Spectral approach to finding communities in networks based on the modularity density [J]. J4, 2010, 37(5): 916-920+965.
[8]	MA Xiu-li;JIAO Li-cheng. Initialization-independent spectral clustering on the joint model [J]. J4, 2007, 34(5): 768-772.
[9]	SONG Yue;LIU San-yang;FENG Hai-lin. Reliability analysis of consecutive n-1-out-of-n: G repairable systems with the multi-state component [J]. J4, 2005, 32(6): 965-967.