特征向量的核方法检测网络社团结构

doi:10.3969/j.issn.1001-2400.2012.02.029

J4 ›› 2012, Vol. 39 ›› Issue (2): 175-180.doi: 10.3969/j.issn.1001-2400.2012.02.029

• Original Articles • Previous Articles Next Articles

Kernel k-means clustering algorithm for detecting communities in complex networks based on eigenvector

FU Lidong^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 Sci. and Tech., Xi'an 710054， China)

Received:2010-12-27 Online:2012-04-20 Published:2012-05-21
Contact: FU Lidong E-mail:fulidong2005@163.com

Abstract

Abstract:

To detect the community structure in weighted complex networks, the modularity density function D is generalized to weighted variants(WD) and shows how optimizing the weighted function WD can be formulated as a spectral clustering problem, and a weighted kernel k-means clustering problem. We also prove the equivalence of both clustering approaches based on WD in mathematics. Using the equivalence, we propose a new eigenvector-based kernel clustering algorithm to detect communities in complex networks. Experimental results indicate that it has better performance compared with either the direct kernel k-means algorithm or direct spectral clustering algorithm in terms of quality.

Key words: community structures, modularity density, kernel k-means method, spectral approach, eigenvector-based kernel approach

CLC Number:

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.

References

［1］ Fortunato S. Community Detection in Graphs［J］. Physics Reports, 2010, 486(3-5): 75-174.
［2］ 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(7043): 814-818.
［3］ Palla G, Barabsi Al, Vicsek T. Quantifying Social Group Evolution［J］. Nature, 2007, 446(7136): 664-667.
［4］ Newman M E J. Modularity and Community Structure in Networks［J］. Proc Natl Acad Sci USA, 2006, 103(23): 8577-8582.
［5］陈盈晖, 杜海峰, 李树茁. 一种改进的模块性指标及其社群结构探测算法［J］. 西安电子科技大学学报, 2010, 37(2): 374-379.
Chen Yinghui, Du Haifeng, Li Shuzhuo. Modified Modularity and the Corresponding Community Structure Detecting Algorithm［J］. Journal of Xidian University, 2010, 37(2): 374-379.
［6］ Newman M E J. Finding Community Structure in Networks Using the Eigenvectors of Matrices［J］. Phys Rev E, 2006, 74(3): 036104.
［7］ Fortunato S, Barthélemy M. Resolution Limit in Community Detection［J］. Proc Natl Acad Sci USA, 2007, 104(1): 36-41.
［8］ Rosvall M, Bergstrom C T. A Information-theoretic Framework for Resolving Community Structure in Complex Networks［J］. Proc Natl Acad Sci USA, 2007, 104(18): 7327-7331..
［9］ Muff S, Rao F, Caflisch A. Local Modularity Measure for Network Clusterizations［J］. Phys Rev E, 2005, 72(5): 056107.
［10］ Li Z P, Zhang S H, Wang R S, et al. Quantitative Function for Community Detection［J］. Phys Rev E, 2008, 77(3): 036109.
［11］ Fu Lidong, Gao Lin, Ma Xiaoke. A Centrality Measure Based on Spectral Optimization of Modularity Density［J］. Science China Information Sciences, 2010, 53(9): 1727-1737.
［12］付立东, 高琳. 模块密度谱分的复杂网络社团发现方法［J］. 西安电子科技大学学报, 2010, 37(5): 916-920.
Fu Lidong, Gao Lin. Spectral Approach to Finding Communities in Networks Based on the Modularity Density［J］. Journal of Xidian University, 2010, 37(5): 916-920.
［13］ Dhillon I S, Guan Y, Kulis B. Kernel K-means, Spectral Clusterng and Normalized Cuts［C］//Proc of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2004: 551-556.
［14］ Lancichinetti A, Fourtunato S. Benchmarks for Testing Community Detection Algorithms on Directed and Weighted Graphs with Overlapping Communities［J］. Phys Rev E, 2009, 80(1): 016118.
［15］ Danon L, Diaz-Guilera A, Duch J, et.al. Comparing Community Structure Identification［J］. J Stat Mech Theory Exp, 2005(9): 09008.
［16］ Good B H, Montjoye Y A D, Clauset A. The Performance of Modularity Maximization in Practical Contexts［J］. Phys Rev E, 2010, 81(4): 046106.

[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]	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.

Kernel k-means clustering algorithm for detecting communities in complex networks based on eigenvector

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Metrics

Comments

Recommended 0