A New Metric for Quality of Network Community Structure
arXiv:1507.04308
Abstract
Modularity is widely used to effectively measure the strength of the community structure found by community detection algorithms. However, modularity maximization suffers from two opposite yet coexisting problems: in some cases, it tends to favor small communities over large ones while in others, large communities over small ones. The latter tendency is known in the literature as the resolution limit problem. To address them, we propose to modify modularity by subtracting from it the fraction of edges connecting nodes of different communities and by including community density into modularity. We refer to the modified metric as Modularity Density and we demonstrate that it indeed resolves both problems mentioned above. We describe the motivation for introducing this metric by using intuitively clear and simple examples. We also prove that this new metric solves the resolution limit problem. Finally, we discuss the results of applying this metric, modularity, and several other popular community quality metrics to two real dynamic networks. The results imply that Modularity Density is consistent with all the community quality measurements but not modularity, which suggests that Modularity Density is an improved measurement of the community quality compared to modularity.
arXiv comment15 pages, 7 figures
References in corpus (23)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Fast algorithm for detecting community structure in networks
- Uncovering the overlapping community structure of complex networks in nature and society
- Functional cartography of complex metabolic networks
- Near linear time algorithm to detect community structures in large-scale networks
- Resolution limit in community detection
- Analysis of weighted networks
- Statistical Mechanics of Community Detection
- Link communities reveal multiscale complexity in networks
- Detecting the overlapping and hierarchical community structure of complex networks
- Community detection in complex networks using Extremal Optimization
- Community structure in directed networks
- The performance of modularity maximization in practical contexts
- Detect overlapping and hierarchical community structure in networks
- Limits of modularity maximization in community detection
- Weighted network modules
- Tolerating the Community Detection Resolution Limit with Edge Weighting
- Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
- Spectral tripartitioning of networks
Cited by in corpus (13)
- Community Detection via Maximization of Modularity and Its Variants
- Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering
- Network community detection using modularity density measures
- Adaptive Modularity Maximization via Edge Weighting Scheme
- Finding network communities using modularity density
- Extension of Modularity Density for Overlapping Community Structure
- DMCS : Density Modularity based Community Search
- Generalized Markov stability of network communities
- Parallel Toolkit for Measuring the Quality of Network Community Structure
- Resolution limit revisited: community detection using generalized modularity density
- A new measure of modularity density for community detection
- Evaluation of Community Detection Methods
- Density-based Community Detection/Optimization