Measuring the significance of community structure in complex networks

Many complex systems can be represented as networks, and separating a network into communities could simplify functional analysis considerably. Many approaches have recently been proposed to detect communities, but a method to determine whether the detected communities are significant is still lacking. In this paper, an index to evaluate the significance of communities in networks is proposed based on perturbation of the network. In contrast to previous approaches, the network is disturbed gradually, and the index is defined by integrating all of the similarities between the community structures before and after perturbation. Moreover, by taking the null model into account, the index eliminates scale effects. Thus, it can evaluate and compare the significance of communities in different networks. The method has been tested in many artificial and real-world networks. The results show that the index is in fact independent of the size of the network and the number of communities. With this approach, clear communities are found to always exist in social networks, but significant communities cannot be found in protein interactions and metabolic networks.