Finding network communities using modularity density

Abstract

Many real-world complex networks exhibit a community structure, in which the modules correspond to actual functional units. Identifying these communities is a key challenge for scientists. A common approach is to search for the network partition that maximizes a quality function. Here, we present a detailed analysis of a recently proposed function, namely modularity density. We show that it does not incur in the drawbacks suffered by traditional modularity, and that it can identify networks without ground-truth community structure, deriving its analytical dependence on link density in generic random graphs. In addition, we show that modularity density allows an easy comparison between networks of different sizes, and we also present some limitations that methods based on modularity density may suffer from. Finally, we introduce an efficient, quadratic community detection algorithm based on modularity density maximization, validating its accuracy against theoretical predictions and on a set of benchmark networks.

33 pages, 10 figures

References in corpus (44)

• Emergence of scaling in random networks
• Fast unfolding of communities in large networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Modularity and community structure in networks
• Community detection in graphs
• Uncovering the overlapping community structure of complex networks in nature and society
• Assortative mixing in networks
• Cooperative Game Theory Approaches for Network Partitioning
• The structure of scientific collaboration networks
• The diameter of the world wide web
• The large-scale organization of metabolic networks
• Functional cartography of complex metabolic networks
• Random graphs with arbitrary degree distributions and their applications
• Multilayer Networks
• Benchmark graphs for testing community detection algorithms
• The structure and dynamics of multilayer networks
• Resolution limit in community detection
• Classes of behavior of small-world networks
• Comparing community structure identification
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Synchronization reveals topological scales in complex networks
• Limits of modularity maximization in community detection
• Analysis of the structure of complex networks at different resolution levels
• Phase transition in the detection of modules in sparse networks
• Narrow scope for resolution-limit-free community detection
• Community Detection via Maximization of Modularity and Its Variants
• Characterizing the dynamical importance of network nodes and links
• Parsimonious module inference in large networks
• Modularity and Extreme Edges of the Internet
• Trophic coherence determines food-web stability
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• All scale-free networks are sparse
• The entropic origin of disassortativity in complex networks
• Currency and commodity metabolites: Their identification and relation to the modularity of metabolic networks
• From seconds to months: multi-scale dynamics of mobile telephone calls
• Generalized communities in networks
• A New Metric for Quality of Network Community Structure
• Degree correlations in directed scale-free networks
• Robust Detection of Hierarchical Communities from Escherichia coli Gene Expression Data
• Fast and accurate determination of modularity and its effect size
• Synchronization in dynamical networks with unconstrained structure switching
• Endemic infections are always possible on regular networks

Cited by in corpus (5)

• Network community detection using modularity density measures
• Identifying multi-scale communities in networks by asymptotic surprise
• Community detection based on significance optimization in complex networks
• A Study on Modularity Density Maximization: Column Generation Acceleration and Computational Complexity Analysis
• Resolution limit revisited: community detection using generalized modularity density