When are networks truly modular?

The study of cluster or community structure of complex networks contributes to the understanding of networks at a functional level. In many networks, latent classes of nodes are suspected which manifest themselves as communities, i.e. groups of nodes with a high link density among the nodes of the same class and low link density between nodes of different classes. Community detection algorithms are used to infer these classes, e.g. by finding a partition of the network which maximizes a quality function such as the network modularity Q [M. Newman, M. Girvan, Finding and evaluating community structure in networks, Phys. Rev. E 69 (2004) 026113]. However, it is known from numerical experiments that even purely random networks display intrinsic modularity and may be partitioned yielding high values of Q. Extending on our earlier results [J. Reichardt, S. Bornholdt, Statistical mechanics of community detection, Phys. Rev. E 74 (2006) 016110], the mapping of the community detection problem onto finding the ground state of a spin glass is exploited in order to derive analytical expressions for the expected modularity in random graphs and assess the theoretical limits to community detection. The results are independent of any specific community detection algorithm and allow for differentiation between modularity arising purely due to the search process in the large configuration space of possible partitionings on the one hand, or due to the actual presence of different classes of nodes on the other hand. (c) 2006 Elsevier B.V. All rights reserved,