Community Detection via Maximization of Modularity and Its Variants

Abstract

In this paper, we first discuss the definition of modularity (Q) used as a metric for community quality and then we review the modularity maximization approaches which were used for community detection in the last decade. Then, we discuss two opposite yet coexisting problems of modularity optimization: in some cases, it tends to favor small communities over large ones while in others, large communities over small ones (so called the resolution limit problem). Next, we overview several community quality metrics proposed to solve the resolution limit problem and discuss Modularity Density (Qds) which simultaneously avoids the two problems of modularity. Finally, we introduce two novel fine-tuned community detection algorithms that iteratively attempt to improve the community quality measurements by splitting and merging the given network community structure. The first of them, referred to as Fine-tuned Q, is based on modularity (Q) while the second one is based on Modularity Density (Qds) and denoted as Fine-tuned Qds. Then, we compare the greedy algorithm of modularity maximization (denoted as Greedy Q), Fine-tuned Q, and Fine-tuned Qds on four real networks, and also on the classical clique network and the LFR benchmark networks, each of which is instantiated by a wide range of parameters. The results indicate that Fine-tuned Qds is the most effective among the three algorithms discussed. Moreover, we show that Fine-tuned Qds can be applied to the communities detected by other algorithms to significantly improve their results.

References in corpus (34)

• Fast unfolding of communities in large networks
• Community structure in social and biological 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
• Natural Scales in Geographical Patterns
• Fast algorithm for detecting community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Functional cartography of complex metabolic networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Comparing community structure identification
• Analysis of weighted networks
• Community detection in complex networks using Extremal Optimization
• Community structure in directed networks
• The performance of modularity maximization in practical contexts
• Extracting the hierarchical organization of complex systems
• Limits of modularity maximization in community detection
• Analysis of the structure of complex networks at different resolution levels
• Spectral methods for network community detection and graph partitioning
• Narrow scope for resolution-limit-free community detection
• Optimization with Extremal Dynamics
• Modularity-Maximizing Network Communities via Mathematical Programming
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• Identifying network communities with a high resolution
• Local modularity measure for network clusterizations
• Identifying "communities" within energy landscapes
• Spectral tripartitioning of networks
• Partitioning and modularity of graphs with arbitrary degree distribution
• Hierarchical multiresolution method to overcome the resolution limit in complex networks
• A New Metric for Quality of Network Community Structure
• Party Polarization in Congress: A Network Science Approach

Cited by in corpus (35)

• A Review of Stochastic Block Models and Extensions for Graph Clustering
• On community structure in complex networks: challenges and opportunities
• The many facets of community detection in complex networks
• Identifying robust communities and multi-community nodes by combining top-down and bottom-up approaches to clustering
• Network community detection using modularity density measures
• Fast and accurate determination of modularity and its effect size
• Adaptive Modularity Maximization via Edge Weighting Scheme
• Finding network communities using modularity density
• Different approaches to community detection
• A generalised significance test for individual communities in networks
• DMCS : Density Modularity based Community Search
• Community detection in multiplex networks based on orthogonal nonnegative matrix tri-factorization
• Detection of Community Structures in Networks with Nodal Features based on Generative Probabilistic Approach
• Community detection by label propagation with compression of flow
• Fuzzy Overlapping Community Quality Metrics
• Asymptotic resolution bounds of generalized modularity and multi-scale community detection
• Composite Community-Aware Diversified Influence Maximization with Efficient Approximation
• Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks
• Modularity in Multilayer Networks using Redundancy-based Resolution and Projection-based Inter-Layer Coupling
• A Spectral Representation of Power Systems with Applications to Adaptive Grid Partitioning and Cascading Failure Localization
• The Asymptotic Distribution of Modularity in Weighted Signed Networks
• Some remarks on modularity density
• A Synthetic Network Generator for Covert Network Analytics
• Parallel Toolkit for Measuring the Quality of Network Community Structure
• A General Definition of Network Communities and the Corresponding Detection Algorithm
• Improved Deep Embeddings for Inferencing with Multi-Layered Networks
• Resolution limit revisited: community detection using generalized modularity density
• High-utility itemset mining for subadditive monotone utility functions
• Optimizing Edge Sets in Networks to Produce Ground Truth Communities Based on Modularity
• Multi-View Community Detection in Facebook Public Pages
• Community detection algorithm evaluation with ground-truth data
• A new measure of modularity density for community detection
• Distributed Pseudo-Likelihood Method for Community Detection in Large-Scale Networks
• A Survey on Role-Oriented Network Embedding
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach