An approximate spectral clustering for community detection based on coarsening networks

作者：Zhu Mu^*; Meng Fanrong; Zhou Yong; Yuan Guan

来源：International Journal of Advancements in Computing Technology, 2012, 4(4): 235-243.

DOI：10.4156/ijact.vol4.issue4.29

• Community detecting
• Community detection
• Community detection algorithms
• Complex networks
• Large-scale network
• Real data sets
• Spectral algorithm
• Spectral clustering
• State of the art
• Time complexity
• Time efficiencies

Recently, community detection in complex networks has attracted growing attention due to the widely applications in many fields. In the enormous variety of community detection algorithms, spectral clustering is a very famous algorithm and has excellent advantages. However, the O (n3) time complexity makes it fail in the large-scale networks. We propose an approximate spectral clustering for community detection based on coarsening the networks (CASP) to deal with the large time complexity of the traditional spectral algorithm. CASP first finds the subset most possibly belonged to the same community in the original network, and merges them into a single node. The scale of the network will decrease with the network being coarsened. Then, the spectral clustering algorithm is performed on the coarsened network with the maintained advantages and the improved time efficiency. The clustering experimental results on the synthetic and real datasets demonstrate that our method, compared with the current state-of-the art method, has superior performance.

• 出版日期2012
• 单位中国矿业大学（北京）