Fast and accurate determination of modularity and its effect size

Abstract

We present a fast spectral algorithm for community detection in complex networks. Our method searches for the partition with the maximum value of the modularity via the interplay of several refinement steps that include both agglomeration and division. We validate the accuracy of the algorithm by applying it to several real-world benchmark networks. On all these, our algorithm performs as well or better than any other known polynomial scheme. This allows us to extensively study the modularity distribution in ensembles of Erdős-Rényi networks, producing theoretical predictions for means and variances inclusive of finite-size corrections. Our work provides a way to accurately estimate the effect size of modularity, providing a $z$-score measure of it and enabling a more informative comparison of networks with different numbers of nodes and links.

arXiv comment23 pages, 6 figures

References in corpus (31)

• 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
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Functional cartography of complex metabolic networks
• The structure and dynamics of multilayer networks
• Statistical Mechanics of Community Detection
• Community detection in complex networks using Extremal Optimization
• Self-similar community structure in organisations
• Community Structure in Jazz
• The performance of modularity maximization in practical contexts
• Synchronization reveals topological scales in complex networks
• Community Detection via Maximization of Modularity and Its Variants
• Characterizing the dynamical importance of network nodes and links
• Modularity and Extreme Edges of the Internet
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• 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
• Improved community structure detection using a modified fine tuning strategy
• When are networks truly modular?
• Currency and commodity metabolites: Their identification and relation to the modularity of metabolic networks
• Partitioning and modularity of graphs with arbitrary degree distribution
• Degree correlations in directed scale-free networks
• Robust Detection of Hierarchical Communities from Escherichia coli Gene Expression Data
• Endemic infections are always possible on regular networks
• Emergent bipartiteness in a society of knights and knaves

Cited by in corpus (8)

• Quantifying randomness in real networks
• Synchronization in networks with multiple interaction layers
• Network community detection using modularity density measures
• Finding network communities using modularity density
• Multi-resolution community detection in massive networks
• Reduced network extremal ensemble learning (RenEEL) scheme for community detection in complex networks
• Resolution limit revisited: community detection using generalized modularity density
• Comprehensive spectral approach for community structure analysis on complex networks