A Graph Clustering Algorithm Based on Structural Similarity

doi:10.3969/j.issn.1006-2475.2016.03.005

Abstract

Abstract: Network clustering (or graph partitioning) is an important task for the discovery of underlying structures in networks. In this paper, a fast algorithm named GNSCAN based on structure similarity is proposed, and the related definition and algorithm implementation process are given. In order to test the performance of the algorithm, a group of real datasets are used to test the algorithm. The theoretical analysis and experimental results show that the proposed GNSCAN algorithm is improved in efficiency. On the basis of the above GNSCAN algorithm, IGNSCAN is proposed. And the computation complexity of the algorithm IGNSCAN is more efficiency.

Key words: community discovery, social network, GNSCAN algorithm, structural similarity

CLC Number:

TP391

JIN Chao, ZHANG Long-bo, WANG Hai-peng, AN Jian-rui, HUAI Hao, WANG Xiao-dan. A Graph Clustering Algorithm Based on Structural Similarity[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2016.03.005.

References

[1] Flake G W, Tarjan R E, Tsioutsiouliklis K. Graph clustering and minimum cut trees[J]. Internet Mathematics, 2003,1(4):385-408.

[2] Beineke L W, Wilson R J. Topics in Algebraic Graph Theory[M]. Cambridge University Press, 2004:276.

[3] Yang Bo, Cheung W K, Liu Jiming. Community mining from signed social networks[J]. IEEE Transactions on Knowledge & Data Engineering, 2007,19(10):1333-1348.

[4] 沈华伟,程学旗,陈海强,等. 基于信息瓶颈的社区发现[J]. 计算机学报, 2008,31(4):677-686.

[5] 黄发良,张师超,朱晓峰. 基于多目标优化的网络社区发现方法[J]. 软件学报, 2013,24(9):2062-2077.

[6] 段炼,朱欣焰. 基于社区时空主题模型的微博社区发现方法[J]. 电子科技大学学报, 2014,43(3):464-469.

[7] McDaid A F, Murphy T B, Friel N, et al. Model-based clustering in networks with stochastic community finding[C]// COMPSTAT 2012 Proceedings. 2012.

[8] Chen Dongming, Dong Yanlin, Huang Xinyu, et al. A community finding method for weighted dynamic online social network based on user behavior[J]. International Journal of Distributed Sensor Networks, 2015,2015: Article No. 97.

[9] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences, 2002,99(12):7821-7826.

[10] Newman M E J. Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004,69(6):279-307.

[11] Xu Xiaowei, Yuruk N, Feng Zhidan, et al. SCAN: A structural clustering algorithm for networks[C]// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2007:824-833.

[12] Zhao Weizhong, Martha V, Xu Xiaowei. PSCAN: A parallel structural clustering algorithm for big networks in MapReduce[C]// Proceedings of the 27th IEEE International Conference on Advanced Information Networking and Applications (AINA). 2013:862-869.

[13] Zhang Huijuan, Sun Shixuan. A graph clustering algorithm based on shared neighbors and connectivity[C]// Proceedings of the 8th IEEE International Conference on Computer Science & Education (ICCSE). 2013:761-764.

[14] 吴烨,钟志农,熊伟,等. 一种高效的属性图聚类方法[J]. 计算机学报, 2013,36(8):1704-1713.

[15] 冷泳林,鲁富宇. 基于MapReduce的SimRank算法在图聚类中的应用[J]. 电子设计工程, 2015,23(6):9-11.

[16] Tabrizi S A, Shakery A, Asadpour M, et al. Personalized pageRank clustering: A graph clustering algorithm based on random walks[J]. Physica A: Statistical Mechanics & Its Applications, 2013,392(22):5772-5785.

[17] Newman M E J. Communities, modules and large-scale structure in networks[J]. Nature Physics, 2012,8(1):25-31.