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 (16)

• Fast unfolding of communities in large networks
• Modularity and community structure in networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Benchmark graphs for testing community detection algorithms
• The structure and dynamics of multilayer networks
• Resolution limit in community detection
• Comparing community structure identification
• 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
• Characterizing the dynamical importance of network nodes and links
• Parsimonious module inference in large networks
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• The entropic origin of disassortativity in complex networks
• Degree correlations in directed scale-free networks
• Fast and accurate determination of modularity and its effect size