二谱分聚类的复杂网络社团检测方法

J4 ›› 2012, Vol. 34 ›› Issue (1): 34-37.

二谱分聚类的复杂网络社团检测方法

付立东

（1.西安科技大学计算机科学技术学院，陕西西安 710054；
2.西安电子科技大学计算机科学工程学院，陕西西安 710071）

收稿日期:2010-03-30 修回日期:2011-02-25 出版日期:2012-01-25 发布日期:2012-01-25
基金资助:
国家自然基金重点项目（60933009);教育部高校博士点基金资助项目（200807010013);西安科技大学培育基金（2010029）

Detecting Community Structures in Complex Networks:A Bisection Spectral Clustering Approach

FU Lidong

(1.School of Computer Science and Technology,Xi’an University of Science and Technology,Xi’an 710054;
2.School of Computer Science and Engineering,Xidian University,Xi’an 710071,China)

Received:2010-03-30 Revised:2011-02-25 Online:2012-01-25 Published:2012-01-25

摘要/Abstract

摘要：

近年来，复杂网络中的社团发现越来越受到研究人员的关注并且许多方法被提了出来。为有效地检测复杂网络中的社团结构，优化了评估与发现社团的模块密度函数(即D值)。通过模块密度的优化进程，证明了模块密度函数能写成模块密度矩阵迹的最大化表达形式。利用模块密度矩阵的谱分分解，提出了一种新的二谱分的聚类检测复杂网络社团方法。在LFR标准人工模型网络中验证了二谱分方法的有效性。实验结果显示这种新的方法在发现复杂网络社团上有较高的准确性。

关键词: 社团结构, 模块密度, 二谱分聚类方法

Abstract:

In recent years, the problem of community structure detection has attracted more and more attention and many approaches have been proposed. To detect community structures in complex networks, the modularity density function (D value) is optimized, by optimizing process, the modularity density function can be expressed as a trace maximization form about the modularity density matrix. By spectral optimization of modularity density matrix, a bisection spectral clustering approach is proposed to detect communities in complex networks. The algorithm is validated in the LFR benchmark networks. Experimental results show the significance of the proposed approach.

Key words: community structures;modularity density;bisection spectral clustering

付立东. 二谱分聚类的复杂网络社团检测方法[J]. J4, 2012, 34(1): 34-37.

FU Lidong. Detecting Community Structures in Complex Networks:A Bisection Spectral Clustering Approach[J]. J4, 2012, 34(1): 34-37.

参考文献［18］

［1］	Fortunato S, Latora V, Marchiori M. Method to Find Community Structure Based on Information Centrality［J］. Physical Review E, 2004, 70(13):056105.
［2］	Girvan M,Newman M E J.Community Structure in Social and Biological Networks［J］. Proceedings National Academy Science USA, 2002,99(12),78217826.
［3］	Duch J, Arenas A. Community Detection in Complex Networks Using Extremal Optimization［J］. Physical Review E, 2005,72(2):(027104).
［4］	Clauset A, Newman M E J,Moore C. Finding Community Structure in Very Large Networks［J］. Physical Review E, 2004,70(066111).
［5］	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.
［6］	Newman M E J. The Structure and Function of Complex Networks［J］. SIAM Review, 2003, 45(2):167256.
［7］	Newman M E J, Girvan M. Finding and Evaluating Community Structure in Networks［J］. Physical Review E,2004,69(2):026113.
［8］	Radicchi F, Castellano C, Cecconi F, et al. Defining and Identifying Communities in Networks［J］. Proceeding of National Academy Science USA, 2004,101:26582663.
［9］	Newman M E J. Finding Community Structure in Networks Using the Eigenvectors of Matrices［J］. Physical Review E, 2006,74(3):036104.
［10］	Newman M E J. Modularity and Community Structure in Networks［J］. Proceeding of National Academy Science USA, 2006,103:85778582.
［11］	Fortunato S, Barthélemy M. Resolution Limit in Community Detection［J］. Proceeding of National Academy Science USA, 2007,104(1):3641.
［12］	Li Z P, Zhang S H, Wang R S, et al. Quantitative Function for Community Detection［J］. Physical Review E, 2008,77(3):036109.
［13］	Dhillon I S, Guan Y, Kulis B. Spectral Clusterng and Normalized Cuts［C］∥Proc of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004:551556.
［14］	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.
［15］	付立东，高琳. 模块密度谱分的复杂网络社团发现方法［J］. 西安电子科技大学学报, 2010,37（5）：916920.
［16］	付立东.复杂网络社团的谱分检测方法［J］. 计算机工程, 2011,37（1）：3133.
［17］	Lancichinetti A, Fourtunato S, Radicchi F. Benchmark Graphs for Testing Community Detection Algorithm［J］. Physical Review E, 2008, 78:046110.
［18］	Danon L, DiazGuilera A, Duch J et.al. Comparing Community Structure Identification［J］. Journal of Statistical Mechanics Theory and Experiment, 2005(9):09008.