Spectral methods for the detection of network community structure: a comparative analysis

doi:10.1088/1742-5468/2010/10/P10020

	Spectral methods for the detection of network community structure: a comparative analysis
	Shen, Hua-Wei; Cheng, Xue-Qi
	2010-10-01
发表期刊	JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
ISSN	1742-5468
页码	13
摘要	Spectral analysis has been successfully applied to the detection of community structure of networks, respectively being based on the adjacency matrix, the standard Laplacian matrix, the normalized Laplacian matrix, the modularity matrix, the correlation matrix and several other variants of these matrices. However, the comparison between these spectral methods is less reported. More importantly, it is still unclear which matrix is more appropriate for the detection of community structure. This paper answers the question by evaluating the effectiveness of these five matrices against benchmark networks with heterogeneous distributions of node degree and community size. Test results demonstrate that the normalized Laplacian matrix and the correlation matrix significantly outperform the other three matrices at identifying the community structure of networks. This indicates that it is crucial to take into account the heterogeneous distribution of node degree when using spectral analysis for the detection of community structure. In addition, to our surprise, the modularity matrix exhibits very similar performance to the adjacency matrix, which indicates that the modularity matrix does not gain benefits from using the configuration model as a reference network with the consideration of the node degree heterogeneity.
关键词	analysis of algorithms random graphs networks clustering techniques
DOI	10.1088/1742-5468/2010/10/P10020
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[60873245] ; National Natural Science Foundation of China[60933005] ; National Basic Research Program of China (973)[2007CB310805]
WOS研究方向	Mechanics ; Physics
WOS类目	Mechanics ; Physics, Mathematical
WOS记录号	WOS:000286466100020
出版者	IOP PUBLISHING LTD
引用统计	被引频次：65[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/12102
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Shen, Hua-Wei
作者单位	Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Shen, Hua-Wei,Cheng, Xue-Qi. Spectral methods for the detection of network community structure: a comparative analysis[J]. JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,2010:13.
APA	Shen, Hua-Wei,&Cheng, Xue-Qi.(2010).Spectral methods for the detection of network community structure: a comparative analysis.JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT,13.
MLA	Shen, Hua-Wei,et al."Spectral methods for the detection of network community structure: a comparative analysis".JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT (2010):13.