Performance of modularity maximization in practical contexts.

By Benjamin H. Good, Y. de Montjoye, Aaron Clauset. Physical review. E, Statistical, nonlinear, and soft matter physics, 2009

968 citations recorded by the source corpus.

Although widely used in practice, the behavior and accuracy of the popular module identification technique called modularity maximization is not well understood in practical contexts. Here, we present a broad characterization of its performance in such situations. First, we revisit and clarify the resolution limit phenomenon for modularity maximization. Second, we show that the modularity function Q exhibits extreme degeneracies: it typically admits an exponential number of distinct high-scoring solutions and typically lacks a clear global maximum. Third, we derive the limiting behavior of the maximum modularity Qmax for one model of infinitely modular networks, showing that it depends strongly both on the size of the network and on the number of modules it contains. Finally, using three real-world metabolic networks as examples, we show that the degenerate solutions can fundamentally disagree on many, but not all, partition properties such as the composition of the largest modules and the distribution of module sizes. These results imply that the output of any modularity maximization procedure should be interpreted cautiously in scientific contexts. They also explain why many heuristics are often successful at finding high-scoring partitions in practice and why different heuristics can disagree on the modular structure of the same network. We conclude by discussing avenues for mitigating some of these behaviors, such as combining information from many degenerate solutions or using generative models.

Subfields: Computational Theory and Mathematics, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/2b08ec87801de2ec614cbbc881a74e1e820c13cf

How researchers see this paper

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

In Computational Theory and Mathematics

In Molecular Biology

Citations in the corpus

Community detection in networks: A user guide (2016, methodology): “22 For instance, for clustering methods based on optimisation, there are many partitions corresponding to values of the quality function very close to the searched optimum [110].”
The multilayer nature of ecological networks (2015, background): “lar ( Q obs B 0:77 and Q null B 0:73; the p-value is P < 0:001). These close values (0.73 vs. 0.77) indicate that a closer inspection regarding the nature of the modular structure is necessary [66]. More importantly, this observed modularity is larger than that of the aggregated network, which ”
A classification for community discovery methods in complex networks (2011, background): “en discovered that modularity does not have a single peak given all the possible partitions, but there are several local optima. Moreover, real networks have many near-global-optima at various places [84] (the rightmost peak in Figure 5) and we cannot know where the algorithm locates its solution. Z”
On the permanence of vertices in network communities (2014, background): “Asymptotic growth of value of a metric implies a strong dependence on the size of the network and the number of modules the network contains [11].”
Uncovering space-independent communities in spatial networks (2010, methodology): “These methods have been shown to produce useful and relevant partitions in a broad class of systems [31], even if modularity suﬀers from limitations such as resolution limit [65] and a possible high degeneracy of its landscape [66, 67].”
Non-overlapping community detection (2018, background): “For a good review of modularity limitations, refer to (Good, De Montjoye, and Clauset 2010).”
Core-Periphery Structure in Networks (2012, background): “For instance, such nodes might be assigned to different communities when applying different computational heuristics using the same notion of community structure [30], and it becomes crucial to consider their strengths of membership across different communities (e.”
Belief Network Analysis: A Relational Approach to Understanding the Structure of Attitudes (2017, background): “Second, the modularity function exhibits degeneracies that greatly compromise its reliability in many empirical settings (Good et al. 2010; Rubinov and Sporns 2011).”
Schizophrenia, neuroimaging and connectomics (2012, background): “As a result, many alternative, similarly adequate, socalled degenerate, partitions may exist (Good et al., 2010).”
Generalist Species Have a Central Role In a Highly Diverse Plant–Frugivore Network (2016, methodology): “Therefore, we ran the algorithm 25 times and combined information from the different partitions generated to assign species to a specific module (Good et al. 2010).”
Weight-conserving characterization of complex functional brain networks (2011, background): “Secondly, the study of modularity degeneracy is still in its infancy, and efficient and exhaustive search algorithms are only beginning to be developed (Good et al., 2010; Duggal et al., 2010).”
Redrawing the Map of Great Britain from a Network of Human Interactions (2010, background): “As it has been shown [13,27], a modularity function such as ours is likely to have exponentially many local maxima, and these maxima typically have different clustered structures.”
Structure and inference in annotated networks (2015, background): “The final sum in (12) is the entropy of the posterior distribution q(s), which is harder to calculate because it requires not just the marginals of q but the entire distribution.”
Modular Brain Networks (2015, background): “As a network's size and its number of communities increase, the number of partitions that achieve a near-maximal Q grows exponentially, leading to a degeneracy of high-quality partitions (Good et al. 2010).”
Improved community detection in weighted bipartite networks (2016, background): “There are four challenges to address when attempting to maximize modularity [38] which are also relevant to weighted modularity.”