On Modularity Clustering
Ulrik Brandes, Daniel Delling, Marco Gaertler et al. · IEEE Transactions on Knowledge and Data Engineering · 2008
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.
Cited by 1,242 works. doi:10.1109/tkde.2007.190689
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Data clustering
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Finding community structure in very large networks
- Fast algorithm for detecting community structure in networks
- An Information Flow Model for Conflict and Fission in Small Groups
- Resolution limit in community detection
- Comparing community structure identification
- Analysis of weighted networks