On Modularity Clustering

By U. Brandes, Daniel Delling, Marco Gaertler, Robert Görke, Martin Hoefer, Zoran Nikoloski, Dorothea Wagner. 2008

1,298 citations recorded by the source corpus.

Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, particularly in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomerative approach.

Subfields: Artificial Intelligence, Geometry and Topology, Statistical and Nonlinear Physics, Graph Learning

How researchers see this paper

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

In Artificial Intelligence

In Geometry and Topology

In Statistical and Nonlinear Physics

In Graph Learning

Citations in the corpus

Semi-Supervised Classification with Graph Convolutional Networks (2016, methodology): “Every node is labeled by one of four classes, obtained via modularity-based clustering (Brandes et al., 2008).”
Distance geometry and data science (2019, methodology): “tion and its solution methods: for a survey, see [72, xVI]. Solution methods based on MP are of particular interest to the topics of this survey. A BLP formulation similar to Eq. (19) was proposed in [39]. Another BLP formulation with dierent sets of 6 ROBUST SOLUTION METHODS FOR THE DGP 22 decision”
Community detection in networks: A user guide (2016, methodology): “Modularity maximisation is NP-hard (Brandes et al., 2008).”
Geographic Constraints on Social Network Groups (2010, background): “While maximizing modularity is known to be an NP-hard problem [27], there are numerous computational heuristics available [6,7].”
Local search of communities in large graphs (2014, background): “Now we show that the mCST problem, which we introduced in Section 2.1, is NP-complete.”
Social Structure of Facebook Networks (2011, neutral): “As we illustrate below, both perspectives are important because they provide complementary insights.”
Controllability of structural brain networks (2014, neutral): “Maximization of Q 0 yields a hard partition of a network into communities such that the total edge weight inside of communities is as large as possible (relative to the null model and subject to the limitations of the employed computational heuristics, as optimizing Q 0 is NP-hard 61–63 ).”
From Louvain to Leiden: guaranteeing well-connected communities (2018, methodology): “Optimising modularity is NP-hard 5 , and consequentially many heuristic algorithms have been proposed, such as hierarchical agglomeration 6 , extremal optimisation 7 , simulated annealing 4,8 and spectral 9 algorithms.”
The community-search problem and how to plan a successful cocktail party (2010, methodology): “[6] showed that it is NP-hard to optimize modularity, Fortunato and Barthelemy [14] identify the resolution-limit problem, White and Smyth [29] follow a spectral approach to optimize modularity, Agarwal and Kempe [1] develop a mathematical-programing algorithm, and many more algorithms.”
Optimal Behavioral Hierarchy (2014, background): “[46] and reformulated the problem as binary integer programming.”
NetCoMi: network construction and comparison for microbiome data in R (2020, neutral): “Modularity clustering [88] The modularity measure is maximized over all possible clusterings.”