A spectral method to detect community structure based on Coulomb’s matrix

Community detection based on spectral clustering has been proved effective. However, spectral clustering is more challenging due to two significant issues: the construction of a good similarity matrix and the automatic detection of the number of clusters. In our previous paper, we developed a new similarity matrix for undirected networks based on Coulomb's law. It uses local and global measures to identify the communities efficiently using a label propagation algorithm. Thus, this paper extends our previous work to spectral clustering, and a novel community detection algorithm called SC_CL is proposed. Specifically, by exploiting the spectrum of the normalized Laplacian based on Coulomb's matrix, the graph's vertices are first embedded into a low-dimensional vector space, then k-means clustering is performed on the projected vertices. Experiments on synthetic benchmarks and real network datasets show that spectral clustering with this new similarity matrix achieves significant accuracy over existing methods. Moreover, the results provide clear and meaningful visualization of graph embedding in 2D space using dimensionality reduction.