Date Added: Mar 2012
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. The authors 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.