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

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

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

付立东^1,2;高琳²

(1. 西安电子科技大学计算机学院，陕西西安 710071;
2. 西安科技大学计算机学院，陕西西安 710054)

收稿日期:2010-12-27 出版日期:2012-04-20 发布日期:2012-05-21
通讯作者: 付立东
作者简介:付立东(1973-)，男，副教授，西安电子科技大学博士研究生，E-mail: fulidong2005@163.com．
基金资助:
国家自然科学基金重点资助项目(60933009);国家自然科学基金资助项目(61100157,61072103);西安科技大学培育基金资助项目(2010029)

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

摘要/Abstract

摘要：

为在权重的复杂网络中检测社团结构，推广模块密度函数到权重形式，并优化权重形式的权重密度函数到谱分聚类形式及权重的核聚类形式．证明了基于权重密度的两类聚类方法在数学上的等价性，利用这种等价性，提出了一种新的基于特征向量核聚类检测复杂网络社团方法．实验结果表明，这种方法比直接的谱分方法或直接的核方法检测社团更加准确．

关键词: 社团结构, 模块密度, 核k-means, 谱分方法, 特征向量的核方法

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

中图分类号:

付立东;高琳. 特征向量的核方法检测网络社团结构[J]. J4, 2012, 39(2): 175-180.

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.

参考文献

［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]	付立冬;马小科;聂靖靖. 进化谱分算法检测动态网络社团结构[J]. 西安电子科技大学学报, 2018, 45(2): 43-47+53.
[2]	王玙;高琳. 动态网络桥系数增量聚类算法[J]. J4, 2013, 40(1): 30-35.
[3]	付立东;高琳. 模块密度谱分的网络社团发现方法[J]. J4, 2010, 37(5): 916-920+965.

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

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

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 3

Metrics

本文评价

推荐阅读 0