Resolution limit in community detection

Abstract

Detecting community structure is fundamental for uncovering the links between structure and function in complex networks and for practical applications in many disciplines such as biology and sociology. A popular method now widely used relies on the optimization of a quantity called modularity, which is a quality index for a partition of a network into communities. We find that modularity optimization may fail to identify modules smaller than a scale which depends on the total size of the network and on the degree of interconnectedness of the modules, even in cases where modules are unambiguously defined. This finding is confirmed through several examples, both in artificial and in real social, biological, and technological networks, where we show that modularity optimization indeed does not resolve a large number of modules. A check of the modules obtained through modularity optimization is thus necessary, and we provide here key elements for the assessment of the reliability of this community detection method.

Fig. 1.

Design of a connected network with maximal modularity. The modules (circles) must be connected to each other by the minimal number of links.

Fig. 2.

Scheme of a network partition into three or more modules. The circles on the left represent two modules ₁ and ₂, the oval on the right represents the rest of the network ₀, whose structure is arbitrary.

Fig. 3.

Schematic examples. (A) A network made out of identical cliques (which are here complete graphs with m nodes) connected by single links. If the number of cliques is larger than about $\sqrt{L}$, modularity optimization would lead to a partition where the cliques are combined into groups of two or more (represented by dotted lines). (B) A network with four pairwise identical cliques (complete graphs with m and p < m nodes, respectively); if m is large enough with respect to p (e.g., m = 20, p = 5), modularity optimization merges the two smallest modules into one (shown with a dotted line).