关键词: 社团检测, 谱二分法, 特征值, 特征向量, 模块度

Abstract: In general, the bisection spectral method always uses only one certain eigenvalue and its corresponding  eigenvector to extract communities, which does not guarantee to obtain the best community structures. To solve this problem, this paper proposes a bisection spectral method based on the optimal eigenvectors, which utilizes the eigenvectors of transition matrices to partition the network/subnetwork into communities repeatedly, and the eigenvector used in each partition is the one whose bisection can lead to the largest modularity increment. Besides this, in order to encode the topological information into the proposed method, this paper also converts the original networks into weighted ones by utilizing the information of common neighbors of the two end vertices associated with each edge. Based on the transition matrix of the converted network, this paper applies the same bisection spectral method to extract communities. The experiments on 7 real-world networks are performed, and the experimental results show that the proposed method can extract the high-quality community structures from networks effectively.

Key words: community detection, bisection spectral method, eigenvalues, eigenvector, modularity