Limits of modularity maximization in community detection

By Andrea Lancichinetti, Santo Fortunato. Physical review. E, Statistical, nonlinear, and soft matter physics, 2011

470 citations recorded by the source corpus.

Modularity maximization is the most popular technique for the detection of community structure in graphs. The resolution limit of the method is supposedly solvable with the introduction of modified versions of the measure, with tunable resolution parameters. We show that multiresolution modularity suffers from two opposite coexisting problems: the tendency to merge small subgraphs, which dominates when the resolution is low; the tendency to split large subgraphs, which dominates when the resolution is high. In benchmark networks with heterogeneous distributions of cluster sizes, the simultaneous elimination of both biases is not possible and multiresolution modularity is not capable to recover the planted community structure, not even when it is pronounced and easily detectable by other methods, for any value of the resolution parameter. This holds for other multiresolution techniques and it is likely to be a general problem of methods based on global optimization.

Subfields: Molecular Biology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/d4d9eb25acc7d62c02c83f2cea3fb2af3e388dd4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Networks beyond pairwise interactions: structure and dynamics (2020, unknown): “[41] Andrea Lancichinetti and Santo Fortunato.”
Belief Network Analysis: A Relational Approach to Understanding the Structure of Attitudes (2017, methodology): “…small modules in large networks, as well as (ii) large modules in small networks, even when the existence of such modules appears intuitively clear and can be easily determined by other methods (Fortunato and Barthélemy 2007; Good, de Montjoye, and Clauset 2010; Lancichinetti and Fortunato 2011).”
Clustering attributed graphs: Models, measures and methods (2015, background): “Although this measure suffers from some well-known pitfalls (Fortunato & Barthélemy, 2007; Lancichinetti & Fortunato, 2011), it has recently been at the basis of several graph clustering methods and it has also been extended to deal with attributed graphs.”
Hierarchical block structures and high-resolution model selection in large networks (2013, background): “In addition to the lack of statistical validation, modularity maximization fails to detect clusters with size below a given threshold [14, 15], which increases with the size of the system as ∼ √ E , where E is the number of edges in the entire network.”
Modular Brain Networks (2015, methodology): “One such method is OSLOM (Order Statistics Local Optimization Method) (Lancichinetti et al. 2011), which scores communities based on how likely it is to find a community with similar properties in a random network with no community structure (Lancichinetti et al. 2010).”
Community detection in networks: A user guide (2016, background): “This is because modularity maximisation has an additional bias: large subgraphs are usually split in smaller pieces [156].”
Community detection in Attributed Network (2018, background): “Modularity optimization approaches make assumption that the best partition of a graph is the one that maximizes the modularity, but [12], [16] have shown that this assumption can not be satisfied if the modularity is not a pertinent measure for some graphs.”
On the permanence of vertices in network communities (2014, background): “Furthermore, Lancichinetti and Fortunato [16] stated that even those multi-resolution versions of modularity are not only inclined to merge the smallest well-formed communities, but also to split the largest well-formed communities.”
Using Geodesic Space Density Gradients for Network Community Detection (2017, background): “Index Terms—Complex Networks, Community Detection, Geodesic Space, Geodesic Distance, Density Field Gradients F”