Identifying network communities with a high resolution

Abstract

Community structure is an important property of complex networks. An automatic discovery of such structure is a fundamental task in many disciplines, including sociology, biology, engineering, and computer science. Recently, several community discovery algorithms have been proposed based on the optimization of a quantity called modularity (Q). However, the problem of modularity optimization is NP-hard, and the existing approaches often suffer from prohibitively long running time or poor quality. Furthermore, it has been recently pointed out that algorithms based on optimizing Q will have a resolution limit, i.e., communities below a certain scale may not be detected. In this research, we first propose an efficient heuristic algorithm, Qcut, which combines spectral graph partitioning and local search to optimize Q. Using both synthetic and real networks, we show that Qcut can find higher modularities and is more scalable than the existing algorithms. Furthermore, using Qcut as an essential component, we propose a recursive algorithm, HQcut, to solve the resolution limit problem. We show that HQcut can successfully detect communities at a much finer scale and with a higher accuracy than the existing algorithms. Finally, we apply Qcut and HQcut to study a protein-protein interaction network, and show that the combination of the two algorithms can reveal interesting biological results that may be otherwise undetectable.

14 pages, 5 figures. 1 supplemental file at http://cic.cs.wustl.edu/qcut/supplemental.pdf

References in corpus (18)

• Statistical mechanics of complex networks
• The structure and function of complex networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Finding community structure in very large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Functional cartography of complex metabolic networks
• Resolution limit in community detection
• Comparing community structure identification
• Defining and identifying communities in networks
• Community detection in complex networks using Extremal Optimization
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Synchronization reveals topological scales in complex networks
• Detecting fuzzy community structures in complex networks with a Potts model
• On the uniform generation of random graphs with prescribed degree sequences
• Maximizing Modularity is hard
• Local modularity measure for network clusterizations

Cited by in corpus (13)

• Community detection in graphs
• The performance of modularity maximization in practical contexts
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Community Detection via Maximization of Modularity and Its Variants
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• Analyzing complex functional brain networks: fusing statistics and network science to understand the brain
• Improved community structure detection using a modified fine tuning strategy
• Assessing the consistency of community structure in complex networks
• Limitation of multi-resolution methods in community detection
• Axioms for graph clustering quality functions
• Adaptive Modularity Maximization via Edge Weighting Scheme
• Enhancing community detection by local structural information
• Criterions for locally dense subgraphs