2007/04/27 by Jianhua Ruan, Weixiong Zhang
Biochemistry, Genetics and Molecular Biology · Physics and Astronomy · #Bioinformatics and Genomic Networks #Complex Network Analysis Techniques #Gene Regulatory Network Analysis #physics.comp-ph #physics.soc-ph
paper · pdf · doi:10.1103/physreve.77.016104
published as Phys. Rev. E 77, 016104 (2008) · 14 pages, 5 figures. 1 supplemental file at http://cic.cs.wustl.edu/qcut/supplemental.pdf
arxiv created 2007/04/27 · openalex publication_date 2008/01/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Community structure is an important property of complex networks. The 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 modularity function (Q) . However, the problem of modularity optimization is NP-hard and the existing approaches often suffer from a 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 or with a higher accuracy than the existing algorithms. We also discuss two possible reasons that can cause the resolution limit problem and provide a method to distinguish them. 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 undetected.