A modularity-maximization-based approach for detecting multi-communities in social networks

摘要

The modularity is a widely-used objective function to determine communities from a given network. The leading eigenvector method is a popular solution that applies the first eigenvector to determine the communities. The low computation cost is the major advantage of the leading eigenvector method. However, the leading eigenvector method only can split a network into two communities. To detect multiple communities, the modularity maximization is transformed to the vector partition problem (VPP). We propose an algorithm which is called as the partition at polar coordinate protocol (PPCP) to solve the VPP problem. The goal of PPCP is to find non-overlapping vertex vector sets so as to maximize the quadratic sum of the norms of community vectors. The proposed PPCP has two steps to determine the communities that are the network structure analysis and the community determination. During the network structure analysis, we obtain following issues. First, the vertex vectors belong to different communities can be separated by the distribution angles. Second, a node with a higher degree corresponds to a vertex vector with a larger norm. So, we propose three refinement functions including the noise reduction, the common-friends model and the strong connectivity hypothesis to improve the accuracy of PPCP. In our simulations, PPCP detects communities more precisely than Fine-tuned algorithm especially in the network with the weak structure. Moreover, the proposed refinement functions can capture the special properties of the network. So, PPCP with refinement functions performs much better than Fine-tuned algorithm and PPCP without refinement functions in terms of the accuracy in detecting communities.