How to Measure Significance of Community Structure in Complex Networks

Abstract

Community structure analysis is a powerful tool for complex networks, which can simplify their functional analysis considerably. Recently, many approaches were proposed to community structure detection, but few works were focused on the significance of community structure. Since real networks obtained from complex systems always contain error links, and most of the community detection algorithms have random factors, evaluate the significance of community structure is important and urgent. In this paper, we use the eigenvectors' stability to characterize the significance of community structures. By employing the eigenvalues of Laplacian matrix of a given network, we can evaluate the significance of its community structure and obtain the optimal number of communities, which are always hard for community detection algorithms. We apply our method to many real networks. We find that significant community structures exist in many social networks and C.elegans neural network, and that less significant community structures appear in protein-interaction networks and metabolic networks. Our method can be applied to broad clustering problems in data mining due to its solid mathematical basis and efficiency.

10pages,38 figures

References in corpus (5)

• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Benchmark graphs for testing community detection algorithms
• Laplacian Spectra as a Diagnostic Tool for Network Structure and Dynamics
• Accuracy and Precision of Methods for Community Identification in Weighted Networks