模块密度谱分的网络社团发现方法

doi:10.3969/j.issn.1001-2400.2010.05.025

J4 ›› 2010, Vol. 37 ›› Issue (5): 916-920+965.doi: 10.3969/j.issn.1001-2400.2010.05.025

• Original Articles • Previous Articles Next Articles

Spectral approach to finding communities in networks based on the modularity density

FU Li-dong^1,2;GAO Lin¹

(1. School of Computer Science and Technology, Xidian Univ., Xi'an 710071， China;
2. The School of Computer, Xi'an Univ. of Science and Tech., Xi'an 710054， China)

Received:2009-10-12 Online:2010-10-20 Published:2010-10-11
Contact: FU Li-dong E-mail:fulidong2005@163.com

Abstract

Abstract:

To detect the community structure in complex networks effectively, the modularity density function (D value) is optimized by the optimizing process, how the optimization of the D function can be reformulated as a spectral relaxation problem is proved and a new spectral clustering algorithm is proposed. The algorithm allows automatic selection of the number of community structures. The approach is illustrated and compared with the direct kernel approach based on the modularity density and spectral clustering based on modularity (Q) by using a classic computer generated networks and a real world network. Experimental results show the significance of the proposed approach, particularly, in the cases when the community structure is obscure.

Key words: complex networks, community structures, modularity density, spectral approach

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.

References

[1] Fortunato S, Latora V, Marchiori M. Method to Find Community Structure Based on Information Centrality[J] . Phys Rev E, 2004, 70(13): 056105.
[2] Girvan M, Newman M E J. Community Structure in Social and Biological Networks[J] . Proc Natl Acad Sci USA, 2002(99): 7821.
[3] Palla G, Derényi I, Farkas I, et al. Uncovering the Overlapping Community Structure of Complex Network in Nature and Society[J] . Nature, 2005(435): 814-818.
[4] Newman M E J. The Structure and Function of Complex Networks[J] . Proc Natl Acad Sci USA, 2006(103): 8577-8582.
[5] Wang G X, Shen Y, Ouyang M. A Vector Partitioning Approach to Detecting Community Structure in Complex Networks[J] . Comput Math Appl, 2008, 55(12): 2746-2752.
[6] Pothen A, Simon H D, Uou K P. Partitioning Sparse Matrices with Eigenvectors of Graphs[J] . Siam J Matrix Anal Appl, 1990, 11(3): 430-452.
[7] Fiedler M. Albegraic Connectivity of Graphs[J] . Czech Math J, 1973(23): 298-305.
[8] 马秀丽, 焦李成. 联合模型初始化独立谱聚类算法[J] . 西安电子科技大学学报, 2007, 34(5): 768-772.
Ma Xiuli, Jiao Licheng. Initialization-independent Spectral Clustering on the Joint Model[J] . Joural of Xidian University, 2007, 34(5): 768-772.
[9] Newman M E J. Finding Community Structure in Networks Using the Eigenvectors of Matrices[J] . Phys Rev E, 2006, 74(3): 036104.
[10] Newman M E J. Modularity and Community Structure in Networks[J] . Proc Natl Acad Sci USA, 2006(103): 8577-8582.
[11] Fortunato S, Barthélemy M. Resolution Limit in Community Detection[J] . Proc Natl Acad Sci USA, 2007, 104(1): 36-41.
[12] Li Z P, Zhang S H, Wang R S, et al. Quantitative Function for Community Detection[J] . Phys Rev E, 2008, 77(3): 036109.
[13] Dhillon I S, Guan Y, Kulis B. Kernel K-means, Spectral Clusterng and Normalized Cuts[C] //Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2004: 551-556.
[14] Luxburg U V. A Tutorial on Spectral Clustering[J] . Stati Comp, 2007, 17(4): 395-416.
[15] Newman M E J, Girvan M. Finding and Evaluating Community Structure in Network[J] . Phys Rev E, 2004, 69(15): 026113.
[16] Kulis B, Basu S, Dhillon I, et.al. Semi-supervised Graph Clustering: a Kernel Approach[J] . Math Learn, 2009(74):1-22.
[17] 赵峰, 张军英, 刘敬. 核最优变换与聚类中心的算法[J] . 西安电子科技大学学报, 2009, 36(1):127-133.
Zhang Feng, Zhang Junying, Liu Jing. Kernel Optimal Transformation and Cluster Centers Algorithm[J] . Journal of Xidian University, 2009, 36(1): 127-133.
[18] Zachary W W. An Information Flow Model for Conflict and Fission in Small Groups[J] . Jour Anth Rese, 1977(33): 452-473.

Spectral approach to finding communities in networks based on the modularity density

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 4

Metrics

Comments

Recommended 0

[1]	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.
[2]	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.
[3]	WANG Yu;GAO Lin. Discovering communities in dynamic networks: a bridgeness incremental clustering algorithm [J]. J4, 2013, 40(1): 30-35.
[4]	FU Lidong;GAO Lin. Kernel k-means clustering algorithm for detecting communities in complex networks based on eigenvector [J]. J4, 2012, 39(2): 175-180.