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

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

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

付立东^1,2;高琳¹

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

收稿日期:2009-10-12 出版日期:2010-10-20 发布日期:2010-10-11
通讯作者: 付立东
作者简介:付立东(1973-)，男，西安电子科技大学博士研究生，E-mail: fulidong2005@163.com．
基金资助:
国家自然科学基金重点资助项目(60933009);高等学校博士学科点专项科研基金资助项目(200807010013);国家自然科学基金资助项目(60970065)

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

摘要/Abstract

摘要：

为有效地检测复杂网络中的社团结构，对评估与发现社团的模块密度函数(即D值)进行了优化．通过模块密度函数的优化进程，论证了模块密度函数被优化框定到广阔的谱分聚类方法中的矩阵松散最大化，并且提出了一种新的谱分算法．该算法允许自动选择最优的社团结构数目．在经典的计算机产生的随机网络及真实世界网络中检验了该算法．特别地，当网络中社团结构变得模糊时，实验结果显示这种新的算法在发现复杂网络社团上比基于模块密度的直接核方法及基于模块函数(Q)的谱分方法更加有效．

关键词: 复杂网络, 社团结构, 模块密度, 谱分方法

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

付立东;高琳. 模块密度谱分的网络社团发现方法[J]. J4, 2010, 37(5): 916-920+965.

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.

参考文献

[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)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

Metrics

本文评价

推荐阅读 0

[1]	张书博,任淑霞,吴涛. 结合概率矩阵的改进谱聚类社区发现算法[J]. 西安电子科技大学学报, 2019, 46(3): 167-172.
[2]	付立冬;马小科;聂靖靖. 进化谱分算法检测动态网络社团结构[J]. 西安电子科技大学学报, 2018, 45(2): 43-47+53.
[3]	陈国强;王宇平. 分解多目标优化揭示复杂网络社区层次结构[J]. J4, 2013, 40(3): 205-211.
[4]	王玙;高琳. 动态网络桥系数增量聚类算法[J]. J4, 2013, 40(1): 30-35.
[5]	付立东;高琳. 特征向量的核方法检测网络社团结构[J]. J4, 2012, 39(2): 175-180.