Abstract: In this paper we discuss some problematic aspects of Newman's modularity function QN. Given a graph G, the modularity of G can be written as QN = Qf -Q0, where Qf is the intracluster edge fraction of G and Q0 is the expected intracluster edge fraction of the null model, i.e., a randomly connected graph with same expected degree distribution as G. It follows that the maximization of QN must accomodate two factors pulling in opposite directions: Qf favors a small number of clusters and Q0 favors many balanced (i.e., with approximately equal degrees) clusters. In certain cases the Q0 term can cause overestimation of the true cluster number; this is the opposite of the well-known under estimation effect caused by the "resolution limit" of modularity. We illustrate the overestimation effect by constructing families of graphs with a "natural" community structure which, however, does not maximize modularity. In fact, we prove that we can always find a graph G with a "natural clustering" V of G and another, balanced clustering U of G such that (i) the pair (G; U) has higher modularity than (G; V) and (ii) V and U are arbitrarily different.
Recommendations
- Modularity function for community structure based on natural density of networks
- On Finding Graph Clusterings with Maximum Modularity
- On the complexity of Newman's community finding approach for biological and social networks
- When are networks truly modular?
- Finding network communities using modularity density
Cites work
Cited in
(14)- Ascent-descent variable neighborhood decomposition search for community detection by modularity maximization
- Modularized tri-factor nonnegative matrix factorization for community detection enhancement
- Modularized convex nonnegative matrix factorization for community detection in signed and unsigned networks
- Axioms for graph clustering quality functions
- Some properties of E-quality function for network clustering
- Information Theoretic Comparison of Stochastic Graph Models: Some Experiments
- Modularity function for community structure based on natural density of networks
- Comparison of linear modularization criteria using the relational formalism, an approach to easily identify resolution limit
- Comparing different modularization criteria using relational metric
- Correcting for granularity bias in modularity-based community detection methods
- Exponential quality function for community detection in complex networks
- Graph clustering with Boltzmann machines
- A node-based index for clustering validation of graph data
- When are networks truly modular?
This page was built for publication: Bad communities with high modularity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135296)
